[Algorytmy] Rekurencja w sposób iteracyjny

[Mariusz M]

Cormen i reszta zapisali sortowanie stogowe w sposób rekurencyjny
Sortowanie przez scalanie oraz sortowanie przez podział
też jest często podawane w sposób rekurencyjny
W przypadku sortowania przez scalanie widziałem że niektórzy oprócz procedury sortującej
także procedurę scalającą piszą w sposób rekurencyjny

Oczywiście sortowania to tylko przykład chodzi mi o jakiś ogólny sposób
zamiany algorytmu rekurencyjnego na jego iteracyjny odpowiednik

[Jacek_Karwatka]

Generalnie nie ma ogólnej metody która pozwalała by każdy problem który jest opisany rekurencyjnie zapisać w sposób iteracyjny. Tym niemniej w wielu konkretnych przypadkach można rozwikłać rekurencje i w wielu przypadkach tak się postępuje. Olbrzymią zaletą rekurencyjnego zapisu algorytmu jest jego prostota i klarowność. Jednak należy zachować ostrożność - rekurencyjne metody obliczeniowe mogą być dużo mniej wydajne niż ich iteracyjne odpowiedniki np. obliczając liczby Fibonacciego w sposób rekurencyjny mamy wykładniczo rosnąca złożoność liczby wywołań funkcji, obliczając iteracyjne dostaniemy liniową złożoność.

[Mariusz M]

Mógłbyś coś więcej napisać o tym rozwikłaniu rekurencji ?

Jako przykłady podałem sortowania

Sortowanie przez kopcowanie wersja zamieszczona u Cormena i reszty
Strukturą danych niech będzie tablica
Sortowanie przez scalanie tutaj niech strukturą danych będzie lista
a procedurami rekurencyjnymi procedura scalająca i procedura sortująca
Jeżeli na strukturę danych wybierzemy tablicę to będzie potrzebna
dodatkowa pamięć nie tylko na obsłużenie rekurencji
Sortowanie przez podział działa na tej samej zasadzie co sortowanie przez scalanie
tylko sortowanie odbywa się na etapie dzielenia
Strukturą danych może być albo tablica albo lista

Jeśli chodzi o przykłady to poza sortowaniami mamy np

Wyszukiwanie binarne

Wieże Hanoi

itp

[Jacek_Karwatka]

Weźmy np. Wieże Hanoi
Piękny rekurencyjny algorytm wygląda tak:

Kod: Zaznacz cały

przenieś n krążków z A na B
{
  if n >1
  {
      przenieś n-1 krążków z A na C
      przenieś n-ty krążek z A na B
      przenieś n-1 krążków z C na B
  }
  if n==1
  {
     przenieś 1-ty krążek z A na B
  }
}

okazuje się ze algorytm można też zapisać bez użycia rekurencji.
Do pomysłu prowadzą dwie obserwacje:
-po pierwsze, zawsze na przemian przenosimy krążek najmniejszy i jakiś większy
-po drugie, krążek najmniejszy zawsze wędruje cyklicznie w tą samą stronę (z A na B, z B na C, z C na A)

Stąd pomysł iteracyjnego algorytmu:

Kod: Zaznacz cały

przenieś najmniejszy krążek cyklicznie w prawo
while cala wieża nie jest przeniesiona
{
   wykonaj jedyny możliwy ruch nie przesuwając najmniejszego krążka
   przenieś najmniejszy krążek cyklicznie w prawo
}

dla nieparzystych n przeniesiemy wieżę w prawo, dla parzystych w lewo.

Kiedy zna się ten algorytm udowodnienie że jest on równoważny algorytmowi rekurencyjnemu jest dość proste, ale wpaść na niego tak prosto nie jest.

Generalnie każdy problem jest inny, i nie ma ogólnych metod jak z procedury rekurencyjnej przejść do iteracyjnej wersji algorytmu. Istnieją oczywiście pewne analogie i powiązania miedzy podobnymi problemami. Często jednak drobna zmiana w rekurencji prowadzi do zupełnie innego algorytmu iteracyjnego. Sprawdza się chyba tylko jedna zasada. Praktyka czyni mistrza:-)

[Mariusz M]

Jeśli chodzi o sortowania to u Cormena i reszty
tylko procedura przywracająca kopiec jest zapisana rekurencyjnie

