ALG3

6,6. Klasyczne schematy derekursywacji 183

(

A<x) i PO ; D(x) i }

also

C(X) ;

I

Zakładając AAkrotne wywołanie procedury P. jej działanie można poglądowo przedstawić jako sekwencję instrukcji:

_N_ _N_

A x);... zł(-v); (’(.v); B(.v):... B{x):

Jest to taka forma zapisu algorytmu, która od razu sugeruje możliwe zapisanie w formie iteracyjnej... pod warunkiem wszakże znajomości N. Niestety, ilość wywołań procedury P nie jest nigdy znana a priori - wszystko zależy od globalnego „parametru’", z którym zostanie ona wywołana!

Nie popadajmy jednak w przedwczesną depresję i spójrzmy na następującą wersję procedury P:

int N-0; void p{)

t

i£ malunek,*)

(

A(x) ;

N++;P(J;N—;

B(x) ;

}

alse

C (X) ;

)

Załóżmy, że wykonanie tego programu zostało przerwane w pewnym losowo wybranym momencie i za pomocą debuggera odczytaliśmy wartość N. Biorąc pod uwagę, iż - jak to wynika z treści programu - zmienna globalna A'jest inkrementowana podczas każdego wywołania rekurencyjnego P i dekrementowana po powrocie z niego, możemy wykorzystać tę zmienną do odczytywania aktualnego poziomu rekurencji procedury P '.

Idea kolejnej transformacji procedury /•'jest teraz następująca: wywołanie re-kurencyjne procedury P będziemy symulować przy pomocy skoku do jej początku. Podczas kolejnego wykonania procedury P możemy w bardzo łatwy sposób

I3

Patrz §2.3.