V předcházejícím článku jsme viděli, že základem rekurzivního výpočtu je volání programu sebou samým s vhodnými parametry. Zdůrazněme, že jde o obecný princip, bez ohledu na programovací jazyk, v kterém rekurzivní algoritmus zapíšeme. Poznamenejme, že ne každý programovací jazyk musí umožňovat rekurzivní volání programů.
Pro vysvětlení implementace výpočtu rekurzivního algoritmu si nejprve připomeneme základní princip volání podprogramu (procedury, funkce, metody). Tento je obecný bez ohledu na jazyk a jenom pokud jde o terminologii budeme se držet jazyka Java.
Při volání metody z metody main( ) se do zásobníku uloží aktivační záznam obsahující
- parametry
- návratovou adresu, tedy adresu instrukce, kde bude program pokračovat v metodě main( ) po skončení volané metody.
Následuje
- vstup do metody
- její vykonání s použitím parametrů uložených v zásobníku
- návrat do metody main( ) na adresu uloženou v zásobníku s odstraněním aktivačního záznamu
Uvedené schéma vyhovuje nejen pro volání metody v metodě main( ), ale i když tato metoda opět volá nějakou metodu. Do zásobníku se uloží další aktivační záznam s adresou kde budeme pokračovat ve volající metodě a vykoná se volaná metoda. Po jejím vykonání se vrátíme do volající metody na adresu, kterou získáme z vrcholu zásobníku a odstraníme aktivační záznam volané metody. Dále se dokončí volající metoda jak bylo uvedeno. Tímto způsobem lze postupovat až do potenciálního přetečení použitého zásobníku.
Rekurzivní výpočty jsou potom implementovány tak, že metoda buď přímo nebo nepřímo volá sama sebe. Uvažujme přímou rekurzi voláním rekurzivní metody z metody main( ). Potom celý proces můžeme rozložit na následující kroky
volání rekurzivní metody z metody main( )
vstup do metody
nula nebo více rekurzivních volání
dosažení základního případu a následné výstupy z rekurzivních volání až po návrat do metody main( )
Na obr. jsou pro rekurzivní výpočet faktoriálu uvedené kroky vysvětleny pomocí komentářů.
V předcházejícím článku jsme uvedli jak je možné eliminovat koncovou rekurzi. Na příkladu rekurzivního programu pro výpočet faktoriálu si ukážeme jak můžeme jakýkoliv rekurzivní program transformovat na program bez rekurzivních volání využitím vlastního zásobníku.
Vlastní zásobník použijeme pro aktivační záznamy s položkami
par, parametr pro faktoriál
segmentKodu, indikace pokračování výpočtu nabývající hodnoty
navrat, skončení rekurze
nasobeni, počítání faktoriálu při výstupu z rekurzivního volání.
Aktivační záznamy budou objekty třídy AZaznam na obr..
Při vstupu do rekurzivní procedury potřebujeme zjistit hodnotu parametru v aktivačním záznamu, avšak bez odstranění aktivačního záznamu ze zásobníku. Obecně jde o operaci přečti hodnotu na vrcholu zásobníku a obvykle má jméno top. Zásobník aktivačních záznamů potom implementuje třída AZasobnik na obr..
Sledujíc komentáře v programu Faktorial (obr.), můžeme implementaci rekurzivního výpočtu faktoriálu uživatelským zásobníkem vyjádřit diagramem na obr.
. V bloku 1 se do zásobníku uloží aktivační záznam s hodnotou parametru n a adresou pokračování, co je návrat do programu volajícího metodu pro výpočet faktoriálu. V bloku 2 se rozhoduje jde-li o základní případ nebo ne. Nejde-li o základní případ uloží se do zásobníku aktivační záznam s parametre o 1 menším a adresou pokračování, co bude segment násobení, které se vykoná po výpočtu faktoriálu pro tento parametr. Po dosáhnutí základního případu, v bloku 5 zjistíme, kterým segmentem programu, tj. na které adrese, máme pokračovat. Může jít o násobení v bloku 4, kde se na proměnné vysledek postupně vypočítá hodnota faktoriálu nebo v bloku 6 o návrat do volajícího programu s vypočtenou hodnotou n!.
Diagramu z obr. pak přímočaře odpovídá program ZFaktorial na obr.
a
. Základem je metoda pokracuj( ) na obr.
, která obsahuje segmenty programu pro akce v obdélnících na obr.
. Tato metoda je volána z metody faktorial( ) (obr.
), ve které se vytvoří zásobník aktivačních záznamů a nastaví se číslo začátečního segmentu. Metoda pokracuj( ) je volána opakovaně přičemž vykoná akce segmentu. Pokud se požaduje vykonání dalšího segmentu vrátí hodnotu true, jinak vrátí hodnotu false, kdy výpočet faktoriálu skončí. Takto získaný program je možné dále upravit. Hodnota proměnné vysledek a obsah zásobníku při vstupu do jednotlivých segmentů, tj. větví příkazu switch, pro výpočet 0! a 2! jsou na obr.
.
Nyní by jste měli vědět odpovědět na otázku jak skončí náš první návrh programu Pisnicka. Program skončí chybou přetečení systémového zásobníka. Pokud rekurzi jako koncovou odstránime, získáme nekonečný cyklus a program tedy neskončí.