Rekurze

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Rekurzivně definovaný Sierpinského trojúhelník.

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[editovat | editovat zdroj]

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[zdroj?], 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í.

V praktických aplikacích obvykle po každém rekurzivním volání funkce dochází ke zjednodušení problému. Takové funkce končí. 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í[editovat | editovat zdroj]

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. Průběh rekurze je možné znázornit jako strom. Pro dvě volání v jednom průchodu vzniká binární strom, pro tři ternární strom, atd.

Počet rekurzivních volání nemusí být stejný, např. při rekurzivním procházení grafu voláme zpracování na všechny sousedy vrcholu, a těch je obecně různý počet.

Příklady využití[editovat | editovat zdroj]

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, tvorbě a zpracovávání datových struktur. Vytvořený objekt obsahuje prvek stejného typu. Definujeme tak potenciálně nekonečnou datovou strukturu konečným způsobem (například u dynamických struktur, kdy předem neznáme potřebnou velikost). Při tvorbě datové struktury pak určíme skutečnou 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 zápisu a řešení problému.

Rekurze se velmi často využívá při syntaktické analýze textů formálních jazyků (programovací jazyky, matematické vzorce).

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.

Obecně, popis algoritmů pro rekurzivní datové struktury (stromy, adresáře, ale i čísla) se jednoduše zapíše rekurzivně.

Velmi zajímavou oblastí použití rekurze jsou fraktály.

Rekurze v programovacích jazycích[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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.


Faktoriál[editovat | editovat zdroj]

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, jiným testování N >= 0 před voláním.

Pokud úloha má přímočaré nerekurzivní řešení, bývá rychlejší. Často však ztrácí na přehlednosti, je pracnější ho vymyslet a kvůli složitosti je náchylnější k chybám. 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

Příklad rekurzivní funkce v programovacím jazyce C:

double faktorial(int f){
	if (f <= 1) 
		return 1;
	else 
		return f * faktorial(f - 1);
}

Robot Karel[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Ukázkou vhodného užití rekurze je třídící algoritmus QuickSort. Jedná se o jeden z nejrychlejších (pouze v příznivém případě (je častý)) a zároveň i jednodušších algoritmů řazení. Princip spočívá v rozdělení posloupnosti čísel do dvou oblastí na základě srovnání s hodnotou nějakého vhodně zvoleného členu posloupnosti – nazýváme ji pivot. Do první oblasti umístíme čísla menší než pivot a do druhé čísla větší. (Pivot se často volí z prostřed posloupnosti pro případ uspořádané nebo částečně uspořádané posloupnosti.) Dále se obě části rekurzivně řadí stejným postupem, dokud nebudou mít jednotlivé úseky pouze jeden člen. V momentě, kdy jsou takto seřazeny obě části, je seřazená i celá posloupnost.

Program v jazyce C++
void QuickSort(int Array[], int Left, int Right) // Array[] – odkaz na pole prvků typu
{ // int (celé číslo)
  int i, tmp, pivot, l, r;
 
  pivot = Array[(Left+Right)/2];
  l = Left;
  r = Right;
 
  do {                                        // cyklus s podmínkou na konci
    while (Array[l] < pivot) { l++; }         // l++, r-- zvětšení/zmenšení o jedničku 
    while (Array[r] > pivot) { r--; }
 
    if (l < r) {                              // prohození čísel
      tmp = Array[l];
      Array[l] = Array[r];
      Array[r] = tmp;
      l++; r--; }
    else {
      if (l == r) {                           // "překřížení" l a r
        l++; r--;
      }
    }
  } while (l <= r);                           // podmínka "do" cyklu
 
  if (r > Left) { QuickSort(Array, Left, r); }
  if (l < Right) { QuickSort(Array, l, Right); }
}

Efektivita rekurzivních algoritmů[editovat | editovat zdroj]

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.

Koncová rekurze je optimalizacní technika, která snižuje spotřebu paměti pro ukládání návratových adres. V případě lineární rekurze optimalizovaný program může počítat bez používání zásobníku (v konstantní paměti).

Fibonacciho posloupnost[editovat | editovat zdroj]

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 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ískat 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í. used

Tabelace[editovat | editovat zdroj]

Tabelace je způsob odstraňování neefektivity pocházející z opakovaných volání se stejnými argumenty. Spočítané výsledky se ukládají (např. do pole) a místo opakovaného volání se použije výsledek z tabulky, do které se zaznamená po prvním výpočtu s danými argumenty. Položky tabulky potřebují kromě uložené hodnoty 1 bit navíc, který určuje, zda jsou data platná, tj. už spočítána. Tabelace se často používá v dynamickém programování. Tento přístup je trade-off času a paměti.

Výhoda je, že nemusíme měnit rekurzivní algoritmus. Nevýhoda je potřeba paměti pro tabulku, která je případně větší než při "ručním" návrhu a počítání zdola. V případě Fibonacciho čísel použijeme pole P[] velikosti N.

Tabelace nemá smysl, pokud se počítají v rekurzi různé hodnoty, příklad je výpočet FFT.

Humor o rekurzi[editovat | editovat zdroj]

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í dříve nebo později k vyčerpání paměti a (v lepším případě) následuje násilné ukončení 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.

Související články[editovat | editovat zdroj]