Rekurze je obecně cokoliv, co se samo v sobě opakuje nebo je popsané pomocí sebe samotného. V matematice se setkáváme například s rekurentními posloupnostmi, kdy jsou členy definovány nějakým vztahem oproti ostatním členům. Důležité je, aby rekurze byla konečná: v případě rekurentních posloupností například obvykle dostaneme několik členů s jasně danou hodnotou, tak, abychom mohli odvodit všechny ostatní. Když budeme trpělivě pořád dokola rozepisovat vzoreček pro n-tý člen, dostaneme nakonec vzorec používající jen členy, jejichž hodnotu jsme přímo dostali. Kdyby to tak nebylo, mohli bychom vzoreček rozepisovat do nekonečna a pořád se nedozvíme nic: to je případ nekonečné rekurze.
V programování se rekurzí míní situace, kdy nějaká funkce volá sebe samotnou. Některé úlohy přímo navádějí k tomu, abychom k jejich řešení rekurzi použili, může to výrazně zjednodušit kód. Například lze pomocí rekurze snadno napsat kalkulačku, která umí pracovat se závorkami: když narazí na začátek závorky, najde jí odpovídající konec a sama sebe zavolá na vnitřek. Kdybychom to psali bez rekurze, museli bychom si nějakým chytrým způsobem pamatovat mezivýsledky výpočtů v závorkách a vlastně přímo napodobovat rekurzivní volání.
Snadno se může stát, že bude rekurze nekonečná, pokud si nedáme pozor. Pokud jsou splněny určité podmínky, musí funkce přímo navrátit nějaký výsledek a sama sebe už znovu nevolat. Hloubkou rekurze se myslí právě počet předchozích volání funkce, která byla potřeba, abychom se dostali na jasný výsledek. Nejlepší bude ukázat si příklad.
funkci faktoriál_s_rekurzí(přirozené číslo N) definujeme takto:
pokud N větší než 1:
navrací faktoriál_s_rekurzí(N - 1)
jinak:
navrací 1
Tato funkce volá sama sebe pokaždé s parametrem o 1 menším, takže skončí po nejvýše N voláních; hloubka rekurze je nejvýše N. To může pro hodně vysoká N způsobovat potíže: při každém volání funkce se ukládá stav programu, tedy především poloha ve volajícím kódu, na zásobník (zvaný anglicky call stack), a ten má omezenou velikost. Než jakákoliv funkce skončí, zabírá na zásobníku místo. Pokud je tedy hloubka rekurze větší, než se na zásobník vejde (řádově to budou stovky až tisíce volání), program bez varování sletí.
Program jde vždy nějakým způsobem přepsat tak, aby rekurzivní volání neobsahoval. Někdy to dá práci, ale v tomhle případě se kód spíše zjednoduší:
funkci faktoriál_bez_rekurze(přirozené číslo N) definujeme takto:
číslo výsledek nastaví na 1
cyklus pro číslo i jdoucí od 2 do N:
výsledek přenásobí číslem i
navrací výsledek
Výpočet faktoriálu bez rekurze bude jistě také o něco rychlejší, protože volání funkce vždy znamená nějakou práci navíc. V některých jazycích (zvláště v interpretovaných) to může být dost výrazné.
Fibonacciho posloupnost se občas definuje různě; pro nás je Fib1=Fib2=1 a dále FibN+2=FibN+FibN+1
Tenhle úkol určitě není dobré řešit rekurzí přímo. Naopak, následující algoritmus by byl ukázkově chybný:
funkci člen_fibonacciho_posloupnosti(přirozené číslo N) definujeme takto:
pokud je N větší než 2:
navrací člen_fibonacciho_posloupnosti(N-1) + člen_fibonacciho_posloupnosti(N-2)
jinak:
navrací 1
Problému si všimneme snadno, když si nakreslíme strom volání. Funkce pro každé N větší než 2 sama sebe zavolá dvakrát a hodnotu některých předchozích členů kvůli tomu počítáme znovu a znovu několikrát. Tím, že jsou volání rekurzivní, tento počet roste nesmírně rychle: pro výpočet N-tého členu potřebujeme víc než 2N-2 volání funkce. To je z paměťového i časového hlediska neúnosné.
Opravit to jde snadno, pokud si budeme výsledky předchozích výpočtů pamatovat. Když hodnotu nějakého členu počítáme poprvé, uložíme ji na správné místo do nějakého pole a poznamenáme si, že jsem ji už spočítali. Když se pak funkce zavolá pro toto N znovu, rovnou přečte výsledek z pole a už nic nepočítá. Při troše péče můžeme také funkci přepsat tak, aby vůbec rekurzi neobsahovala.
Problém pak může být ještě, že potřebujeme pole velikosti N. Když budeme ale členy počítat chytře od nejmenšího, je možné na paměti ušetřit a vystačíme si s polem o dvou prvcích, nezávisle na požadovaném členu posloupnosti.
Tato metoda dosáhla největší slávy ve vojenství, ale zasahuje do mnoha jiných oborů lidského konání. V informatice to označuje přístup k řešení úlohy, když problém nějakým způsobem rozdělíme na několik problémů menších (nejčastěji na poloviny) a ty vyřešíme rekurzivně. Samozřejmě opět musíme být schopni pro dostatečně malé problémy řešení spočítat přímo, aby rekurze byla konečná, a musíme nakonec umět sloučit řešení menších problémů tak, abychom získali řešení celku. V mnoha případech tímto přístupem získáme rychlejší algoritmus, než bychom na první pohled čekali.
V rámci otázky 17 si ukážeme dva chytré třídící algoritmy založené tomto přístupu. Posloupnost N čísel setřídíme tak, že ji nějak rozdělíme na poloviny a ty setřídíme stejným způsobem. V tomhle případě rekurze končí ve chvíli, když dostaneme jediné číslo: to není oproti čemu třídit, takže jsme hotovi. Pochopitelně je potřeba pokaždé ještě provést několik kroků navíc, aby program vůbec něco dělal.
Dynamické programování má s rekurzí obecně pramálo společného. Často je to naopak přístup ze zcela opačné strany; zmiňme se o něm jen okrajově.
Je založené také na řešení pomocí menšího podproblému. Tentokrát ale nedělíme vstup na rovnoměrné části, ale přidáváme vždy jeden kousek vstupu po druhém. Musíme tedy umět rozšířit řešení, pokud je vstup o malý kousek větší. S trochou nadsázky můžeme za dynamické programování označit způsob, jakým jsme počítali faktoriál: faktoriál vždy rozšiřujeme pro vyšší a vyšší N, až dojdeme ke kýženému výsledku.