ALG8

168 Rozdział 6. Derekursywacjł

Jak odróżnić powrót z procedury P, który powoduje definitywne jej zakończenie, od tego, który przekazuje kontrolę do Instr2? Okazuje się, że jedyny łatwy do zautomatyzowania sposób polega na użyciu tzw. stosu wywołań rekurencyj-nych (patrz również §5.3).

Zarządzanie powrotami z wywołań rekurencyjnych wymaga uprzedniego zapamiętywania dwóch informacji: tzw. otoczenia (np. wartości zmiennych lokalnych) i adresu powrotu, dobrze nam znanego z poprzedniego przykładu. Podczas wywołania rekurencyjnego następuje zapamiętanie na stosie tych informacji i kontrola jest oddawana procedurze. Jeśli wewnątrz niej nastąpi jeszcze raz wywołanie rekurencyjne. to na stos zostaną odłożone kolejne wartości otoczenia i adresu powrotu - różniące się od poprzednich. Podczas powrotu z procedury rekurencyjnej możliwe jest odtworzenie stanu zmiennych otoczenia sprzed wywołania poprzez zwykłe zdjęcie ich ze stosu.

Kompilator „wie”, gdzie ma nastąpić powrót, bowiem adres (argument instrukcji goło') także został zapamiętany na stosie. Testując stan stosu możliwe jest określenie momentu zakończenia procedury: jeśli stos jest pusty, to wszystkie wywołania rekurencyjne już „się” wykonały.

Oto jak możliwe byłoby zrealizowanie w formie sekwencyjnej poprzedniego przykładu:

start:

procedura -i wywołania rekurencyjne

powroty z wywołań rekurencyjnych

ASM(Instr1) push(Otoczenie, etl) x=F(x) goto start etl:

ASM{InstrŻ) if_not(StosPusty)

pop(Otoczenie, Addr) Odtwórz(Otoczenie) goto Addr

)

)

To tyle tytułem wstępu. W dalszej części rozdziału przystąpimy już do kilku prób tłumaczenia algorytmów rekurencyjnych na iteracyjne.

⁴ Warto przypomnieć, że instrukcja goto istnieje również w C++.