TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Možná někoho z vás napadne, zdali je možné, aby podprogram volal sám sebe. Odpověď je ano, je to možné. A takovému volání se říká rekurzivní volání. Rekurze je trochu kontroverzní téma. Někdo na ni nedá dopustit, někdo se ji vyhýbá jako čert kříži.
Podprogramy, jak již bylo řečeno, je možné volat jak z hlavního programu, tak i z podprogramů a říkáme tomu rekurzivní volání. Rekurzi si je možné představit i "v reálu". Pokud máte kameru, tak ji připojte k TV a nechte na ni zobrazovat to, co kamera snímá. Následně kamerou zaberte obrazovku TV, výsledkem je rekurze.
Rekurze je trochu kontroverzní téma. Někdo na ni nedá dopustit, někdo se ji vyhýbá jako čert kříži. Problém rekurze je v tom, že je to mocný nástroj, který se snadno může stát noční můrou programátora. Obecně se doporučuje rekurzi se vyhnnout, vždy se dá zapsat algoritmus tak, že nepoužijeme rekurzi, i když se nabízí. Řešení ovšem nebývá tak elegantní.
A proč se rekurze nedoporučuje? Máte podprogram z něhož voláme opět tento podprogram - to je princip rekurze. Pokud bychom měli volání jen tak, bez nějakého dalšího omezení, tak dostáváme nekonečný program. První důležitá věc, která musí být při použití rekurze jasně definována, je podmínka pro zastavení. Jak již bylo řečeno, pokud tato podmínka chybí nebo je "jenom" nepřesná nebo neúplná, tak dostaneme v lepší případě vždy nekonečný program, v horším případě jenom někdy (což se hledá a odstraňuje o poznání hůře).
Druhou věc, která je u rekurze velmi problematická, je spotřeba zdrojů poskytovaných počítačem. Až si ukážeme datové typy, tak uvidíte, že každá proměnná zabírá v paměti místo. Rekurzivní volání vlastně vytváří nové a nové instance podprogramu, s ní vytváří i nové instance jeho proměnných a postupně zaplňuje paměť. A stejně tak je někde potřeba mít zaznamenáno, jak se podprogramy volaly. To se opět ukládá do paměti, která samozřejmě není neomezená. V případě nevhodného použití lze tuto paměť vyčerpat a výsledný program se opět stává nestabilní.
Fibonacciho posloupnost (rekurzivní řešení)
Rekurzi si ukážeme na jednoduchém příkladu - Fibonacciho posloupnosti. Tato posloupnost je definována jako funkce F(n), pro kterou platí, že pro n=0 je výsledek 0, pro n=1 je výsledek 1 a pro n > 1 je výsledek F(n-1) + F(n-2), nebo-li součet předchozích 2 členů.
Zadáním by tedy bylo vytvoření algoritmu pro výpočet Fibonacciho posloupnosti. Na vstupu od uživatele bude číslo N, pro které se má spočítat F(N). Na výstupu bude výsledné číslo z Fibonacciho posloupnosti.
Jelikož je posloupnost zadána rekurzivně (F(n) = F(n-2) + F(n-1)), tak řešení pomocí rekurze se nabízí. Hlavní program bude opět jednoduchý - zadání čísla uživatelem, zavolání podprogramu na výpočet a vypsání výsledku. Výsledek si můžete prohlédnout na obrázku.
Tělo podprogramu je dáno definicí posloupnosti. Pokud je N = 0, tak je výsledek 0 - což bude první podmínka. Druhá podmínka bude na hodnotu N = 1, v tomto případě je výsledek 1. Pro vyšší hodnoty než je 1 je výsledek součtem předchozích 2 hodnot, nebo-li zavoláme výpočet podprogramu znovu pro předchozí 2 hodnoty.
Elegantně jsme přenesli definici posloupnosti do vývojového diagramu. Výsledek, který si můžete prohlédnout na obrázku, je jednoduše čitelný, přehledný a přesně odpovídá definici. Tak proč tedy rekurzi zatracovat? Vývojový diagram je sice pěkný, co se týká je délky a přehlednosti, ale jeho činnost už tak příznivá není. Celé si to demonstrujeme na výpisu průchodu pro zadané N.
Průchod kódem si znázorníme v textovém podání. Každé odsazení je po volání podprogramu. Ukázku provedeme pro N=5
Začátek
N <- 5
F(5)
X=5
A=0
X není 0
A=1
X není 1
B=F(4)
X=4
A=0
X není 0
A=1
X není 1
B=F(3)
X=3
A=0
X není 0
A=1
X není 1
B=F(2)
X=2
A=0
X není 0
A=1
X není 1
B=F(1)
X=1
A=0
X není 0
A=1
X je 1
Návrat(1)
B=1
C=F(0)
X=1
A=0
X je 0
Návrat(0)
C=0
A=1+0=1
Návrat(1)
B=1
C=F(1)
X=1
A=0
X není 0
A=1
X je 1
Návrat(1)
C=1
A=1+1=2
Návrat(2)
B=2
C=F(2)
X=2
A=0
X není 0
A=1
X není 1
B=F(1)
X=1
A=0
X není 0
A=1
X je 1
Návrat(1)
B=1
C=F(0)
X=1
A=0
X je 0
Návrat(0)
C=0
A=1+0=1
Návrat(1)
C=1
A=2+1=3
Návrat(3)
B=3
C=F(3)
X=3
A=0
X není 0
A=1
X není 1
B=F(2)
X=2
A=0
X není 0
A=1
X není 1
B=F(1)
X=1
A=0
X není 0
A=1
X je 1
Návrat(1)
B=1
C=F(0)
X=1
A=0
X je 0
Návrat(0)
C=0
A=1+0=1
Návrat(1)
B=1
C=F(1)
X=1
A=0
X není 0
A=1
X je 1
Návrat(1)
C=1
A=1+1=2
Návrat(2)
C=2
A=3+2=5
Návrat(5)
V=5
Vypiš 5
Konec
Z výpisu je patrná slabina použití rekurze. Některé hodnoty (např. F(2)) jsme počítali opakovaně. Zápis algoritmu pomocí rekurze se sice nabízel a je opravdu jednoduchý, ale pro vysoká N by výpočet trval neúměrně dlouho a zbytečně by zatěžoval systémové prostředky počítače. Rekurzi tedy odstraníme resp. vyřešíme úlohu nerekurzivně.
Fibonacciho posloupnost (nerekurzivní řešení)
Při řešení nerekurzivním způsobem využijeme toho, že si můžeme pamatovat předchozí výsledky, a protože se k výpočtu dalšího prvku používají předchozí 2 prvky, tak si budeme pamatovat právě tyto 2 předchozí prvky.
Nejprve ovšem musíme, stejně jako v rekurzivním způsobu řešení, ošetřit výsledné hodnoty pro N=0 a N=1. Program tedy začne 2 podmínkami, ve kterých se bude s těmito hodnotami počítat a může se rovnou přejít k vypsání výsledku.
Nyní můžeme přistoupit k výpočtu dalších členů posloupnosti. Máme zadaný počet (N), do kterého máme posloupnost počítat, takže použijeme cyklus s daným počtem opakování. Pro první 2 hodnoty (0 a 1) jsme udělali na začátku programu podmínky, takže výpočet bude pro hodnoty 2 a vyšší, tj. rozmezí cyklu bude od 2 do N.
Jak již bylo řečeno, další prvek posloupnosti je součtem předchozích dvou. Hodnota F(2) = F(1) + F(0), hodnota F(3) = F(2) + F(1), hodnota F(4) = F(3) + F(2) atd. Z tohoto krátkého zápisu je vidět, že hodnota F(x) je dána součtem řekněme A a B. Pro další prvek posloupnosti F(x+1) se hodnotou B stává předchozí hodnota A a hodnotu A se stává předchozí vypočtená hodnota F(x) - hodnoty se "posouvají". Stejně tak i my je budeme posouvat.
Na začátku budeme mít nějaké F1 a F2, což jsou předchozí 2 hodnoty. Pro další výpočet se musí provést posunutí těchto hodnot, a to tak, že do F2 se přesune hodnota z F1 a do F1 se je přesune naposledy vypočtená hodnota prvku. Zbývá nám pouze určit počáteční hodnoty F1 a F2. Ty jsou dány předpisem Fibbonaciho posloupnosti a jsou 1 resp. 0.
Výsledný vývojový diagram si můžete prohlédnout na obrázku. Výsledek není tak přehledný jako v případě rekurzivního způsobu, ale eliminovali jsme všechny negativní vlastnosti, které rekurzivní způsob řešení sebou nesl. Každý prvek posloupnosti se počítá pouze jednou a nedochází k opakovanému vnořenému volání. Máme pouze 3 pomocné proměnné navíc.
Tímto dílem zakončíme nejenom rekurzi, ale i podprogramy. V dalších dílech budeme podprogramy dále využívat, ale nejprve si projdeme datové typy, abychom se mohli dostat k praktickým úlohám.
