ALG5

3.7. Analiza programów rekurencyjnych 75

otrzymując w efekcie:

=26„_, +3log, 3} _

frównanie liniowe. b_o=0    J

Zadanie w tej postaci nadaje się już do rozwiązania! Po dokonaniu niewielkich obliczeń możemy otrzymać: b„=(2„-l)\og^J, co ostatecznie daje

o _    _ ,2»-l

^c* l i    “    J    •

3.7.5.Funkcja Ackermanna, czyli coś dla smakoszy

Gdyby inale dzieci znały się odrobinę na informatyce, to rodzice na pewno by je straszyli nie kominiarzem, ale funkcją Ackermanna. Jest to wspaniały przykład ukazujący, jak pozornie niegroźna „z wyglądu” funkcja rckurcncyjna może być kosztowna w użyciu. Spójrzmy na listing:

a.cpp

int A(int n, int p)

I

if (n~0) return 1;

if ((p==0)Si(n>=l)) if (n==i) return 2; else

return n+2; if ( (p>=l)&&(n>=l))

return A(A(n-',p),p-1);

I

Pytanie dotyczące tego programu brzmi: jaki jest powód komunikatu Slack overflow! (ong. przepełnienie stosu) podczas próby wykonania go? Komunikat ten sugeruje jednoznacznie, iż podczas wykonania programu nastąpiła znaczna ilość wywołań funkcji Ackermanna. Jak znaczna, okaże się już za chwilę...

Pobieżna analiza funkcji A prowadzi do następującego spostrzeżenia:

V« > 1, A(n. 1) = A(A(n-1,1),0) = A(n-1,1) + 2,

co daje natychmiast

Vm > I, /4(m,I) = 2«.