ALG3

2.3. Jak wykonują się programy rekurencyjne? 33

2.3. Jak wykonują się programy rekurencyjne?

Dociekliwy Czytelnik będzie miał prawo zapytać w tym miejscu: „OK. zobaczyłem na przykładzie, że TO działa, ale mam też chyba prawo poznać bardziej od podszewki JAK to działa!”. Pozostaje zatem przyporządkować się temu słusznemu żądaniu.

Odpowiedzią na nic jest właśnie niniejszy' podrozdział. Przykład w nim użyty będzie być może banalny, tym niemniej nadaje się doskonale do zilustrowania sposobu wykonywania programu rekurencyjnego.

Już w szkole średniej (lub może nawet podstawowej?!) na lekcjach matematyki dość często używa się tzw. silni z n. czyli iloczynu wszystkich liczb naturalnych od / do n włącznie. Ten użyteczny symboli zdefiniowany jest w sposób następujący:

0! - 1,

n! =    (n — 1)! gdzie n > 1

Pomińmy jego znaczenie matematyczne, nieistotne w tym miejscu. Nic nie stoi jednak na przeszkodzie, aby napisać prosty program, któiy zajmuje się obliczaniem silni w sposób rekurencyjny:

rek2.cpp

unsigned long int silnia(int x)

t

if (x--0) return 1; clse

return z^silnia(x-i);

)

Prześledźmy na przykładzie, jak się wykonuje program, któiy obliczy 3! Rysunek 2-2 przedstawia kolejne etapy wywoływania procedury reknrencyjnej i badanie warunku na przypadek elementarny.

Konwencje użyte podczas tworzenia są następujące:

•    pionowe strzałki w dól oznaczają „zagłębianie się” programu z poziomu n na n-1 itd. w celu dotarcia do przypadku elementarnego 0!\

•    pozioma strzałka oznacza obliczanie wyników cząstkowych;

•    ukośna strzałka prezentuje proces przekazywania wyniku cząstkowego z poziomu niższego na wyższy.

¹ Oznaczany przez n\