Funcții recursive

Funcțiile recursive sunt funcții care se apelează pe ele însele. Astfel de funcții sunt adesea utilizate pentru a parcurge diverse structuri. De exemplu, dacă trebuie să găsim un anumit fișier într-un dosar, mai întâi verificăm toate fișierele din acel dosar, apoi toate subdosarele sale.

De exemplu, să definim calculul factorialului sub forma unei funcții recursive:

#include <iostream>
  
unsigned long long factorial(unsigned);
  
int main()
{
    unsigned n {5};
    auto result { factorial(n)};
    std::cout << "Factorial of " << n << " is equal to " << result << std::endl;
}
  
unsigned long long factorial(unsigned n)
{
    if(n > 1)
        return n * factorial(n-1);
    return 1;
}

În funcția factorial este definită condiția că, dacă numărul n este mai mare ca 1, atunci acest număr este înmulțit cu rezultatul aceleași funcții, în care se transmite ca parametru numărul n-1. Adică are loc o coborâre recursivă. Și așa mai departe, până când ajungem la momentul în care valoarea parametrului este egală cu 1. În acest caz, funcția returnează 1.

O funcție recursivă trebuie neapărat să aibă un caz de bază, care folosește operatorul return și către care converg toate celelalte apeluri ale funcției. În cazul factorialului, cazul de bază este situația în care n = 1. În acest caz se execută instrucțiunea return 1;.

De exemplu, pentru apelul factorial(5) se obține următorul lanț de apeluri:

5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1

Un alt exemplu frecvent și ilustrativ de funcție recursivă este funcția care calculează numerele Fibonacci. Al n-lea termen din șirul Fibonacci se definește prin formula:

f(n) = f(n - 1) + f(n - 2), cu condițiile f(0) = 0 și f(1) = 1.

Valorile f(0) = 0 și f(1) = 1 definesc cazurile de bază pentru această funcție:

#include <iostream>
  
unsigned long long fib(unsigned);
  
int main()
{
    for(unsigned i{}; i < 10; i++)
    {
        auto n = fib(i);
        std::cout << n << "\t";
    }
    std::cout << std::endl;
}
unsigned long long fib(unsigned n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

Rezultatul execuției programului – afișarea în consolă a primelor 10 numere din șirul Fibonacci:

În exemplele de mai sus, funcția își apelează direct propria definiție. Însă apelul recursiv poate fi și indirect. De exemplu, funcția fun1() apelează altă funcție fun2(), care la rândul ei o apelează din nou pe fun1(). În acest caz, funcțiile fun1() și fun2() sunt numite funcții recursiv mutuale.

Trebuie menționat că deseori funcțiile recursive pot fi rescrise sub forma unor cicluri. De exemplu, pentru calculul factorialului, putem folosi un ciclu în locul recursiei:

#include <iostream>
  
unsigned long long factorial(unsigned);
  
int main()
{
    unsigned n {6};
    std::cout << "Factorial of " << n << " : " << factorial(n) << std::endl;
}
  
unsigned long long factorial(unsigned n)
{
    unsigned long long result{1};
    for(unsigned i{1}; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

Și deseori structurile iterative sunt mai eficiente decât recursia. De exemplu, dacă o funcție se apelează pe sine de mii de ori, este necesară o cantitate mare de memorie de stivă pentru a stoca copii ale valorilor parametrilor și adresele de revenire pentru fiecare apel, ceea ce poate duce la epuizarea rapidă a memoriei de stivă alocate programului, deoarece această memorie este, de obicei, fixă și limitată. Acest lucru poate duce la închiderea neașteptată a programului.

Din acest motiv, în astfel de cazuri este de preferat să folosim soluții alternative, cum ar fi ciclurile. Cu toate acestea, în ciuda costurilor suplimentare, utilizarea recursiei poate simplifica considerabil scrierea programului.