<b>function</b> silnia(n:Integer):Integer; <b>begin</b> <b>if</b> n=0 <b>then</b> silnia := 1 <b>else</b> silnia := n*silnia(n-1) <b>end</b>;
Wywołanie tej funkcji od pewnego naturalnego argumentu \( n\ge 0 \) spowoduje, że identyfikatorowi silnia zostanie nadana wartość \( n! \). Stanie się to w następujący sposób. Najpierw sprawdzimy, czy \( n \) równa się zero. Jeżeli tak, to wynik wyniesie 1. Jeżeli nie, to wywołana zostanie funkcja silnia od parametru \( n-1 \), a jej wynik przemnożony zostanie przez \( n \) dając ostateczną wartość funkcji. Wykonanie instrukcji mnożenia przez \( n \) zostanie więc zawieszone na czas obliczenia wartości \( {silnia}(n-1) \). Zawartość sumatora i wszystkich rejestrów używanych przez komputer do obliczeń zostaną więc automatycznie zapamiętane przez system wykonujący program tak, że \({silnia}(n-1) \) wykona się w czystym środowisku. Po obliczeniu silni z \( n-1 \), zawartość stanu komputera zostanie odtworzona i mnożenie przez \( n \) będzie mogło zostać zakończone.
Rzecz jasna \( {silnia}(n-1) \) zostanie obliczona w analogiczny sposób. Rolę wartości \( n \) przejmie \( n-1 \), zatem wywoła się w miarę potrzeby \( {silnia}(n-2) \) itd. Widać więc, że do wywołania funkcji silnia od jakiegoś dużego parametru wymaga się zawieszenia wykonywania mnożeń na wielu poziomach wywołań rekurencyjnych (po jednym dla każdego \( 1 \le k \le n \)).
Zauważmy, że podobnie jak w przypadku źle skonstruowanych pętli, możemy nabawić się kłopotów wywołując funkcję silnia od argumentu ujemnego. System zacznie wtedy wywoływać kaskadę silni wołanych dla parametrów ujemnych coraz bardziej oddalonych od zera. Gdyby pamięć komputera była nieskończona, spowodowałoby to nieskończone zapętlenie się programu. Każde wywołanie funkcji wymaga jednak zapamiętania aktualnego stanu komputera. Zużywa to dostępną pamięć blokując potrzebny jej fragment do końca wywołania funkcji; w naszym przypadku ten koniec nigdy nie nastąpi. Program zostanie zatem zerwany przez system wykonujący z powodu braku pamięci. Nie jest to jednak jedyna groźba, którą napotykamy stosując rekurencję. Znacznie poważniejszym problemem może okazać się nieprawidłowa organizacja rekurencji powodująca brzemienne w skutkach zużycie czasu wykonywanego programu.
Spróbujmy zastosować technikę rekurencyjną do napisania funkcji obliczającej n-tą liczbę Fibonacciego \( F_n \).
<b>function</b> Fibo(n:integer):Integer; {funkcja liczy n-ta liczbe Fibonacciego dla n>=0} <b>begin</b> <b>if</b> n <= 1 <b>then</b> Fibo := n <b>else</b> Fibo := Fibo(n-2) + Fibo(n-1) <b>end</b>; {Fibo}
Na pierwszy rzut oka widać, że funkcja powinna dobrze zadziałać. Została napisana zgodnie z podaną wyżej definicją liczb Fibonacciego. Spróbujmy zatem prześledzić, jak będzie się wykonywać dla \( n=4 \). Aby obliczyć wartość \( F_4 \), będziemy musieli wywołać Fibo dla \( n=2 \) i dla \( n=3 \), a następnie dodać te wartości. Zauważmy jednak, że obliczywszy \( { Fibo}(2) \) weźmiemy się za liczenie \( { Fibo}(3) \) od nowa. Do policzenia \( {Fibo}(3) \) będziemy jednak potrzebowali wartości \( {Fibo}(1) \) oraz \( {Fibo}(2) \). Ponieważ komputer nie otrzymał od nas żadnych wskazówek dotyczących wykorzystania raz już obliczonych wartości, więc zacznie od nowa obliczać \( {Fibo}(2) \).
Ta drobna niegospodarność będzie nas dużo kosztować. Liczba wywołań funkcji Fibo będzie bowiem proporcjonalna do wartości wykładniczej ze względu na \( n \). Oznacza to, jak już wiemy, że nawet dla niewielkich stosunkowo danych, rzędu 100, żaden komputer na świecie nie poradzi sobie z zakończeniem obliczeń, niezależnie od tego jak jest szybki i jak wiele czasu mu damy.
Cały problem będzie rozwiązany bezboleśnie, jeżeli tylko nie dopuścimy do więcej niż jednokrotnego wywołania funkcji dla tych samych danych. Wystarczy zatem stworzyć bank danych o obliczonych już wartościach \( F_n \). W tym celu zadeklarujemy sobie tablicę \( F \), w której będziemy przechowywali obliczone już wartości \( F_n \). Aby zaznaczyć, że dana wartość nie została jeszcze obliczona, wypełnimy tablicę minus jedynkami. Funkcję Fibo będziemy zatem liczyli rekurencyjnie jedynie w miarę potrzeby, czyli wtedy, gdy dla danego argumentu liczymy ją po raz pierwszy. Zmodyfikujmy zatem naszą funkcję.
<b>var</b> F:array[0..m] <b>of</b> Integer; <p><b>function</b> Fibo1(n:integer): Integer; { funkcja liczy n-ta liczbe Fibonacciego dla n>=0, korzystając przy tym z globalnej tablicy F, przy czym F[i] = F_i, jezeli F_i jest juz obliczone F[i] = -1, jezeli nie jest jeszcze obliczone Założenie: n>=0 } <b>begin</b> <b>if</b> F[n]<0 <b>then</b> {Wartosc F[n] nie jest jeszcze obliczona, więc zaczniemy od wypełnienia tablicy właściwą wartością} <b>if</b> n <= 1 <b>then</b> F[n]:=n <b>else</b> F[n] := Fibo1(n-2) + Fibo1(n-1); {i teraz dopiero nadamy odpowiednią wartośc identyfikatorowi Fibo. W tablicy F[n] znajduje się zawsze własciwa wartość} Fibo1 := F[n] <b>end</b>;{Fibo1}
Wykonanie tego programu dla paru danych szybko przekona nas o skuteczności tego ulepszenia. Tym razem powinniśmy także uważać na stosunkowo nieduży zakres typu integer, i jeżeli chcemy obliczać większe liczby Fibonacciego, musimy użyć innego typu (np. longint).
Rzecz jasna istnieją znacznie prostsze metody pozwalające nam na obliczenie n-tej liczby Fibonacciego. Podobnie jak w przypadku silni, można to zrobić jedną prostą pętlą z czterema przypisaniami. Są jednak problemy, dla których znalezienie nierekurencyjnego rozwiązania ani nie jest proste, ani warte zachodu ze względu na elegancję i efektywność rekurencji w tych przypadkach.
Wielu znane jest zapewne zadanie o wieżach z Hanoi. Legenda głosi, że w pewnej świątyni buddyjskiej w Hanoi znajdują się trzy wbite w ziemię pręty. Na jednym z nich początkowo umieszczono 64 koła o malejących średnicach. Należy te koła przenieść z pierwszego pręta na drugi przy pomocy trzeciego, respektując następujące zasady:
warunkiem, że kładzie się go na pusty pręt lub na krążek o większej średnicy. Ponoć mnisi przekładają od jakiegoś czasu te krążki, a gdy skończą, nastąpi koniec świata.
Jak można wyobrazić sobie najprostszy algorytm przekładający w możliwie szybki sposób krążki? Przenieść jeden krążek to żadna sztuka. Jak jednak poradzić sobie z ich większą liczbą? Załóżmy indukcyjnie, że umiemy tego dokonać dla \( n-1 \) krążków. Rekurencyjnie nasz algorytm formułuje się bardzo prosto. Aby przełożyć wieżę złożoną z n krążków z jednego pręta na drugi przy pomocy trzeciego, należy \( n-1 \) krążków przełożyć na pręt trzeci, następnie przełożyć krążek \( n \) na pręt drugi, a następnie \( (n-1) \)-elementową wieżę przełożyć z pręta trzeciego na drugi przy pomocy pierwszego.
Zauważmy przy okazji, że liczba przenosin \( n \) krążków, \( T_n \), wymaga dwukrotnego przeniesienia wieży złożonej z \( n-1 \) krążków oraz jednokrotnego przeniesienia jednego krążka. Mamy więc wzór:
\( T_1 = 1; \ T_n=2T_{n-1}+1 \)
zatem
\( T_n=2(2^{n-1}-1)+1=2^n-1 \). Liczba przenosin jest więc wykładnicza ze względu na \( n \). Możemy spać spokojnie. Nawet jeżeli mnisi będą bardzo wydajni, to prędzej nastąpi koniec Układu Słonecznego, aniżeli przełożenie tych 64 krążków (zakładając, że mnisi zaczęli w czasach historycznych).
Procedura, która dokona wygenerowania kolejnych ruchów przenoszących n-elementową wieżę może więc wyglądać następująco. Zakładamy, że zamiast dźwigania krążków komputer będzie wypisywał kolejne ruchy w postaci przenieś krążek z pręta \( i \) na pręt \( j \).
<b>procedure</b> Hanoi (n, skad, dokad:integer); { procedura przenosi n krążkow z wieży skąd na wieżę dokąd } <b>procedure</b> przenies (co, skad, dokad:integer); { Tu rzecz jasna można wpisać dowolnie inteligentną procedurę} <b>begin</b> writeln ('PRZENIES ', CO, ' Z ', skad, ' NA ', dokad) <b>end</b>; <b>begin</b> <b>if</b> n<=1 then przenies (1, skad, dokad) <b>else</b> <b>begin</b> {zauważmy, że jeżeli jeden pręt ma numer i, a drugi j, to trzeci z nich ma numer 6-i-j} hanoi (n-1, skad, 6-skad-dokad); przenies (n, skad, dokad ); hanoi (n-1, 6-skad-dokad, dokad) <b>end</b> <b>end</b>;
Nasza procedura będzie teraz działała w czasie wykładniczym ze względu na \( n \). Dzieje się tak w zasadzie zawsze, gdy bez żadnych finezji dokonujemy we wnętrzu procedury więcej niż jednokrotnego wywołania rekurencyjnego tej procedury. Tym razem jednak nie będzie to stanowiło wady rozwiązania - taka jest natura problemu: odpowiedź w postaci ciągu ruchów do wykonania ma długość wykładniczą ze względu na \( n \), więc trudno tu cokolwiek poprawić. Rzecz jasna procedurę należy wywoływać dla danych znacznie mniejszych niż 64.