Wstęp do programowania/Rekursja

Częstokroć stajemy przed problemem. który łatwo by było 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;$Możemy tę parę wzorów przyjąć za definicję funkcji silnia. Takie definiowanie nazywamy {\em rekurencyjnym}; czy też {\em indukcyjnym}. My jednak słowo {\em 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 następująco: $T_0=0;T_n=2T_{n-1}+1,$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 do funkcji {\em 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 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 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);
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 {\em 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 {\em 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 Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em 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 Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em 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 Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em silnia}(n-1)} zostanie obliczona w analogiczny sposób. Rolę wartości $n$ przejmie $n-1$, zatem wywoła się w miarę potrzeby Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em 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ć sobie kłopotów wywołując funkcję {\em 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 silnia(n:integer);
begin
  if n=0 then silnia := 1
         else silnia := n*silnia(n-1)
end;

function Fibo(n: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 wywolać {\em Fibo} dla $n=2$ i dla $n=3$, a następnie dodać te wartości. Zauważmy jednak, że obliczywszy Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em Fibo}(2)} weźmiemy się za liczenie Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em Fibo}(3)} od nowa. Do policzenia Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em Fibo}(3)} będziemy jednak potrzebowali wartości Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em Fibo}(1)} oraz Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em 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ć Parser nie mógł rozpoznać (nieznana funkcja „\em”): {\displaystyle {\em Fibo}(2)} .

Ta drobna niegospodarność będzie nas dużo kosztować. Liczba wywołań funkcji {\em 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ę {\em 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ę.

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

function Fibo(n: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}

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

function Fibo1(n: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
}
  begin
  if  F[n]<0  then {Wartosc F[n] nie jest jeszcze obliczona, wiec
                    zaczniemy  od  wypelnienia  tablicy  wlasciwa 
                    wartoscia}
    if n <= 0 then F[n]:=n 
    else F[n] := Fibo1(n-2) + Fibo1(n-1);
{i teraz dopiero nadamy odpowiednia wartosc identyfikatorowi Fibo.
W tablicy F[n] znajduje sie zawsze wlasciwa wartosc}
  Fibo1 := F[n]
  end; {Fibo1}

Wykonanie tego programu dla paru danych szybko przekona nas o skuteczności tego ulepszenia. Tym razem powinniśmy takze uważać na stosunkowo nieduży zakres typu integer i jeżeli chcemy obliczać większe liczby Fibonacciego, to 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 swiątyni byddyjskiej 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 mozna 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? Jeden krążek przenieść, 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że 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$.

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

function Fibo(n: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}

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

function Fibo1(n: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
}
  begin
  if  F[n]<0  then {Wartosc F[n] nie jest jeszcze obliczona, wiec
                    zaczniemy  od  wypelnienia  tablicy  wlasciwa 
                    wartoscia}
    if n <= 0 then F[n]:=n 
    else F[n] := Fibo1(n-2) + Fibo1(n-1);
{i teraz dopiero nadamy odpowiednia wartosc identyfikatorowi Fibo.
W tablicy F[n] znajduje sie zawsze wlasciwa wartosc}
  Fibo1 := F[n]
  end; {Fibo1}

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 mozna wpisac dowolnie inteligentna procedure}
          begin
           writeln ('PRZENIES ', CO, ' Z ', skad, ' NA ', dokad)
          end;
  begin
   if n<=1 then
      przenies (1, skad, dokad)
   else
    begin
      {zauwazmy, ze jezeli jeden pret 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.