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).

Používá se i v přirozeném jazyce a jsou i rekurzivní obrázky, např. od M. C. Eschera.

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. Obvyklou součástí rekurzivní funkce je ukončující podmínka určující, kdy se má vnořování zastavit. V tom případě funkce vrací výsledky spočítané nerekurzivně. Chyba v rekurzi může způsobit vyčerpání zásobníku a následně ukončení programu anebo zacyklení.

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í. Obvyklý způsob implementace (v překladači) je, že data volající funkce se uloží na zásobník předtím, než se volá rekurze.

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. Nicméně jsou i programy, které ukončující podmínku neobsahují nebo se k ní nedostanou, např. filtry nebo pípy v Unixu. Ty cyklí v nekonečném cyklu, ale přitom můžou zpracovávat nekonečný proud dat (stream) a/nebo ho generovat.

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. A spíš v teorii, i naopak.

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. Podstatné je, že podprogram nevolá sám sebe přímo, ale přes prostředníka.

Nepřímá rekurze může nastat jak při vytváření datových struktur (nejsou jen binární stromy), tak u funkcí.

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 strukturu konečných i (některých) nekonečných 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 nebo podstrukturu stejného typu. Definujeme tak libovolně velikou 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 anebo se dynamická struktura tvoří postupně (streamy) .

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í v jednom z popisů dynamického programování. Často jej nalezneme v algoritmech typu „rozděl a panuj“, anglicky „divide and conquer“. Tato programovací technika je vhodná pouze pro omezený okruh úloh,[zdroj?] 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 a algoritmu. Pokud chceme výhod rekurze využít pro úlohy, které se nedělí na úlohy stejného charakteru , ale pouze podobného charakteru, tak je potřeba úlohu nebo algoritmus zobecnit.

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

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

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.

Rekurzi obsahují v nějaké podobě všechny moderní programovací jazyky, jako (podle abecedy) C, C++, Java, Pascal a dnes snad i Fortran, který ji původně neměl.

I klasické jazyky dokáží i klasicky zadané rekurzivní algoritmy (například quicksort a mergesort) vyjádřit přímočaře rekurzivně anebo pomocí cyklů či jiných prostředků jazyka, a to i v případě , že použitá datová struktura je pole.

Vzpomínaný Lisp a Prolog používají rekurzi při zpracování rekurzivních datových struktur, s-výrazů nebo termů. V klasických jazycích je přirozenější při zpracování pole použít for-cyklus a i++.

Rekurze se pro praktické účely a při optimalizaci často odstraňuje. Viz dále.

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); }
}

Rekurze a datové struktury[editovat | editovat zdroj]

Postup výpočtu a vzájemná volání procedur lze popsat a znázornit stromem volání, nebo v případě tabelace orientovaným acyklickým grafem. Strom výpočtu může sloužit pro ilustraci algoritmu a pro výuku a obvykle se explicitně v programu nevytváří, ale např. při syntaktické analýze v algoritmu analýze rekurzivním sestupem je strom ve vhodné podobě výstupem této fáze zpracování.

Rekurzí se přirozeně procházejí a zpracovávají rekurzivní datové struktury.

Rekurze, ale nejen ona, může zpracovávat i (potenciálně) nekonečné vstupy a generovat i (potenciálně) nekonečné výstupy, případně oboje zároveň. Data se můžou generovat líně a zpracovávat synchronizovaně, takže může stačit konečná, někdy i malá paměť (buffer). Pro odlišení potenciálně nekonečných dat (stream) od obvyklých konečných dat (spojový seznam), i když libovolně velkých, se pro ty první používá pojem codata. Pro představu, simulátor konečného automatu, který dostává nekonečný proud písmenek a vrací nekonečný proud svých stavů, bude ukončen z jiných příčin. Pokud simulátor rozeznává konec proudu EOF, tak může i skončit.

Je vhodné si ale uvědomit, že i když rekurze nezpůsobí přetečení, zpracovávaná data typicky rostou (například když počítáme délku streamu nebo něco z něho logujeme) a tak prakticky omezeni jsme.

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. Pro vyjasnění spotřeby paměti, programová rekurze ukládá obvykle všechny lokální proměnné (protože statická analýza kódu je ještě nedokonalá), kdežto ruční obsluha zásobníku ukládá pouze potřebné informace.

