Ruská panenka matrjoška má v sobě menší panenku, ta zase menší a tak dál, až v nejmenší už nic není. Chceš spočítat, kolik panenek je celkem? Otevřeš jednu, řekneš „jedna plus tolik, kolik je v té menší“ a s menší uděláš totéž. U nejmenší skončíš.
Tomuhle způsobu řešení se říká rekurze. Úlohu vyřešíš tak, že ji převedeš na stejnou, ale menší úlohu. Rekurzivně se prochází složky na disku, stromy rodokmenů nebo se třídí velké seznamy.
return n * faktorial(n - 1)0! = 1.5! = 5 · 4 · 3 · 2 · 1 = 120def faktorial(n): if n <= 1: return 1 return n * faktorial(n - 1)Všimni si, že 5! = 5 · 4!, 4! = 4 · 3! a tak dál. Funkce přesně tohle zapisuje. Řádek s if je základní případ, poslední řádek rekurzivní případ.
faktorial(4) čeká na faktorial(3).faktorial(3) čeká na faktorial(2).faktorial(2) čeká na faktorial(1).faktorial(1) je základní případ a vrátí 1.2 · 1 = 2, 3 · 2 = 6, 4 · 6 = 24.if n == 0: return 0. Rekurzivní: return n + soucet(n - 1). soucet(4) = 4 + 3 + 2 + 1 + 0 = 10.len().def delka(s): → if s == "": return 0 → return 1 + delka(s[1:]). Každé volání „uloupne“ první znak. Pro „ahoj“: 1 + 1 + 1 + 1 + 0 = 4.def faktorial(n): return n * faktorial(n - 1)if n <= 1: return 1.Bez základního případu se funkce volá pořád dál (1, 0, −1, …). Python po zhruba 1000 zanořeních skončí chybou RecursionError.
Vaříš a uprostřed receptu zjistíš, že musíš udělat omáčku. Odložíš rozdělaný recept a začneš omáčku. V ní zjistíš, že potřebuješ vývar. Odložíš i omáčku. Až je vývar hotový, vrátíš se k omáčce a pak k původnímu receptu. Rozdělané úlohy máš na sobě jako hromádku talířů.
Počítač si rozdělaná volání funkcí pamatuje úplně stejně. Když tomu porozumíš, pochopíš, proč rekurze funguje, kdy je pomalá a proč může spadnout.
def soucet(n): return 0 if n == 0 else n + soucet(n - 1)RecursionError.Rekurze bez základního případu.for, while) místo rekurze. Každou rekurzi lze přepsat na cyklus.Faktoriál cyklem: v = 1, for i in range(2, n + 1): v = v * i.Záleží na tom, jestli funkce něco udělá před, nebo po rekurzivním volání.
| Funkce | Tělo | Výstup pro n = 3 |
|---|---|---|
dolu(n) | if n == 0: return → print(n) → dolu(n - 1) | 3 2 1 |
nahoru(n) | if n == 0: return → nahoru(n - 1) → print(n) | 1 2 3 |
U nahoru se print provede až při návratu. Nejdřív se dojde až na dno zásobníku (n = 0) a vypisuje se cestou zpět.
Každé číslo je součet dvou předchozích: 0, 1, 1, 2, 3, 5, 8, 13… Rekurzivně: fib(n) = fib(n - 1) + fib(n - 2), základní případy fib(0) = 0, fib(1) = 1.
Graf ukazuje, kolikrát se funkce zavolá. Porovnej fib(10) a fib(20): vstup je jen dvakrát větší, volání je víc než stokrát víc. Stejné hodnoty se počítají pořád znovu.
nsd(a, b) = a, když b == 0, jinak nsd(b, a % b). Kolik je nsd(48, 18)?RecursionError.Každé volání zabere místo na zásobníku a čas. Naivní fib(n) navíc počítá stejné věci mnohokrát.
RecursionError. Každou rekurzi lze přepsat cyklem a naivní rekurze může být velmi pomalá.