Wstęp do programowania/Rekursja: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 1: Linia 1:
Częstokroć stajemy  przed  problemem,  który  łatwo  by  było
+
Częstokroć stajemy  przed  problemem,  który  łatwo  byłoby
 
rozwiązać, gdybyśmy mieli w  ręku  odpowiedź  dla  mniejszych  
 
rozwiązać, gdybyśmy mieli w  ręku  odpowiedź  dla  mniejszych  
danych.  Dla  przykładu  obliczenie  silni  liczby  <math> n</math>  wymaga  
+
danych.  Dla  przykładu, obliczenie  silni  liczby  <math> n</math>  wymaga  
 
przemnożenia silni <math> (n-1)</math> przez <math> n</math>. Wiemy zatem, że:  
 
przemnożenia silni <math> (n-1)</math> przez <math> n</math>. Wiemy zatem, że:  
 
<span id=""/>  
 
<span id=""/>  
Linia 45: Linia 45:
 
naturalnej, która byłaby spodziewanym wynikiem  obliczeń.  Poza  
 
naturalnej, która byłaby spodziewanym wynikiem  obliczeń.  Poza  
 
tym  lekką  przesadą  możnaby    nazwać    używanie    tak  
 
tym  lekką  przesadą  możnaby    nazwać    używanie    tak  
skomplikowanych operacji, jak potęgowanie liczb  niewymiernych  w  
+
skomplikowanych operacji jak potęgowanie liczb  niewymiernych  w  
 
celu uzyskania w miarę prostej liczby naturalnej.
 
celu uzyskania w miarę prostej liczby naturalnej.
  
Linia 84: Linia 84:
  
 
Zauważmy, że  podobnie  jak  w  przypadku  źle  skonstruowanych  
 
Zauważmy, że  podobnie  jak  w  przypadku  źle  skonstruowanych  
pętli możemy nabawić sobie 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.  
+
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ą  
 
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
 
pamięć blokując potrzebny jej  fragment  do  końca
Linia 123: Linia 123:
 
wiemy, że nawet dla niewielkich stosunkowo  danych,  rzędu  100,  
 
wiemy, że nawet dla niewielkich stosunkowo  danych,  rzędu  100,  
 
żaden komputer na świecie  nie  poradzi  sobie  z  zakończeniem  
 
żaden komputer na świecie  nie  poradzi  sobie  z  zakończeniem  
obliczeń, niezależnie od tego, jak jest szybki i jak wiele  czasu  
+
obliczeń, niezależnie od tego jak jest szybki i jak wiele  czasu  
 
mu damy.
 
mu damy.
  
Linia 148: Linia 148:
 
   }
 
   }
 
     '''begin'''
 
     '''begin'''
     '''if'''  F[n]<0  '''then''' {Wartosc F[n] nie jest jeszcze obliczona, wiec
+
     '''if'''  F[n]<0  '''then''' {Wartosc F[n] nie jest jeszcze obliczona, więc
                     zaczniemy  od  wypelnienia tablicy  wlasciwa
+
                     zaczniemy  od  wypełnienia tablicy  właściwą
                     wartoscia}
+
                     wartością}
 
       '''if''' n <= 0 '''then''' F[n]:=n  
 
       '''if''' n <= 0 '''then''' F[n]:=n  
 
       '''else''' F[n] := Fibo1(n-2) + Fibo1(n-1);
 
       '''else''' F[n] := Fibo1(n-2) + Fibo1(n-1);
   {i teraz dopiero nadamy odpowiednia wartosc identyfikatorowi Fibo.
+
   {i teraz dopiero nadamy odpowiednią wartośc identyfikatorowi Fibo.
   Ttablicy F[n] znajduje sie zawsze wlasciwa wartosc}
+
   Ttablicy F[n] znajduje się zawsze własciwa wartość}
 
     Fibo1 := F[n]
 
     Fibo1 := F[n]
 
     '''end'''; {Fibo1}
 
     '''end'''; {Fibo1}
Linia 161: Linia 161:
 
Wykonanie  tego  programu  dla paru danych szybko przekona  nas  o  
 
Wykonanie  tego  programu  dla paru danych szybko przekona  nas  o  
 
skuteczności tego ulepszenia. Tym razem  powinniśmy  także uważać  
 
