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)!\) a pro \(N = 0\) je \(N! = 1\)

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

Jelikož při každém průchodu funkcí snižujeme hodnotu čísla N a testujeme, zda již N nabylo hodnoty 0, má funkce konec. Poznámka: V uvedeném příkladu je chyba, pokud je uvedená funkce volána pro číslo menší než nula, nebude nikdy splněna ukončující podmínka a dojde k zhroucení programu. Jedním z možných řešení je nahrazení podmínky N = 0 za N <= 0. Pokud úloha má přímočaré nerekurzivní řešení, bývá rychlejší. Často však ztrácí na přehlednosti. Vhodnou metodou může být například iterace:

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

Robot Karel

Jiným příkladem rekurzivního algoritmu může být úkol pro robota Karla, aby ušel polovinu vzdálenosti od místa, kde stojí, k protilehlé zdi, přestože neví, jak je zeď daleko. V takovém případě stačí vytvořit proceduru, během které v případě, že stojí již před zdí, tak se otočí čelem vzad, jinak udělá dva kroky, zavolá stejnou proceduru a udělá krok. (Předpokládejme, že před Karlem je sudý počet volných políček.)

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

Quicksort

Ukázkou vhodného užití rekurze je třídící algoritmus QuickSort. Jedná se jeden z nejrychlejších a zároveň i jednodušších algoritmů řazení. Princip spočívá v rozdělení posloupnosti čísel do dvou oblastí. Do jedné umístíme menší čísla než nějaká náhodně zvolená hodnota (nazýváme ji pivot) a do druhé větší. Při vhodném zvolení pivotu jsou obě oblasti přibližně stejně velké. V momentě, kdy jsou seřazeny obě části, je seřazená i celá posloupnost. Obě části se rekurzivně řadí stejným postupem, dokud nebudou mít jednotlivé úseky pouze jeden člen.

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í
}

Efektivita rekurzivních algoritmů

Použití rekurze v algoritmech s sebou přináší výhody i nevýhody. Hlavní výhodou je jednoduchost a přehlednost algoritmu. Naopak hlavní nevýhodou je, že algoritmus pro velký počet vnoření obsadí poměrně velké množství paměti. Při každém vyvolání podprogramu je automaticky provedeno několik kroků. Uložení lokálních proměnných (proměnných používaných pouze pro potřeby aktuálně běžícího podprogramu) do zásobníku, předání parametrů a návratové adresy a skok do podprogramu. Po ukončení rekurze se díky uloženým návratovým adresám procházíme zpět stejnou cestou a uložené informace si opět vyzvedáváme.

Fibonacciho posloupnost

Fibonacciho posloupnost je vhodnou ukázkou, jak lze řešit rekurzívní úlohu různými a různě efektivními způsoby. Jedná se o posloupnost, jejíž první člen \(f(0)=0\), druhý člen \(f(1)=1\) a každý další člen je součet dvou předchozích. Prvních několik členů vypadá následovně:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

n-tý člen posloupnosti lze nalézt pomocí rekurzivního algoritmu. Funkce se volá sama sebe pro výpočet dvou předchozích členů posloupnosti a ty následně sečte. Struktura volání podprogramů tvoří strom. Tento způsob výpočtu má exponenciální časovou složitost. Je to dáno tím, že při výpočtu vyšších čísel počítáme stále častěji prvky, které jsme již počítali.

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)

n-té Fibonacciho číslo lze spočítat i bez rekurze. Stačí prvky posloupnosti počítat od začátku a ukládat je například do Pole (datová struktura). První dva členy jsou dány (0, 1) a každým součtem předchozích dvou prvků lze získát další prvek.

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

Dokonce stačí ukládat si jen poslední dvě hodnoty a paměťovou složitost tak zredukovat na konstantní.

Související články

• Rekurzivní funkce
• Fraktál