Pokud máme víc rekurzivních volání za sebou v stejném podprogramu, tak jedno volání po skončení dealokuje svojí paměť a další volání ji znovupoužívá. Paměť se tím přirozeně a automaticky šetří a spotřeba paměti je obvykle menší než časová složitost, i když existují i výjimky, například prohledávání grafu do hloubky může na zásobník uložit všechny vrcholy grafu. Viz také vhodná implementace quicksortu a fibonacciho posloupnosti. Stručně řečeno, paměť pro zásobník odpovídá maximálnímu zanoření rekurze.

Koncová rekurze je automatická 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), stejně jako while cyklus. V obecném případě poslední volání neukládá data na zásobník, ale přepíše nebo dealokuje rámec volající procedury. Optimalizaci lze provádět pro přímou i nepřímou rekurzi. Ne všechny kompilátory tuto techniku podporují. V některých případech je nutné (a vhodné) upravit program, aby se optimalizace koncové rekurze dala použít.

Když algoritmus "se napsal" rekurzivně a nelze odhadnout maximální hloubku zanoření potřebnou k vyřešení problému, lze hloubku natvrdo stanovit jako vstupní parametr, nebo lépe postupně zvětšovat. Tato technika se nazývá iterativní prohlubování (iterative deepening).

Tabelace a obecné odstraňování rekurze refaktorizací programu je popsáno v podkapitolách.

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 předpisu f(n)=f(n-1)+f(n-2) a z něho odvozeného 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 opakovaně 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. Na podobné chování, tj. ne příliš optimalizované - z hlediska paměti, vede použití tabelace na rekurzivní algoritmus.

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

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.

Pole může být vícerozměrné, kdy počet rozměrů odpovídá počtu argumentů. Anebo jednorozměrné, použité jako hašovací tabulka. První reprezentace je výhodná, pokud jsou počítané hodnoty husté, druhá je spíše pro řídké.

Výhoda tabelace 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 přímočaře použijeme pole P[] velikosti N, kdežto při ručním návrhu stačí pamatovat si poslední dvě čísla. Speciálně, některé úlohy dynamického programování dovolují reformulaci algoritmu šetřící paměť.

Tabelace nemá smysl, pokud se počítají v rekurzi různé hodnoty, například při obvyklém výpočtu FFT dělíme vstupní vektor na dva různé vektory poloviční délky, kterých výsledky si explicitně pamatujeme.

Odstraňování rekurze[editovat | editovat zdroj]

Odlišení rekurzivního popisu a vhodné implementace

Rekurze dovoluje stručný zápis. To je i tím, že některé věci se berou implicitně, konvencí, a tudíž se nemusí explicitně vypisovat. Ale protože jsou následně řízeny softwarem, tak nad nimi programátor nemá plnou kontrolu a jsou realizovány obecně a tudíž neefektivně pro danou konkrétní úlohu.

Stručný zápis je vhodný pro úvodní seznámení s algoritmem či jeho hlavní myšlenkou, pokud teda čtenář už ví, co to je rekurze a nečiní mu problémy. Tento stručný zápis bez mnoha technických detailů nemusí být vhodný pro přímočarou implementaci. Následně se algoritmus vhodně implementuje, což může znamenat i opuštění rekurzivního popisu, návrh nových datových struktur (vlastního zásobníku či pole pro dynamické programování) a jejich vhodnou obsluhu. Vhodná implementace pak funguje dostatečně dobře a případně se to dá i zdůvodnit. Například quicksort dovoluje taková implementační rozhodnutí.

Související problémy
  1. Speciální přístupy jsou tabelace, koncová rekurze a návrhový vzor trampolína (trampolínový styl), zahrnujíc i dynamické programování.
  2. Fibonacciho čísla i při naivní zápisu algoritmu s exponenciální složitostí potřebují pouze lineární počet položek na zásobníku. Položky jsou sice velikostí závislé na vstupu, ale úměrně výsledku, takže ta paměť se musí stejně alokovat.
  3. Rekurze implementovaná obecně uchovává na zásobníku případně systémové informace kromě vlastních (lokálních) proměnných algoritmu. Spotřeba paměti je větší než při ručním uchovávání pouze potřebných informací.

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 obvykle součástí rekurze a její nesprávná formulace někdy vede na nekonečný cyklus (či cyklus nekonečný) a tím obvykle 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]