skuteczności tego ulepszenia. Tym razem  powinniśmy  także uważać  
na stosunkowo nieduży zakres typu integer i jeżeli chcemy  obliczać  
+
na stosunkowo nieduży zakres typu integer, i jeżeli chcemy  obliczać  
 
większe liczby Fibonacciego,  musimy  użyć  innego  typu  (np.  
 
większe liczby Fibonacciego,  musimy  użyć  innego  typu  (np.  
 
longint).
 
longint).
  
 
Rzecz jasna istnieją znacznie prostsze metody pozwalające nam na  
 
Rzecz jasna istnieją znacznie prostsze metody pozwalające nam na  
obliczenie n-tej liczby Fibonacciego. Podobniejak  w  przypadku  
+
obliczenie n-tej liczby Fibonacciego. Podobnie jak  w  przypadku  
 
silni,  można  to  zrobić  jedną  prostą  pętlą  z  czterema  
 
silni,  można  to  zrobić  jedną  prostą  pętlą  z  czterema  
 
przypisaniami.  Są  jednak  problemy,  dla  których  znalezienie  
 
przypisaniami.  Są  jednak  problemy,  dla  których  znalezienie  
nierekurencyjnego rozwiązania ani nie  jest  proste,  ani  warte  
+
nierekurencyjnego rozwiązania ani nie  jest  proste,  ani  warte  
 
zachodu ze względu na elegancję  i  efektywność  rekurencji  w  
 
zachodu ze względu na elegancję  i  efektywność  rekurencji  w  
 
tych przypadkach.
 
tych przypadkach.
Linia 175: Linia 175:
 
{{kotwica|wieze Hanoi|}}
 
{{kotwica|wieze Hanoi|}}
 
Wielu znane jest zapewne  zadanie  o  wieżach  z  Hanoi.  Legenda  
 
Wielu znane jest zapewne  zadanie  o  wieżach  z  Hanoi.  Legenda  
głosi że w pewnej swiątyni byddyjskiej w Hanoi, znajdują się  
+
głosi, że w pewnej świątyni buddyjskiej w Hanoi znajdują się  
 
trzy  wbite  w  ziemię  pręty.  Na  jednym  z  nich  początkowo  
 
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  
 
umieszczono 64 koła o malejących średnicach.  Należy  te  koła  
Linia 184: Linia 184:
 
warunkiem, że kładzie się go na pusty pręt lub na  krążek  o  
 
warunkiem, że kładzie się go na pusty pręt lub na  krążek  o  
 
większej średnicy.
 
większej średnicy.
Ponoć mnisi przekładają od jakiegoś czasu te krążki, a  gdy  
+
Ponoć mnisi przekładają od jakiegoś czasu te krążki, a  gdy  
 
skończą, nastąpi koniec świata.
 
skończą, nastąpi koniec świata.
  
 
Jak można wyobrazić sobie najprostszy algorytm przekładający w  
 
Jak można wyobrazić sobie najprostszy algorytm przekładający w  
możliwie    szybki    sposób    krążki?     Jeden    krążek  
+
możliwie    szybki    sposób    krążki? Przenieść jeden krążek to żadna sztuka. Jak jednak poradzić  sobie  z  ich  
przenieść, to żadna sztuka. Jak jednak poradzić  sobie  z  ich  
+
większą liczbą? Załóżmy indukcyjnie,  
większą liczbą. Załóżmy indukcyjnie,  
 
 
że umiemy tego dokonać dla <math> n-1</math> krążków. Rekurencyjnie  nasz  
 
że umiemy tego dokonać dla <math> n-1</math> krążków. Rekurencyjnie  nasz  
 
algorytm formułuje się bardzo  prosto.  Aby  przełożyć  wieżę  
 
algorytm formułuje się bardzo  prosto.  Aby  przełożyć  wieżę  
Linia 217: Linia 216:
  
 
Procedura,  która  dokona  wygenerowania  kolejnych  ruchów  
 
Procedura,  która  dokona  wygenerowania  kolejnych  ruchów  
przenoszących  n-elementową  wieże   może  więc  wyglądać  
+
przenoszących  n-elementową  wieżę   może  więc  wyglądać  
 
następująco.  Zakładamy,  że  zamiast  dźwigania  krążków  
 
