ALG5

3.4. Derekursywacja z wykorzystaniem stosu 175

Metoda ta jest podzielona na dwa etapy: l zamianę zmiennych lokalnych na globalne;

2. transformację programu rekurencyjnego pozbawionego zmiennych lokalnych na postać iteracyjną.

W kolejnych paragrafach szczegółowo omówimy te dwa posunięcia.

6.4.1 .Eliminacja zmiennych lokalnych

Zanim w ogóle zaczniemy coś eliminować, warto upewnić się, czy zdajemy sobie sprawę, co będzie przedmiotem naszych zabiegów. Zmienne lokalne pełnią w języku strukturalnym rolę szczególną: umożliwiają czytelne formułowanie algorytmów i pozbaw iają tak dobrze znanego programującym w daw nym BASICu strachu przed modyfikacją jakiejś ważnej „gdzie indziej” zmiennej. Mając to na uwadze. dziwną wydawać by się mogła propozycja powrotu do tych prehistorycznych czasów, w których nie było procedur, zmiennych lokalnych, przesłaniania nazw etc. Na szczęście nikt czegoś takiego nie ma zamiaru proponować! Omawiana metoda nie jest bow iem w żadnym razie metodą programowania, lecz zwykłą techniką optymalizacyjną - a jest to istotna różnica. Wróćmy zatem do zmiennych lokalnych i zdefiniujmy sobie, co to takiego.

zmienną lokalną pewnej procedury P będziemy zwali taką zmienną, która może być modyfikowana tylko przez tę procedurę.

zmienną globalną - z punktu widzenia procedury P będzie taka zmienna, która może być zmodyfikowana na zewnątrz tej procedury.

W C++ każda zmienna zadeklarowana wewnątrz bloku ograniczonego nawiasami klamrowymi { i } jest uważana za lokalną dla tego bloku! Tak więc w poniższej procedurze mamy do czynienia z dwiema różnymi zmiennymi lokalnymi vur loc i jedną zmienną globalną var_glob:

int var_glob; void T()

I

int var_loc;

while(jakiś_warunek;

(

int var_loc;

)

)

Wiedząc już dokładnie z czym mamy do czynienia, możemy zobaczyć, w jaki sposób przekształcić rekurencyjną procedurę zawierającą zmienne lokalne