Kod: Zaznacz cały

const maxA=2000;   
{Starsze środowiska mają limit 64kB na tablice związany z modelem pamięci w DOS}
type TElem=integer; 
{Typ calkowity dlatego że najłatwiej się losuje liczby calkowite}
       TArray=array[1..maxA]of TElem; 

procedure heapify(var A:TArray;i,heapsize:integer);
var left,right,largest:integer;
      temp:TElem;
begin
   left:=2*i;
   right:=2*i+1;
   if((left<=heapsize)and(A[left]>A[i]))then
      largest:=left
   else
      largest:=i;
   if((right<=heapsize)and(A[right]>A[largest])then
       largest:=right;
   if(largest<>i)then
   begin
      temp:=A[i];
      A[i]:=A[largest];
      A[largest]:=temp;
      heapify(A,largest,heapsize);
   end;
end;

{Pozostałe procedury już są iteracyjne}

Procedury rekurencyjne w sortowaniu listy przez scalanie

Kod: Zaznacz cały

    type PNode=^Node;
           Node=record
                      data:integer;
                      next:PNode;
                   end;

{Procedura dzieląca jest iteracyjna}

function merge(a,b:PNode):PNode;
var r:PNode;
begin
   r:=nil; 
   if(a=nil)then
      r:=b
   else if(b=nil)then
     r:=a
   else 
   begin
      if(a^.data<=b^.data)then
      begin
         r:=a;
         r^.next:=merge(a^.next,b); 
      end
      else
      begin
         r:=b;
         r^.next:=merge(a,b^.next);    
      end;
   end; 
   merge:=r;   
end;

procedure mergeSort(var head:PNode);
var h1,h2:PNode;
begin
   h1:=nil;
   h2:=nil;
   if((head<>nil)and(head^.next<>nil))then
   begin
      split(head,h1,h2); {Ta procedura już jest iteracyjna}
      mergeSort(h1);
      mergeSort(h2);
      head:=merge(h1,h2);
   end;
end;

Kod: Zaznacz cały

const maxA=2000;   
{Starsze środowiska mają limit 64kB na tablice związany z modelem pamięci w DOS}
type TElem=integer; 
{Typ calkowity dlatego że najłatwiej się losuje liczby calkowite}
       TArray=array[1..maxA]of TElem; 
 
procedure partitionSort(var A:TArray;l,r:integer);
var i,j:integer;
     x,y:TElem;
begin
    i:=l;
    j:=r;
    x:=A[(l+r)div 2];
    repeat
       while(A[i] < x) do  i:=i+1;
       while(x < A[j]) do  j:=j-1;
       if(i<=j)then
       begin
          y:=A[i];
          A[i]:=A[j];
          A[j]:=y;
          i:=i+1;
          j:=j-1;       
       end;
    until(i>j);
    if(l<j) then partitionSort(A,l,j);
    if(i<r) then partitionSort(A,i,r);           
end;

wyszukiwanie

Kod: Zaznacz cały

const maxA=2000;   
{Starsze środowiska mają limit 64kB na tablice związany z modelem pamięci w DOS}
type TElem=integer; 
{Typ calkowity dlatego że najłatwiej się losuje liczby calkowite}
       TArray=array[1..maxA]of TElem; 

function linearSearch(A:TArray;n,i:integer;x:TElem):integer;
begin
    if(i>n)then linearSearch:=0
    else if(A[i]=x)then linearSearch:=i
    else linearSearch:=linearSearch(A,n,i+1,x);  
end;

Kod: Zaznacz cały

const maxA=2000;   
{Starsze środowiska mają limit 64kB na tablice związany z modelem pamięci w DOS}
type TElem=integer; 
{Typ calkowity dlatego że najłatwiej się losuje liczby calkowite}
       TArray=array[1..maxA]of TElem; 

function binarySearch(var A:TArray;p,r:integer;x:TElem):integer;
var q:integer;
begin
   if(p>r)then binarySearch:=0
   else
   begin
      q:=(p+r) div 2;
       if(A[q]=x)then binarySearch:=q
       else if(A[q]>x)then  binarySearch:=binarySearch(A,p,q-1,x)
       else binarySearch:=binarySearch(A,q+1,r,x);
   end; 
end;