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,

Wyszukiwarka

Podobne podstrony:
ALG1 6.3. Kilka przykładów derekursywacji algorytmów 171 Musimy przełożyć krążki z drążka oznaczone
ALG3 Rozdział 3Analiza sprawności algorytmów Podstawowe kryteria pozwalające na wybór właściwego al
ALG3 4.1. Sortowanie przez wstawianie, algorytm klasy 0(N2) 83 Idea tego algorytmu opiera się na na
ALG3 6,6. Klasyczne schematy derekursywacji 183 ( A<x) i PO ; D(x) i } also C(X)
pokazać odniesienie algorytmu do ułamków dziesiętnych: Nauczyciel podaje kilka przykładów do
ALG
3 Przedmowa 13Rozdział 10 Elementy algorytmiki grafów Opis jednej z najciekawszych struktur dany
ALG3 3.4. Przykład 3: Wpadamy w pułapkę 63 Korzystając z powyższej uwagi oraz informacji zawartych
zaproponować kilka przykładowych (ale zróżnicowanych) ćwiczeń pozwalających poloniście rozwijać tę
zaproponować kilka przykładowych (ale zróżnicowanych) ćwiczeń pozwalających poloniście rozwijać tę

więcej podobnych podstron