11.8 Funkcje rekurencyjne

Funkcje w C/C++ mogą wywoływać same siebie — takie funkcje nazywamy funkcjami rekurencyjnymi. Przy definiowaniu takich funkcji trzeba oczywiście zadbać, aby ciąg wywołań skończył się. Zatem przed wywołaniem samej siebie funkcja zwykle sprawdza pewien warunek i jeśli nie jest on spełniony, nie dokonuje już samo-wywołania.

Jako przykład rozpatrzmy funkcję gcd z poniższego programu. Oblicza ona i zwraca największy wspólny dzielnik (ang. greatest common divisor) swoich dwóch argumentów, które są liczbami naturalnymi (całkowitymi dodatnimi). Użyty algorytm to znana wszystkim modyfikacja algorytmu Euklidesa opisanego w Elementach jako Twierdzenie VII.2 (i będącego wypadkiem szczególnym wcześniejszego i bardziej ogólnego algorytmu, przypisywanemu Teajtetosowi):

P74: gcd.cpp Algorytm Euklidesa - realizacja rekurencyjna

      1.  #include <iostream>
      2.  using namespace std;
      3.  
      4.  int gcd(int a, int b) {
      5.      return b == 0 ? a : gcd(b, a % b);
      6.  }
      7.  
      8.  int main() {
      9.      int x, y;
     10.  
     11.      x = 732591; y = 1272585;
     12.      cout << "gcd(" << x << "," << y << ")\t= "
     13.           << gcd(x,y) << endl;
     14.  
     15.      x = 732591; y = 1270;
     16.      cout << "gcd(" << x << "," << y << ")\t= "
     17.           << gcd(x,y) << endl;
     18.  }

Sama funkcja realizująca algorytm składa się w zasadzie z jednej instrukcji return. Dopóki zmienna lokalna b nie stanie się równa zeru, funkcja wywołuje się rekurencyjnie. Z analizy teoretycznej wynika, że dla prawidłowych danych (a więc liczb naturalnych, czyli, w szczególności, dodatnich) po skończonej liczbie kroków wartość b musi stać się równa zeru. Tak więc warunek zakończenia (tzw. warunek stopu) jest zapewniony i funkcja działa prawidłowo:

    gcd(732591,1272585)     = 129
    gcd(732591,1270)        = 1

„Samowywołanie” się funkcji jest w zasadzie normalnym wywołaniem: wszystkie lokalne zmienne są tworzone oddzielnie w każdym wywołaniu, mechanizm przekazywania argumentów jest taki sam jak dla funkcji nierekursywnych. Na przykład funkcja gcd kreuje zmienne lokalne a i b a następnie, obliczając wyrażenie za dwukropkiem, wywołuje tę samą funkcję gcd i czeka na zwrócenie wyniku. To następne „wcielenie” funkcji też tworzy swoje zmienne lokalne a i b, woła gcd i czeka na wynik, aby go zwrócić, itd. Kiedy w końcu b stanie się zero, funkcja zwróci a, które zostanie zwrócone przez poprzednie „wcielenie”, które zostanie zwrócone przez poprzednie „wcielenie”, itd.

Funkcje rekurencyjne trzeba stosować z umiarem i umiejętnie. Nieprzemyślane zastosowanie rekurencji może bowiem prowadzić do kombinatorycznej eksplozji liczby wywołań i rozmiaru stosu potrzebnego do realizacji rekurencji. Tak na przykład bywa, gdy w treści funkcji wywołanie samej siebie występuje dwukrotnie, jak w klasycznym przykładzie nieprawidłowego obliczania wartości wyrazów ciągu Fibonacciego. Definicja tego ciągu jest następująca:

$\begin{displaymath}F_n = \begin{cases} n & \text{dla\ } 0 \leqslant n < 2, \\ F_{n-1}+F_{n-2} & \text{dla\ } n \geqslant 2 \end{cases}\end{displaymath}$

Naturalnym sposobem zaprogramowania takiej funkcji jest postać rekurencyjna jak w następującym programie (w linii ➊, po dwukropku, mamy tu dwukrotne wywołanie przez funkcję samej siebie):

P75: fib.cpp Ciąg Fibonacciego: zły przykład rekurencji

      1.  #include <iostream>
      2.  #include <iomanip>
      3.  using namespace std;
      4.  
      5.  int licznik;
      6.  
      7.  int fib(int n) {
      8.      licznik++;
      9.      return (n < 2) ? n : fib(n-1) + fib(n-2);    ➊
     10.  }
     11.  
     12.  int main() {
     13.      cout << "\n  i       Fib(i)  # wywolan\n"
     14.              "---------------------------" << endl;
     15.      for (int i = 10; i <= 43; i += 3) {
     16.          licznik = 0;
     17.          int w = fib(i);
     18.          cout << setw(3)  << i << setw(12) << w   ➋
     19.               << setw(12) << licznik << endl;
     20.      }
     21.  }

W programie wprowadziliśmy zmienną globalną licznik zliczającą liczbę wywołań funkcji fib podczas znajdowania elementów ciągu Fibonacciego — zmienna ta jest zerowana przed przystąpieniem do wyliczania każdego kolejnego elementu ciągu. W ten sposób możemy wypisać nie tylko wartości kolejnych liczb Fibonacciego, ale również liczbę wywołań funkcji, jak były potrzebne do ich wyliczenia. Obliczenia zabrały kilka sekund; większość tego czasu zużyta została na obliczenie ostatniej wartości, czyli F₄₃. Poniższy wydruk z tego programu pokazuje, że do obliczenia F₄₃ potrzebne było ponad miliard wywołań!

      i       Fib(i)  # wywolan
    ---------------------------
     10          55         177
     13         233         753
     16         987        3193
     19        4181       13529
     22       17711       57313
     25       75025      242785
     28      317811     1028457
     31     1346269     4356617
     34     5702887    18454929
     37    24157817    78176337
     40   102334155   331160281
     43   433494437  1402817465

Oczywiście wykonanie wersji „normalnej”, a więc tzw. iteracyjnej, tej funkcji zabiera ułamek sekundy i w ogóle nie zużywa miejsca na stosie. [Użyte w tym programie tzw. manipulatory (setw w linii ➋) służą jedynie do przejrzystego sformatowania tabelki wyników — będą one omówione w rozdziale o operacjach we/wy ].

T.R. Werner, 21 lutego 2016; 20:17