ALG8

178

Rozdział 6. Derekursywacja

6.!

Dużą wadą nowej techniki będzie niemożność łatwego jej sformalizowania. Z praktycznego punktu widzenia sprawa polega na tym, iż nie jest możliwe podanie prostego przepisu, który mógłby być w miarę automatycznie⁸ zastosowany. Będziemy musieli zatrudnić naszą wyobraźnię i intuicję-a czasami nawet pogodzić się z niemożnością znalezienia rozwiązania. Przejdźmy jednak do szczegółów.

Przypomnijmy raz jeszcze ogólną postać procedury rekurencyjnej:

void PI(param_wywoi)

I

param_wywcl-F(param_wywol)i PI (parair. wywol);

Wiemy, że wywołanie Pfparam wywal) modyfikuje (lub może zmodyfikować) zmloc i param \rywoL Poprzednio, aby się od tego uchronić, wykorzystaliśmy zachowawcze własności stosu.

Pomysł polega na tym, aby uzupełnić procedurę PI o pewne instrukcje, które wiedząc, jak wywołanie PI (param wywal) modyfikuje zmloc i param wywol wykonałyby czynność odwrotną, tak aby przywrócić ich wartości sprzed wywołania! Inaczej mówiąc, chodzi nam o doprowadzenie programu cło postaci:

void ?2 ()

(

(1)

paran\_wywol-F(param_wywol) ;

P2;

FUNKCJA_ODWROTNA(zm_loc,pa ram_wywol};

(2)

)

Działanie owej tajemniczej funkcji odwrotnej musi być takie, aby wartości zm tac i param wywol były dokładnie takie same w punktach programu oznaczonych (I) i (2). Jak to zrobić? Ba! oto jest dopiero pytanie! Odpowiedź na nic będzie inna w przypadku każdego programu i nie pozostaje nam nic innego, jak tylko pokazać jakiś konkretny przykład.

Poniższa procedura PI liczy elementy wymyślonego ad hac ciągu matematycznego:

odwrotna.cpp

void Pltint a, ints fc)

t

if(a==0!

Co nie znaczy, że bezmyślnie!