ALG3

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

Pokaźna grupa procedur rekurencyjnych dość łatwo poddaje się transformacji opisanej w Twierdzeniu 1. Ponadto wiele procedur daje się sprowadzić, poprzez niewielkie modyfikacje kodu, do „transformowanej” postaci. Taki właśnie przykład będziemy teraz analizowali.

Podczas omawiania rekurencji mieliśmy okazję poznać programową realizację funkcji obliczającej silnię:

int silnia!int x)

I

cout « "x" << x « endl; if (x—0) return 1; else

return x*silnia(x—1);

}

Czy uda nam się zamienić ją na wersję iteracyjną? Pierwszy problem skupia się na tym, że mamy do czynienia ze skrótem polegającym na wprowadzeniu wywołania rekurencyjnego do równania zwracającego wynik funkcji Nic jednak nie stoi na przeszkodzie, aby ową sporną linię rozpisać, co da nam następującą wersję (oczywiście całkowicie równoważną):

int silnia(int x!

{

if (x==0) return 1;

else

(

int tmp=si1ni a(x-l); return x*tmp;

ł

Niestety, niewiele nam to pomogło, gdyż wywołanie rekurencyjne nie jest terminalne, a zatem nie jest możliwe zastosowanie Twierdzenia 1. Ta przeszkoda może być jednak łatwo pokonana, jeśli dokonamy kolejnej transformacji:

int silnia(int x, int resl)

(

if (x==0) return res; else

silnia(x-l,x*res);

)

Nie sposób tu ukryć, że powróciliśmy do tak zachwalanego, podczas omawiania rekurencji, typu rekurencji „z parametrem dodatkowym” (taką wówczas przyjęliśmy nazwę). Czyżby zatem rekurencja „terminalna” i rekurencja „z parametrem dodatkowym” były dokładnie tymi samymi fenomenami?! Jeśli tak,