Wstęp do programowania/Rekursja

Częstokroć stajemy przed problemem, który łatwo byłoby rozwiązać, gdybyśmy mieli w ręku odpowiedź dla mniejszych danych. Dla przykładu, obliczenie silni liczby $n$ wymaga przemnożenia silni $(n-1)$ przez $n$. Wiemy zatem, że:

$0!=1;n!=n*(n-1)!$ dla $n>0$

Możemy tę parę wzorów przyjąć za definicję funkcji silnia. Takie definiowanie nazywamy rekurencyjnym lub indukcyjnym. My jednak słowo indukcja wolimy zachować do określenia sposobu dowodzenia. Będziemy więc mówili o rekurencyjnych definicjach i indukcyjnych dowodach.

Dla przykładu, jeżeli ciąg $T_0,T_1,\dots$ zdefiniujemy rekurencyjnie następująco:

$T_0=0;T_n=2T_{n-1}+1$ dla $n>0$

,

to używając metody indukcji matematycznej, możemy łatwo udowodnić, że $T_n=2^n-1$.

Napotykamy jednak często na problemy, które w odróżnieniu od funkcji silnia, czy ciągu $T_n$, nie mają prostej, nierekurencyjnej postaci, albo wręcz nie jest ona nam znana. Dla przykładu liczby Fibonacciego znane są co najmniej od 1202 roku, i generowanie kolejnych liczb $F_n$ bezpośrednio ze wzoru rekurencyjnego nie stanowi żadnego problemu, jednak dopiero Euler, a niezależnie od niego w 100 lat później w roku 1843 francuski matematyk J.Binet udowodnił wzór bezpośrednio wyliczający n-tą liczbę Fibonacciego:

$F_n=\frac{1}{\sqrt{5}}({\left(\frac{\sqrt{5}+1}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n)$

Znajomość tego wzoru wcale nie rozwiązuje nam wszystkich problemów związanych z wyliczeniem n-tej liczby Fibonacciego. Przede wszystkim komputer mógłby mieć trudności ze stwierdzeniem, że wynik jest liczbą naturalną, choć w istocie powyższy wzór Eulera-Bineta generuje jedynie liczby naturalne.

Gdyby bowiem próbował wyciągać pierwiastek z pięciu, to nieuniknione stałoby się zaokrąglenie wyniku i w rezultacie moglibyśmy otrzymać wartość lekko różniącą się od liczby naturalnej, która byłaby spodziewanym wynikiem obliczeń. Poza tym lekką przesadą możnaby nazwać używanie tak skomplikowanych operacji jak potęgowanie liczb niewymiernych w celu uzyskania w miarę prostej liczby naturalnej.

Ponieważ stosujemy zasadę, że to komputer powinien dostosowywać się w miarę możliwości do potrzeb człowieka, więc mechanizmy pozwalające na korzystanie z rekurencji istnieją w większości współczesnych języków programowania. W Pascalu użycie rekurencji jest niezwykle naturalne:

 function silnia(n:Integer):Integer;
 begin
   if n=0 then silnia := 1
          else silnia := n*silnia(n-1)
 end;

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 ${s}{i}{l}{n}{i}{a}(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 ${s}{i}{l}{n}{i}{a}(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 ${s}{i}{l}{n}{i}{a}(n-1)$ zostanie obliczona w analogiczny sposób. Rolę wartości $n$ przejmie $n-1$, zatem wywoła się w miarę potrzeby ${s}{i}{l}{n}{i}{a}(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$.

 function Fibo(n:integer):Integer; 
 {funkcja liczy n-ta liczbe Fibonacciego dla n>=0}
   begin
     if n <= 1 then Fibo := n
     else Fibo := Fibo(n-2) + Fibo(n-1)
   end; {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 ${F}{i}{b}{o}(2)$ weźmiemy się za liczenie ${F}{i}{b}{o}(3)$ od nowa. Do policzenia ${F}{i}{b}{o}(3)$ będziemy jednak potrzebowali wartości ${F}{i}{b}{o}(1)$ oraz ${F}{i}{b}{o}(2)$. Ponieważ komputer nie otrzymał od nas żadnych wskazówek dotyczących wykorzystania raz już obliczonych wartości, więc zacznie od nowa obliczać ${F}{i}{b}{o}(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ę.

 var F:array[0..m] of Integer;

 function 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
 }
   begin
   if  F[n]<0  then {Wartosc F[n] nie jest jeszcze obliczona, więc
                    zaczniemy  od  wypełnienia  tablicy  właściwą 
                    wartością}
     if n <= 1 then F[n]:=n 
     else 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]
   end; {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:

1. jednorazowo można przenieść jeden krążek
2. krążek można nałożyć na dowolny z prętów pod

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$.

 procedure Hanoi (n, skad, dokad:integer);
   { procedura przenosi n krążkow z wieży skąd na wieżę dokąd }
           procedure przenies (co, skad, dokad:integer);
           { Tu rzecz jasna można wpisać dowolnie inteligentną procedurę}
           begin
            writeln ('PRZENIES ', CO, ' Z ', skad, ' NA ', dokad)
           end;
   begin
    if n<=1 then
       przenies (1, skad, dokad)
    else
     begin
       {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)
     end
   end;

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.