Zapisywanie algorytmów rekurencyjnych w sposób iteracyjny

Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Robakks
Czasem tu bywam
Czasem tu bywam
Posty: 149
Rejestracja: 30 wrz 2012, 20:36
Podziękowania: 2 razy
Otrzymane podziękowania: 13 razy
Płeć:

Zapisywanie algorytmów rekurencyjnych w sposób iteracyjny

Post autor: Robakks »

Jak zapisywać algorytmy rekurencyjne w sposób iteracyjny

Jeśli chodzi o przykłady to można wziąć

Sortowanie przez kopcowanie (wersja umieszczona w książce Cormena)
Sortowanie przez scalanie
Sortowanie przez podział (tzw szybkie)

Wieże Hanoi
arksoftware
Rozkręcam się
Rozkręcam się
Posty: 39
Rejestracja: 24 maja 2016, 11:44
Otrzymane podziękowania: 9 razy
Płeć:

Post autor: arksoftware »

Algorytm rekurencyjny można zaimplementować nie zapisując wprost wołania funkcji przez samą siebie. Np. algorytm sprawdzania, czy liczba znajduje się w posortowanej tablicy metodą połowienia w języku C może wyglądać tak:

Kod: Zaznacz cały

int exists (int *array, int N, int element)
{
  if (N == 1)
  {
    return (array[0] == element);
  }
  else if (array[N/2] >= element)
  {
    return exists (array, N/2);
  }
  else 
  {
    return exists (array + N/2, N/2);
  }
}
lub tak:

Kod: Zaznacz cały

int exists (int *array, int N, int element)
{

  int left = 0, right = N-1;

  while (left != right)
  {
    int center = (left + right) / 2;
    if ( array[center] >= element )
    {
      right = center;
    }
    else 
    {
      left = center;
    }
  }
  return (array [left] == element)
}
Ten kod napisałem na szybko bez uruchomienia i przetestowania, na pewno ma bugi, ale chodzi mi o pokazanie idei.

W przypadku bardziej złożonych algorytmów zrezygnowanie z rekurencji jest o wiele trudniejsze, ponieważ w każdym wywołaniu funkcja rekurencyjna woła samą siebie kilka razy. Jednym ze sposobów byłoby manualne zaimplementowanie stosu rekurencji. W tym celu należałoby zadeklarować strukturę zawierającą wszystkie dane podproblemu. Następnie tworzymy stos obiektów tej struktury i umieszczamy na nim jeden obiekt opisujący wejściowy problem. Następnie kręcimy się w pętli while, dopóki stos nie będzie pusty. W każdej iteracji pętli pobieramy i przetwarzamy element ze stosu. Jeśli rozwiązanie wymaga rozwiązania podproblemów, to umieszczamy je na stosie.

Czy odpowiedziałem na twoje pytanie? W razie czego dopytuj śmiało :)
Matematyka: Generator zadań - darmowa apka dla Androida generuje losowe zadania i pokazuje pełne rozwiązania
Robakks
Czasem tu bywam
Czasem tu bywam
Posty: 149
Rejestracja: 30 wrz 2012, 20:36
Podziękowania: 2 razy
Otrzymane podziękowania: 13 razy
Płeć:

Re: Zapisywanie algorytmów rekurencyjnych w sposób iteracyjn

Post autor: Robakks »

Kod: Zaznacz cały

const maxA=1000;
type TElem=integer;
        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;
Czy to jest rekurencja ogonowa ?
Jak zamienić ją na iterację bez żadnych instrukcji break i innych goto
ODPOWIEDZ