29
4 Rekurze
4 Rekurze
Co je rekurze
Rekurzivní algoritmus
– Odkazuje přímo nebo nepřímo na sebe
Rekurzivní datová struktura
– obsahuje odkazy na datové struktury stejného
druhu
Seznam, strom
Rekurzivní podprogram
– Naprogramování rekurzivního algoritmu
Příklad
Rekurzivní zpracování binárního stromu
(přímé)
1. Je-li strom prázdný, skončíme
2. Jinak zpracujeme údaj v kořeni
3. Zpracujeme tímto algoritmem levý podstrom
4. Zpracujeme tímto algoritmem pravý
podstrom
Rekurze
Obecný tvar rekurzivního algoritmu P
P ≡ C[Si, P]
– C označuje kompozici (složení) algoritmů
– Si jsou jiné algoritmy neobsahující odkaz na P
Požadavek: konečnost rekurze
– Použití odkazu na P musí být vázáno na
splnění určité podmínky B:P ≡ C[Si, if(B) P]
P ≡ C[Sn, if(n > 0) P]
Rekurze v programu
Přímá: f() volá f()
Nepřímá: f() volá g1(), g1() volá g2(), … gn() volá f()
Připomeňme si:
– Každé volání znamená vytvoření rámce zásobníku
– Návrat z funkce znamená zrušení rámce zásobníku
– Možnost vyčerpání paměti při příliš hluboké rekurzi
Příklad: faktoriál
Rekurzivní definice
Rekurzivní implementace
Kdy se rekurzi vyhnout
Rekurzivní algoritmus tvaruP ≡ [S, if(B) P]kde závorky [ ] předepisují nejprve provést S, pak – je-li splněna podmínka B – provést P
Lze nahradit iterativním algoritmem P ≡ [S, while(B) S]
Rekurze zde neznamená zásadní neefektivitu
Kdy se rekurzi vyhnout
Obecně u rekurzivních vztahů tvaru
xn = f(xn-1, … xn-k)
pro k > 1
Vedou k exponenciální složitosti
– Ukážeme na příkladě
Fibonacciova čísla
f0 = 0, f1 = 1, fn = fn-1 + fn-2 pro n > 1
Implementace:
Fibonacciova čísla
Složitost:
Odtud
Protože t1 = t2 = 1, dostaneme, že tn roste
rychleji než 2n/2
Exponenciální složitost!!!
Fibonacciova čísla
Strom volání pro Fibonacci(5)
Fibonacciova čísla
Nerekurzivní implementace: O(n)
Příklady podobných vztahů
Besselovy funkce
Kombinační čísla
Odstraňování rekurze
Algoritmus pro náhradu rekurzivního kódu
nerekurzivním
– Nezmění složitost
– Vede k nepěknému kódu (používá skoky)
– Využívá vlastní zásobník
– Základ pro další úpravy
Odstraňování rekurze
Pro určitost:
– void f(int a, int b, int c);
– Volání: f(3,4,5);
Opakování – co se při volání stane:
– Do zásobníku se uloží skutečné parametry
– Do zásobníku se uloží návratová adresa
– Skočí se na začátek těla funkce
– Vytvoří se v zásobníku lokální proměnné
Odstraňování rekurze
Opakování – co se stane při návratu
– Odstraní se ze zásobníku lokální proměnné
– Odstraní se ze zásobníku skutečné parametry
– Vyjme se ze zásobníku návratová adresa a
skočí se na ni
Problém:
– Nemáme přímý přístup k zásobníku
– Nemáme přímý přístup k adresám míst v kódu
Odstraňování rekurze
Řešení:
– Použijeme vlastní zásobník
– Použijeme návěští a skoky
– Nebudeme vytvářet nové parametry a
proměnné, ale uložíme hodnoty stávajících
Odstraňování rekurze
Postup:
– Na počátku zdrojového kódu
– Pro každé rekurzivní volání
Odstraňování rekurze
– Na konci těla funkce:
Odstraňování rekurze
Příklad:
Příklad: výpočet faktoriálu
Úpravy algoritmu:
– Návratovou hodnot budeme ukládat do
pomocné proměnné
– Není třeba ukládat „návratovou adresu“
(rekurzivní volání na jediném místě)
Odstraňování rekurze
Příklad:
Ackermannova funkce
Funkce , kde N0 = N ∪ {0}
Některé hodnoty
Ackermannova funkce
Lze dokázat, že nejen hodnotu, ale i
výpočetní složitost nelze omezit
strukturovaným algoritmem, který by
obsahoval konečné množství cyklů for a
žádné cykly while nebo do-while
Počet volání A(m, n) – fn ~ 4n
Nerekurzivní výpočet
Ackermannovy funkce
Pole S … zásobník, k … index vrcholu
Nerekurzivní výpočet
Ackermannovy funkcePříklad: A(1, 1)
Krok … odkaz na číslo kroku algoritmu
Krok zásobník k
1 1 1 1
5 0 1 0 2
4 0 0 1 2
3 0 2 1
3 3 0
6 Konec – výsledek je 3
Syntaktická analýza
Definice programovacího jazyka přirozeně rekurzivní
Terminální symbol lze opsat do programu
Neterminální symbol musí být dále definován pomocí terminálních symbolů
Jednou z běžných metod překladu tzv. rekurzivní sestup
Definice jazyka obvykle začíná definicí programu, ten je definován neterminálními symboly nižší úrovně atd.
Příklad: aritmetické výrazy
Příklady – zdrojové kódy
Příklady ke stažení ke skriptu Základy
algoritmizace v C++
https://people.fjfi.cvut.cz/viriumir/, odkaz
ZALG (C++) vpravo dole
– Rekurzivní a nerekurzivní výpočet
Ackermannovy funkce: adresář
Programy\04\Ackermann
– Kalkulačka: adresář Programy\04, soubor
Kalkul.cpp
