Rekurencja a iteracja w praktyce

Do rozwiązania problemu możemy wykorzystać zarówno metodę iteracyjną, jak i rekurencyjnąrekurencjarekurencyjną (rekursywną). Ale która z nich jest lepsza?

Nie ma tu jednoznacznej odpowiedzi. Metoda rekurencyjna wymaga wolnego miejsca w stosie. Stos używany jest do zapisu zmiennych lokalnych, przekazywanych argumentów, jak również adresu powrotuadres powrotuadresu powrotu. Każde kolejne wywołanie funkcji rekurencyjnej wymaga użycia pamięci stosu dla tych danych, co sprawia, że liczba wywołań jest ograniczona. Jednak w niektórych przypadkach metoda rekurencyjna jest czytelniejsza niż iteracyjna, np. w algorytmie sortowania przez scalanie.

Zmiana rozmiaru stosu

Jeżeli wyczerpie się pamięć przeznaczona na stos, system operacyjny zgłosi błąd i zakończy działanie programu. Przepełnienie stosu sygnalizowane jest zwykle komunikatem Segmentation fault (w systemach Linux) lub Access Violation (w systemach Windows).

Rozmiar stosu ogranicza maksymalną liczbę wywołań rekurencyjnych. Domyślnie jest to rozmiar rzędu kilku megabajtów i zależy od użytego kompilatora oraz systemu operacyjnego. W systemie Linux z kompilatorem GCC wynosi on domyślnie 8 MB, co pozwala na ok. 200 000 wywołań rekurencyjnych. Rozmiar stosu można tu zmienić systemowym poleceniem ulimit -s [wartość w kB]. W systemie Windows o rozmiarze stosu decyduje linkerlinkerlinker, domyślnie ma on rozmiar 1 MB.

Ciąg Fibonacciego – implementacja rekurencyjna oraz iteracyjna

Przeanalizujmy powyższe rozumowanie na konkretnym przykładzie – porównajmy dwie funkcje obliczające n‑ty wyraz ciągu Fibonacciego.

Na początek przypomnijmy definicję ciągu Fibonacciego:

Jest to definicja rekurencyjna, zatem możemy zaimplementować ją wprost, zgodnie z poniższą specyfikacją:

Specyfikacja:

Dane:

• n – liczba naturalna oznaczająca numer elementu ciągu Fibonacciego do obliczenia przez program

Wynik:

• liczba – liczba całkowita, n‑ty wyraz ciągu Fibonacciego

long long fibonacciRekurencyjnie(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    return fibonacciRekurencyjnie(n-1) + fibonacciRekurencyjnie(n-2);
}

Przykładową implementację iteracyjną możemy zrealizować następująco (ona również spełnia warunki powyższej specyfikacji):

long long fibonacciIteracyjnie(int n) {
    long long wyrazAktualny = 0,
              wyrazNastepny = 1,
              wyrazPoprzedni;
            
    for (int i = 0; i < n; i++) {
        wyrazPoprzedni = wyrazAktualny;
        wyrazAktualny = wyrazNastepny;
        wyrazNastepny += wyrazPoprzedni;
    }
    
    return wyrazAktualny;
}

Sprawdźmy teraz, która implementacja jest wydajniejsza. W tym celu uruchomimy prosty kod, który wykona po 20 wywołań każdej z napisanych funkcji ze stopniowo rosnącym argumentem. Aby porównać liczbę czynności koniecznych do wykonania przez każdą z funkcji, zadeklarujemy dwie zmienne globalne: licznikRekurencyjny oraz licznikIteracyjny. Pierwsza z nich będzie zwiększana z każdym kolejnym wywołaniem funkcji rekurencyjnej, a druga - w pętli w funkcji iteracyjnej. W funkcji głównej programu porównamy wyniki, a przed każdym kolejnym porównaniem obu funkcji liczniki zostaną wyzerowane.

#include <iostream>
using namespace std;

int licznikRekurencyjny,
    licznikIteracyjny;

long long fibonacciRekurencyjnie(int n) {
    licznikRekurencyjny++;
    if (n == 0) return 0;
    else if (n == 1) return 1;
    return fibonacciRekurencyjnie(n - 1) + fibonacciRekurencyjnie(n - 2);
}

long long fibonacciIteracyjnie(int n) {
    long long wyrazAktualny = 0,
              wyrazNastepny = 1,
              wyrazPoprzedni;

    for (int i = 0; i < n; i++) {
        licznikIteracyjny++;
        wyrazPoprzedni = wyrazAktualny;
        wyrazAktualny = wyrazNastepny;
        wyrazNastepny += wyrazPoprzedni;
    }

    return wyrazAktualny;
}

int main() {
    cout << "Rekurencyjnie:\tIteracyjnie:" << endl;
    for (int i = 0; i < 20; ++i) {
        licznikIteracyjny = 0;
        licznikRekurencyjny = 0;

        fibonacciIteracyjnie(i);
        fibonacciRekurencyjnie(i);

        cout << licznikRekurencyjny << "\t" << licznikIteracyjny << endl;
    }
}

Po uruchomieniu kod wypisuje na standardowe wyjście programu następujące rezultaty:

Rekurencyjnie:  Iteracyjnie:
1       0
1       1
3       2
5       3
9       4
15      5
25      6
41      7
67      8
109     9
177     10
287     11
465     12
753     13
1219    14
1973    15
3193    16
5167    17
8361    18
13529   19

Oczywiście wyników nie należy interpretować dosłownie, gdyż nie jesteśmy w stanie stwierdzić, która operacja jest bardziej kosztowna – pojedyncze wywołanie funkcji czy pojedyncze wykonanie kodu w pętli. Widzimy jednak, że złożoność obliczeniowa funkcji rekurencyjnej jest znacząco większa niż w przypadku funkcji iteracyjnej. Przyczynę takiego stanu rzeczy przedstawia schemat ($F_n$ oznacz $n$-ty wyraz ciągu Fibonacciego):

