Rekurzivní algoritmy

Note	Metoda rozděl a panuj, výhody a nevýhody použití rekurze, odstranění rekurze. Vysvětlení principů a implementace řadících rekurzivních algoritmů. Vztah rekurze a matematické indukce. IB002, IB015

Rekurze nastává, když funkce přímo, či nepřímo ("ob jiné funkce") volá sama sebe. To samé se dá aplikovat i na struktury, které obsahují samy sebe (skrze pointer nebo ekvivalent).

Výhody rekurze

V některých případech čistší a elegantnější kód.
Důkazy korektnosti využívají známé metody matematické indukce.
Složitost lze zapsat pomocí rekurentní rovnice.

Nevýhody rekurze

Když si člověk nedá pozor, přeteče mu zásobník, což se špatně ladí.
Volání funkce má vyšší režii (časovou i paměťovou) než vlastní správa zásobníku.
Mentálně náročnější než for cyklus.

Odstranění rekurze

Každý rekurzivní algoritmus lze převést na iterativní. Pokud je rekurze koncová (tail), lze ji nahradit for cyklem. Není-li koncová, je potřeba použít zásobník.

Rozděl a panuj

Přístup dělení na problému na menší, ale podobné podproblémy. Kombinací řešení podproblémů získáme řešení celkové. Tento přístup se často implementuje pomocí rekurze.

Rekurzivní řadící algoritmy

Mergesort

Složitost: $Θ (n lo g (n))$ .

Rozděl posloupnost na poloviny. ( $Θ (n)$ )
Rekurzivně seřaď obě poloviny. ( $2 \cdot T (n /2)$ )
,,Slij'' obě seřazené posloupnosti do jedné. ( $Θ (n)$ )

Quicksort

Složitost: průměrně $Θ (n lo g (n))$ ; $Θ (n^{2})$ , pokud už posloupnost seřazená je.

Vyber pivota.
Rozděl posloupnost na dvě časti: menší než pivot a větší než pivot.
Rekurzivně seřad obě části.
Zkombinuj obě části. (Reálně nedělá nic, protože už jsou ve stejném poli.)

Korektnost rekurzivních algoritmů

Používá se matematická indukce. Rekurze a matematická indukce jsou si podobné. Jen jdou opačným směrem. Matematická indukce začíná u dna a jde do nekonečna, zatímco rekurze začíná na nějaké $n$ -té úrovni a klesá na dno.

Konečnost výpočtu plyne z faktu, že podproblémy se zmenšují.

Správnost výsledku (u řadících algoritmů) dokážeme indukcí vzhledem k délce vstupu:

Báze — třeba, že minimum z posloupnosti délky jedna je onen jediný prvek.
Předpoklad — algoritmus vrací korektní výsledek pro všechny kratší vstupy délky $n$ .
Krok — důkaz tvrzení, že algoritmus vrací správný výsledek i pro vstupy délky $n + 1$ .

Složitost rekurzivních algoritmů

Složitost zapisujeme pomocí rekurentní rovnice, např.:

T (n) = ⎩ ⎨ ⎧ 0 + T (⌊ \frac{n}{2} ⌋) + T (⌈ \frac{n}{2} ⌉) + 2 10 pro n > 2, pro n = 2, pro n = 1.

A nebo obecně:

T (n) = {Θ (1) \sum_{i = 1}^{k} T (n_{i}) + D (n) + C (n) pro n \leq c, jinak .

kde $D (n)$ je složitost konstrukce podproblémů o velikostech $n_{i}$ a $C (n)$ je složitost kombinace výsledků.

Chceme ale explicitní vyjádření funkce $T (n)$ , které můžeme získat několika způsoby:

Substituční metoda: ,,uhodneme'' řešení a ověříme pomocí matematické indukce.
Metoda rekurzivního stromu: zkonstruujeme strom, jehož vrcholy vyjadřují složitost jednotlivých rekurzivních volání. Výsledná složitost je pak suma ohodnocení vrcholů stromu, kterou pak použijeme jako odhad pro substituční metodu.
Kuchařková věta (master method): Pokud $T (n)$ má tvar $T (n) = a \cdot T (n / b) + f (n)$ , kde $a \geq 1, b > 1$ a $f (n)$ je polynomiální funkce, pak platí:

$T (n) = ⎩ ⎨ ⎧ Θ (f (n)) Θ (n^{l o g_{b} a}) Θ (f (n) \cdot lo g_{b} n) kdy \overset{z}{ˇ} a \cdot f (n / b) = c \cdot f (n) pro konstantu c < 1, kdy \overset{z}{ˇ} a \cdot f (n / b) = d \cdot f (n) pro konstantu d > 1, kdy \overset{z}{ˇ} a \cdot f (n / b) = f (n) .$