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