ALG0

180

Rozdział 6. Derekursymijii 6.6,

void main()

(

for (int i=0; i<17;i++) (Pl(i,b); cout « b << "    (

cout << endl;

for (i=C; i<17;i++)

i a-i; P2(); cout << b << "    )

)

Oto co ukaże się na ekranie:

2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 137 2 4 7 11 16 22 29 37 46 56 67 79 92 106 121 137

Wszelkie znaki na ekranie i papierze wskazują, iż procedury PI i P2 są równoważne...

6.6. Klasyczne schematy derekursywacji

Poznane wcześniej metody eliminacji zmiennych lokalnych z procedur, jak również ich „deparametryzacja” służyły jednemu istotnemu celowi: jak największemu zbli- 1 żcniu sposobu wykonywania procedur rekurencyjnych do typowego programu ite- I racyjnego. W istocie, czym jest program określany jako „iteracyjny”? Termin ten I dotyczy zasadniczo systematycznego powtarzania pewnych fragmentów kodu, np. I przy pomocy instrukcji for. while, do... while.. Wywołanie rekurencyjne ma wiele wspólnego z iteracyjnym sposobem wykonywania programów pod względem ide- I owym (chodzi o systematyczne powtarzanie pewnych czynności), bardzo niewiele I jednak ma z nim wspólnego praktycznie. Iteracje są zwykłymi instrukcjami goto¹⁵ I przeplatanymi badaniem warunków. Wywołania rekurencyjne natomiast znajdują [ się co najmniej o poziom" wyżej. Poprzez usunięcie zmiennych lokalnych i para- I metrów' funkcji przybliżyliśmy je bardzo do schematu ileracyjnego.

Procedury rekurencyjne posiadają obowiązkowo pewne testy' służące do sprowa- I dzania procesu wywołań rekurencyjnych do tzw. przypadków elementarnych¹'.

Przykładowo, obliczając rekureneyjnie silnię z n ciągle, badamy czy' n jest równe zeru. Jeśli odpowiedź brzmi tak, procedura zwraca wartość / — w przypadku I zaś przeciwnym następuje kolejne wywołanie rekurencyjne. Są to dwie różne rzeczy-dwa różne fragmenty kodu wykonywane w zależności od spełnienia lub nie pewnych warunków. Iteracje natomiast, generalnie rzecz ujmując,

¹⁰    W rozmaitych wariacjach zależnych od zestawu instrukcji procesora.

¹¹    Abstrakcji, skomplikowania...

¹²    Jest to wymuszone naturalną chęcią zakończenia kiedyś szeregu wywołań rekurencyjnych!