ALG7

6.5. Metoda funkcji przeciwnych 177

Dokonaliśmy zatem tego, co było naszym celem: pozbawiliśmy procedurę P wszelkich parametrów lokalnych, a pomimo to jej funkcjonowanie - jak również funkcjonowanie całego programu - nie uległo zmianie. Musimy jednak pamiętać o tym, by prawidłowo zainicjować globalne już zmienne zm loc i parctm wywol właściwymi wartościami¹, tak aby zachować pełną równoważność funkcjonalną naszego programu - przed i po przeróbce. Analizując jeszcze naszą metodę warto wspomnieć o nasuwającej się od razu optymalizacji. Na stosie musimy zachowywać tylko te wartości zmiennych lokalnych, które są potrzebne. W szczególności absolutnie nie ma potrzeby chować na stos tych zmiennych lokalnych, które nie są już używane po wywołaniu rekurencyjnym.

Dla ilustracji opisanego powyżej procesu przeanalizujmy raz jeszcze nasz klasyczny przykład wież Hanoi (patrz str. 170). Proste przekształcenia algorytmu prowadzą do następującej wersji:

void hanoi3()

(

while (n!=l)

(

push(n); push(a); push(b); n=n-l; b=3-a-b; hanoi3();

pop(b); pop(a); pop(n);

cout « "Przesuń dysk nr "<< n << " z " « a « " na "« b <<endl; n=n-l; a-3-ab;

I

cout << "Przesuń dysk nr 1 z " « a << " na "

<< b «endl;

I

6.5. Metoda funkcji przeciwnych

Użycie stosu - wywołań typu push i pop - jest kosztowne zarówno ze względu na czas potrzebny na obsługę tej struktury danych, jak i na pamięć niezbędną na rezerwację dostatecznie dużego stosu. Jak dużego? Problemem jest to. że nie wiemy tego a priori, co zmusza nas do założenia najgorszego przypadku. Z tego też powodu wszelkie ewentualne metody pozwalające nie korzystać ze stosu powinny być przez nas powitane jak najprzychylniej, faka metoda zostanie przedstawiona już za moment.

1

Przed pierwszym wywołaniem procedury P