ALG5

35

2.4. Niebezpieczeństwa rekurencji

2.4.1.Ciąg Fibonacciego

Naszym pierwszym zadaniem jest napisanie programu, który' liczyłby elementy tzw. ciągu Fibonacciego. Ten dziwoląg matematyczny, używany do wielu różnych i czasami zaskakujących celów, jest definiowany następująco:

W 0)= 1,

M i) = U

ftb(n) = f(n -1) + fib{n) gdzie n> 2

Zaprezentowany niżej program jest niemal dokładnym przetłumaczeniem powyższego wzoru i nie powinien stanowić dla nikogo niespodzianki:

rek3.cpp

unsigned long int fibtint x)

(

if (x<2)

return 1;

else

return fib(x-l)+fib(x-2);

}

Spróbujmy prześledzić dokładnie wywołania rekurencyjne. Nieskomplikowana analiza prowadzi do następującego drzewa:

Rys. 2 - 3.

Obliczanie fib(4)

Każde „zacieńiowane” wyrażenie stanowi problem elementarny; problem o rozmiarze n>2 zostaje „rozbity" na dwa problemy o mniejszym stopniu skomplikowania: n-i i n-2.

Skąd się jednak wziął pesymistyczny tytuł tego podrozdziału? Przypatrzmy się dokładniej rysunkowi 2-3. Już w pierwszej chwili można dostrzec, że znaczna część obliczeń jest wykonywana więcej niż jeden raz (np. cała gałąź zaczynająca się od Jih(2) jest wręcz zdublowana!). Funkcja.///) nie ma żadnej możliwości, aby to „zauważyć”¹, w końcu jest to tylko program, który wykonuje to, co mu

Jeśli można sobie pozwolić na tego typu personifikację...