Obsah
Rekurze
Rekurze je v informatice mocným nástrojem pro řešení problémů, které mají hierarchickou nebo sebepodobnou strukturu. Aby rekurze neskončila nekonečným cyklem, musí mít vždy jasně definovanou ukončovací podmínku.
1. Dvě základní části rekurze
Každá správně napsaná rekurzivní funkce musí obsahovat:
1. **Základní případ (Base Case):** Podmínka, při které rekurze končí a vrací konkrétní výsledek. Bez ní by program běžel "do nekonečna" (resp. do pádu aplikace). 2. **Rekurzivní krok:** Část, kde funkce volá samu sebe s mírně pozměněnými (obvykle menšími) parametry, čímž se přibližuje k základnímu případu.
2. Klasický příklad: Faktoriál
Faktoriál čísla $n$ (značeno $n!$) je součin všech čísel od 1 do $n$. Matematicky lze říci, že $5! = 5 \times 4!$. Tím jsme definovali faktoriál pomocí faktoriálu (rekurze).
Pseudokód:
funkce faktorial(n):
pokud n == 0: // Základní případ
vrat 1
jinak: // Rekurzivní krok
vrat n * faktorial(n - 1)
3. Rekurze v datových strukturách
Rekurze je nejpřirozenějším způsobem, jak procházet složité struktury:
- Složky v počítači: Složka obsahuje soubory a další složky. Funkce pro hledání souboru prohledá složku, a pokud najde podsložku, zavolá samu sebe na tuto podsložku.
- Stromy (Trees): Algoritmy jako DFS využívají rekurzi k procházení větví grafu.
- HTML/XML: Prohlížeče používají rekurzi k vykreslení prvků, které jsou vnořené do jiných prvků.
4. Rizika: Stack Overflow
Každé volání funkce spotřebovává místo v paměti zvané Stack (zásobník). Pokud je rekurze příliš hluboká (tisíce volání), paměť se zaplní a dojde k chybě Stack Overflow (přetečení zásobníku).
| Vlastnost | Iterace (Cyklus) | Rekurze |
|---|---|---|
| Stav | Uložen v proměnných. | Uložen v parametrech na zásobníku. |
| Rychlost | Rychlejší (menší režie). | Pomalejší (režie volání funkcí). |
| Čitelnost | Horší u složitých struktur. | Často mnohem elegantnější a kratší kód. |
5. Ocasní rekurze (Tail Recursion)
Některé moderní programovací jazyky (např. Scala, Haskell, ale i některé verze JavaScriptu) umí rekurzi optimalizovat. Pokud je rekurzivní volání úplně poslední operací ve funkci, překladač ji převede na běžný cyklus, takže nespotřebovává místo na zásobníku a je stejně rychlá jako iterace.
Zajímavost: Existují tzv. rekurzivní zkratky. Například název projektu GNU znamená „GNU's Not Unix“, nebo PHP dříve znamenalo „PHP: Hypertext Preprocessor“. Samy sebe definují pomocí sebe sama.