następująco.  Zakładamy,  że  zamiast  dźwigania  krążków  
 
komputer będzie wypisywał kolejne  ruchy  w  postaci  przenieś  
 
komputer będzie wypisywał kolejne  ruchy  w  postaci  przenieś  
Linia 224: Linia 223:
 
{{kotwica|kod_zrodlowy|}}
 
{{kotwica|kod_zrodlowy|}}
 
   '''procedure''' Hanoi (n, skad, dokad:integer);
 
   '''procedure''' Hanoi (n, skad, dokad:integer);
     { procedura przenosi n krążkow z wieży skżd na wieżę dokąd }
+
     { procedura przenosi n krążkow z wieży skąd na wieżę dokąd }
 
             '''procedure''' przenies (co, skad, dokad:integer);
 
             '''procedure''' przenies (co, skad, dokad:integer);
             { Tu rzecz jasna mozna wpisac dowolnie inteligentna procedure}
+
             { Tu rzecz jasna można wpisać dowolnie inteligentną procedurę}
 
             '''begin'''
 
             '''begin'''
 
             writeln ('PRZENIES ', CO, ' Z ', skad, ' NA ', dokad)
 
             writeln ('PRZENIES ', CO, ' Z ', skad, ' NA ', dokad)
Linia 235: Linia 234:
 
     '''else'''
 
     '''else'''
 
       '''begin'''
 
       '''begin'''
         {zauwazmy, ze jezeli jeden pret ma numer i, a drugi j, '''to''' trzeci
+
         {zauważmy, że jeżeli jeden pręt ma numer i, a drugi j, to trzeci
 
         z nich ma numer 6-i-j}
 
         z nich ma numer 6-i-j}
 
         hanoi  (n-1, skad, 6-skad-dokad);
 
         hanoi  (n-1, skad, 6-skad-dokad);

Wersja z 08:57, 16 lis 2006

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 wymaga przemnożenia silni przez . Wiemy zatem, że:

dla

Możemy tę parę wzorów przyjąć za definicję funkcji silnia. Takie definiowanie nazywamy rekurencyjnym lub 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 zdefiniujemy rekurencyjnie następująco:

dla

,

to używając metody indukcji matematycznej, możemy łatwo udowodnić, że .

Napotykamy jednak często na problemy, które w odróżnieniu od funkcji silnia, czy ciągu , 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 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:

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 spowoduje, że identyfikatorowi silnia zostanie nadana wartość . Stanie się to w następujący sposób. Najpierw sprawdzimy, czy równa się zero. Jeżeli tak, to wynik wyniesie 1. Jeżeli nie, to wywołana zostanie funkcja silnia od parametru , a jej wynik przemnożony zostanie przez dając ostateczną wartość funkcji. Wykonanie instrukcji mnożenia przez 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 , zawartość stanu komputera zostanie odtworzona i mnożenie przez 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 przejmie , 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 ).

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 .

 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 . Aby obliczyć wartość , będziemy musieli wywołać Fibo dla i dla , 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 Fibo będzie bowiem proporcjonalna do wartości wykładniczej ze względu na . 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 . W tym celu zadeklarujemy sobie tablicę , w której będziemy przechowywali obliczone już wartości . 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); 
 {
 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, więc
                    zaczniemy  od  wypełnienia  tablicy  właściwą 
                    wartością}
     if n <= 0 then F[n]:=n 
     else F[n] := Fibo1(n-2) + Fibo1(n-1);
 {i teraz dopiero nadamy odpowiednią wartośc identyfikatorowi Fibo.
  Ttablicy 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 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 krążków przełożyć na pręt trzeci, następnie przełożyć krążek na pręt drugi, a następnie -elementową wieżę przełożyć z pręta trzeciego na drugi przy pomocy pierwszego.

Zauważmy przy okazji, że liczba przenosin krążków, , wymaga dwukrotnego przeniesienia wieży złożonej z krążków oraz jednokrotnego przeniesienia jednego krążka. Mamy więc wzór:

zatem

.

Liczba przenosin jest więc wykładnicza ze względu na . 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 na pręt .

 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 . 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 , więc trudno tu cokolwiek poprawić. Rzecz jasna procedurę należy wywoływać dla danych znacznie mniejszych niż 64.