RCnZIlfQeK9tq

Ilustracja przedstawia drzewko ułożone z zielonych bloków z napisami. Pierwszy blok posiada napis F n, z niego wychodzą dwie linie.
Lewa linia dąży do bloku z wpisem: F n‑1, prawa do F n‑2.
Od bloku z wpisem F n‑2 wychodzą dwie linie.
Lewa dąży do bloku z wpisem: F n‑3, a prawa do bloku z wpisem F n‑4.
Od bloku z wpisem F n‑1 wchodzą dwie linie.
Lewa do bloku z wpisem F n‑2, a prawa do bloku z wpisem F n‑3.
Od każdego z ostatnich bloków wychodzą po dwie przerywane linie.

Już na drugim i trzecim poziomie wartość $F_{n-2}$ musi zostać policzona dwa razy osobno. Podobna sytuacja powtarza się podczas kolejnych wywołań – dla $F_{n-3}$, $F_{n-4}$ itd. Wielokrotnie liczymy te same wartości, przez co zwiększa się złożoność obliczeniowa.

Spróbujmy porównać również złożoność pamięciową obu funkcji. W przypadku metody iteracyjnej możemy od razu stwierdzić, że jest ona stała. Funkcja iteracyjna deklaruje tylko dwie (włącznie z parametrem) zmienne typu int i trzy zmienne typu long long. Natomiast funkcja rekurencyjna – biorąc pod uwagę fakt, że przy każdym kolejnym wywołaniu musimy zapisać na stosie przekazywane argumenty, adres powrotu oraz wszystkie zmienne lokalne – potrzebuje dużo więcej pamięci. Dodatkową wadą funkcji rekurencyjnej jest również możliwość przepełnienia stosu dla dużego argumentu n.

Łatwo zatem stwierdzić, że rekurencyjne obliczanie elementów ciągu Fibonacciego nie jest dobrym przykładem zastosowania rekurencji. Błędem byłoby jednak założenie, że należy unikać tej metody. Istnieją algorytmy oraz struktury danych specjalnie projektowane i optymalizowane pod rekurencję. Przykładem mogą być tu algorytmy szybkiego sortowania, np. sortowanie przez scalanie lub sortowanie szybkie (quick sort). Zadaniem programisty jest ocenienie, które podejście będzie lepsze dla danego problemu.

Silnia – implementacja rekurencyjna oraz iteracyjna

Funkcję silnia możemy zdefiniować iteracyjnie w następujący sposób:

Z kolei definicja rekurencyjna może wyglądać tak:

Aby lepiej wskazać różnice między obiema metodami, zaimplementujemy (korzystając z powyższych definicji) obliczanie wartości silni.

Specyfikacja:

Dane:

• n – liczba naturalna, dla której należy obliczyć wartość $n!$

Wynik:

• silnia – liczba naturalna, wartość $n!$

Obliczanie metodą rekurencyjną:

#include <iostream>
using namespace std;

long long silniaRekurencja(int);

int main() {
  cout << silniaRekurencja(5) << endl;
  
  return 0;   
}

long long silniaRekurencja(int n) {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    }
    
    return n * silniaRekurencja(n - 1);
}

Obie zasady działania rekurencji zostały zachowane.

1. Każde kolejne rekurencyjne wywołanie funkcji ma inną wartość argumentu, ponieważ za każdym razem zmienna n zmniejsza swoją wartość o 1;

2. Funkcja będzie wywoływana tak długo, aż zmienna n osiągnie wartość 1. Gdy tylko tak się stanie, funkcja zwróci wartość 1! do funkcji, która ją wywołała. Ta z kolei pomnoży tę liczbę przez wartość zmiennej n, która została jej przekazana, a następnie zwróci wynik. Czynność ta będzie powtarzać się do momentu, gdy końcowa wartość zostanie zwrócona do funkcji main, gdzie zostanie wypisana na ekran.

Oto fragment kodu poszerzony o implementację algorytmu wyliczającego wartość silni metodą iteracyjną:

#include <iostream>
using namespace std;

// Metoda rekurencyjna
long long silniaRekurencja(int n) {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return 1;
    }
    
    return n * silniaRekurencja(n - 1);
}

// Metoda iteracyjna
long long silniaIteracyjna(int n) {
    long long silniaIteracyjna = 1;
    
    for (int i = 2; i <= n; i++) {
        silniaIteracyjna *= i;
    }
    
    return silniaIteracyjna;
}

int main() {
  // Argument silni
  int n;
  cin >> n;
  
  // Wypisywanie wyników
  cout << "Silnia rekurencyjna: " << silniaRekurencja(n) << endl;
  cout << "Silnia iteracyjna: " << silniaIteracyjna(n) << endl;
  
  return 0;
    
}

W metodzie iteracyjnej zmienną sterującą pętli for inicjujemy wartością 2, ponieważ mnożenie $1\cdot 1$ nie będzie miało żadnego wpływu na wynik działania programu. Przy  każdej iteracji wartość silniaIteracyjna jest mnożona przez i. Pętla kończy działanie, gdy wartość zmiennej sterującej staje się większa niż zmienna n.

Bez względu na to, jakiej metody użyjemy, wynik będzie taki sam. Główną różnicą jest wygoda i sposób zapisu. Poza tym przy zastosowaniu metody rekurencyjnej program będzie wykonywał się nieco dłużej. Mają na to wpływ instrukcje warunkowe, które będą sprawdzane przy każdym wywołaniu funkcji, jak również zapis i odczyt ze stosu.

Słownik