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
)
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