Rekurze

Z Multimediaexpo.cz

Foldable Fractal 2.0

Foldable Fractal 2.0

Rekurzivní polévka (2006)

Rekurze je často používaná technika v matematice a informatice. Termín je pravděpodobně odvozen z latinského slovesa recurso (vrátit se) nebo substantiva recursus (návrat, zpětný běh).

Co je rekurze

V oblasti matematiky pojem rekurze chápeme jako definování objektu pomocí sebe sama. Využívá se například pro definici přirozených čísel, stromových struktur a některých funkcí. V imperativním programování rekurze představuje opakované vnořené volání stejné funkce (podprogramu), v takovém případě se hovoří o rekurzivní funkci. Nedílnou součástí rekurzivní funkce musí být ukončující podmínka určující, kdy se má vnořování zastavit. Jelikož bývá nejčastějším zdrojem chyb, je třeba ji navrhnout dostatečně robustním způsobem a prověřit veškeré možné stavy. Pro uplatnění rekurzivních algoritmů je zapotřebí, aby programovací jazyk umožňoval volání podprogramu ještě před ukončením jeho předchozího volání. Po každém kroku volání sebe sama musí dojít ke zjednodušení problému. Pokud nenastane koncová situace, provede se rekurzivní krok. Každý algoritmus využívající rekurzi lze přepsat do nerekurzivního tvaru při použití zásobníku nebo jiné paměťové struktury.

Základní rozdělení

Rekurzivní chování může být různé v závislosti na tom, kolik podprogramů se jí účastní. Rozlišujeme dva základní typy dělení:

• Přímá rekurze nastává, pokud podprogram volá přímo sám sebe.
• Nepřímá (vzájemná) rekurze je situace, kdy vzájemné volání podprogramů vytvoří „kruh“. Např. v příkazové části funkce A je volána funkce B, ve funkci B voláme funkci C, která volá funkci A.

Druhé dělení:

• Lineární rekurze nastává, pokud podprogram při vykonávání svého úkolu volá sama sebe pouze jednou. Vytváří se takto lineární struktura postupně volaných podprogramů.
• Stromová rekurze nastává, pokud se funkce nebo procedura v rámci jednoho vykonání svého úkolu vyvolá vícekrát. Vzniklou strukturu je možné znázornit jako strom. Pro 2 volání v jednom průchodu vzniká binární strom, pro 3 volání ternární strom, atd.

Při kombinaci zmíněných typů rekurze lze docílit velmi komplikovaných struktur. Je třeba připomenout, že již z charakteru takovéhoto volání podprogramů nelze docílit jiné, než symetrické struktury.

Humor o rekurzi

Některé definice rekurze v sobě zahrnují prvky humoru a parodie na výkladové slovníky:

Cyklus nekonečný

viz Nekonečný cyklus

Nekonečný cyklus

viz Cyklus nekonečný

Tyto žerty v sobě však nesou poučení o nesprávném užívání rekurze a podávají jej poměrně zábavnou a srozumitelnou formou. Hlavním problémem předchozí ukázky je absence ukončující podmínky. Jak již bylo řečeno, ukončující podmínka je nedílnou součástí rekurze a její nesprávná formulace často vede na nekonečný cyklus (či cyklus nekonečný) a tím dochází k zhroucení programu. Poněkud matoucí je i výklad rekurzivní zkratky. Například zkratka GNU v angličtině znamená „GNU's Not Unix“ (česky „GNU není Unix“), zkratka je tedy součástí definice významu samotné zkratky.

Příklady využití

Díky rekurzi lze definovat nekonečnou strukturu objektů konečným popisem, nekonečné výpočty realizovat konečným zápisem rekurzivního programu. V programování je rekurze využívána k definici rozsáhlých datových struktur. Vytvořený objekt obsahuje prvek stejného typu. Definujeme tak nekonečnou datovou strukturu konečným způsobem (například u dynamických struktur, kdy předem neznáme potřebnou velikost). Rekurzivní definice binárního stromu:

typedef struct { // definice typu uzel
    unsigned int data;
    uzel* levyPotomek;    // potomek je také typu uzel
    uzel* pravyPotomek;
} uzel

Dalším využitím je řešení obecných úloh rozkladem na dílčí úlohy stejného typu, které řešíme stejným způsobem. Tento způsob řešení je klíčem k návrhu mnoha důležitých algoritmů, proto je jednou ze základních částí dynamického programování. Často jej nalezneme pod označením „rozděl a panuj“, anglicky „divide and conquer“. Tato programovací technika je vhodná pouze pro omezený okruh úloh, u nichž je rozdělení na menší nezávislé úlohy stejného charakteru možné a přirozené. Pokud lze rekurzi takto využít, vede většinou ke krátkému a efektivnímu řešení problému. Rekurze se velmi často využívá při syntaktické analýze textů formálních jazyků (programovací jazyky, matematické vzorce), například pomocí regulárních výrazů. Typickým příkladem přirozeně rekurzivního algoritmu je průchod stromem:

