ALG0

170

Rozdział 6. Oerekursywaci

6.3.

Uwaga: Wywołanie rekurencyjne procedury P zawarte w jakiejkolwiek pętli, rp:

void P(int n)

I

while(V)

(

Instrl;

P(n-l);

}

)

nie jest uważane za terminalne, bow iem w zależności od warunku V, wywol* nie P(n-l) może, ale nie musi być wykonywane jako ostatnie.

Twierdzenie 1 Następujące procedury PI i P2 są sobie wzajemnie równowai ne, pod warunkiem że PI zawiera tylko jedno rekurencyjut wywołanie terminalne.

void P2(x)

(

while(!Cond(x)) (

InstrŻ(x); x=F(x);

)

Instrl(x);

)

void fi(x)

(

if (Cond(x))

Instrl(x); else (

Instr2(x);

PI(F(x))

I

)

6.3. Kilka przykładów derekursywacji algorytmów

Wypróbujmy teraz świeżo nabytą wiedzę na „nieśmiertelnym’' przykładzie tzw. wież Hanoi. Jest to łamigłówka o dość legendarnym rodowodzie — w co wnikać nie będziemy podczas naszych wywodów, koncentrując się raczej na problemie logicznym i sposobie rozwiązania go.

iy) i końcowa (z prawej) dla 4 krążków

O

Zadanie jest następujące: marny do dyspozycji n krążków o malejących średnicach, każdy z nich posiada wydrążoną dziurkę, która umożliwia nadzianie go na jeden z 3 wbitych w ziemię drążków'. Na rysunku 6-1 jest przedstawiona sytuacja początkowa (z lewej stron

r~ A- r	i jL
	_j

»)    b)    c)

Rys. 6-1.    T,

Wieże Hanoi    r- y

- prezentacja

problemu.    j

»)    b)