void ProjdiStrom(uzel x) {
   unsigned int i = 0;
   while (i < x.count) {
       ProjdiStrom(x.children[i]);
       i++;
   }
   ZpracujUzel(x);    // zde jsou prováděny operace s daty uloženými v daném uzlu
}

Pro zpracování celého stromu voláme na počátku proceduru s počátečním parametrem - kořenový uzel. Procedura rekurzivně volá sebe sama pro potomky aktuálního uzlu (tedy pro podstromy daného stromu), dokud nedosáhne k uzlům, které nemají žádné potomky (uzly bez potomků jsou nazývány „listy“). Při vykonání určité operace se všemi soubory v adresářové struktuře na pevném disku je možné použít rekurzi, neboť na každý nalezený podadresář lze automaticky zavolat stejnou funkci. Velmi zajímavou oblastí použití rekurze jsou fraktály.

Rekurze v programovacích jazycích

Jednou ze základních součástí většiny programovacích jazyků jsou cykly. Jedná se o nejrozmanitější obměny syntaxe příkazů for, while a jim podobných. Cílem těchto nástrojů je umožnit programování opakovaných činností. Existují však i jazyky, které dokazují, že cykly nejsou jedinou cestou, a jejich užití buď nepodporují vůbec, či využívají těchto nástrojů pouze zřídka. Jedná se například o Lisp či Prolog. Pro řešení opakovaných činností používají právě rekurzi a suverénně dokazují, že v mnoha případech se jedná o mocnější a univerzálnější techniku.

Rekurzivní definice

Definice tohoto typu mají zpravidla dvě základní části. Počáteční tvrzení a způsob, jak z aktuálního stavu odvodíme stav následující. Příkladem rekurzivní definice může být definice přirozených čísel:

• 0 je z N
• Pokud n je z N, pak n + 1 je z N
• Soubor přirozených čísel je nejmenší soubor uspokojující předchozí dvě vlastnosti.

Rekurzivní důkazy

Standardní způsob, jak definovat nové matematické či logické systémy je definovat objekty (typu “true” a “false”) a operace pro manipulaci s nimi. Veškeré platné výpočty v systému jsou pak definovány pravidly pro skládání těchto základních případů. Pokud dokážeme, že základní případy a pravidla jsou vypočítatelná, pak jakákoli rovnice v matematickém systému bude také vypočítatelná. Může to znít nezajímavě, avšak tento druh důkazu je používán pro určení, zda výpočet je či není nemožný. Tím může často ušetřit hodně času. Například, tento druh důkazu byl použit pro dokázání, že obsah kruhu není jednoduchým poměrem jeho průměru, a že žádný úhel nemůže být roztrojen s kružítkem a pravítkem — obě hádanky fascinovaly staré národy.

Faktoriál

Nejčastějším příkladem rekurzivní funkce je výpočet faktoriálu N!, který lze spočítat pro celá kladná čísla podle vztahu \(N! = N \cdot (N-1)!</math> a pro \(N = 0</math> je \(N! = 1</math>

faktoriál(N):
  pokud N = 0, potom výsledek = 1,
  jinak výsledek = N * faktoriál(N - 1)

faktoriál (N):
  pokud N < 0, potom konec,
  jinak
    výsledek = 1,
    pro i od 1 do N proveď
      výsledek = výsledek * i,
konec

DoPulky
znamena
  kdyz bude zed
    vlevo
    vlevo
  jinak
    krok
    krok
    DoPulky
    krok
  konec
konec

static void QuickSort(ref int[] array, long VLEVO, long VPRAVO){
   int PIVOT = array[((VLEVO + VPRAVO)/2)];
   long L = VLEVO;
   long P = VPRAVO;
   do {
      while (array[L-1] < PIVOT) { L++;}
      while (PIVOT < array[P-1]) { P--;}
      if(L <= P){                         // prohození čísel
         int TMP = array[L-1];
         array[L-1] = array[P-1];
         array[P-1] = TMP;
         L++;
         P--;
      }
   }while(!(L > P));
   if (VLEVO < P){ QuickSort(ref array, VLEVO, P); }    // rekurzivní volání
   if (L < VPRAVO){ QuickSort(ref array, L, VPRAVO); }  // rekurzivní volání
}

fibonacci(N):
  pokud N < 2, potom
    pokud N < 1, potom výsledek = 0,
    jinak výsledek = 1,
  jinak
    výsledek = fibonacci(N-1) + fibonacci(N-2)

fibonacci(N):
  P je pole[0 .. MaxN]
  P[0] = 0;
  P[1] = 1;
  pro i od 2 do N proveď
     P[i] = P[i-1] + P[i-2],
  výsledek = P[N]
konec