Recursivitate

Un subprogram este recursiv dacă se autoapelează direct sau prin intermediul altor subprograme.

Un subprogram recursiv conține:

o condiție de oprire (altfel, apelurile ar fi infinite);
un apel recursiv care apropie funcția de această condiție.

Exemple de operații matematic recursive:

ridicarea la putere: aⁿ = a * a^n-1 = a * a * a^n-2 = ...
factorial: n! = n * (n-1)! = ...
suma cifrelor: sumCif(n) = n%10 + sumCif(n/10) = ...
șirul lui Fibonacci: fib(n) = fib(n-1) + fib(n-2) = ...

Exemplu: factorialul unui număr

Implementarea în C++ cu o funcție recursivă s-ar face în următorul mod:

int factorial(int n) {
    if (n == 0) return 1; // conditie de oprire
    return n * factorial(n - 1); // apel recursiv
}

Observăm în subprogram:

condiția de oprire (cazul de bază) este atunci când n este 0;
în instrucțiunea return se așteaptă rezultatul funcției reapelate;
în fiecare funcție se înmulțește valoarea din parametru cu rezultatul returnat de apelul recursiv.

Recursiv vs. Iterativ

De multe ori, un algoritm scris recursiv (cu autoapeluri ale funcției) este o adaptare a celui iterativ (cu bucle). Să considerăm un exemplu comun întâlnit:

Să se scrie un subprogram care determină rezultatul operației aⁿ, unde a și n sunt două numere întregi.

Funcția iterativă:

int putere (int a, int n){
    int p = 1;
    for(int i = 1; i <= n; i++) {
        p *= a;
    }
    return p;
}

Funcția recursivă:

int putere (int a, int n){
  if(n == 0) return 1;
  return a * putere(a, n - 1);
}

În ambele subprograme, transmitem cele 2 date de intrare ca parametru, prin valoare. Se observă că varianta recursivă este o alternativă mai elegantă, mai ales în acest context unde însăși operația de înmulțire repetată a aceluiași număr a de n ori este un procedeu matematic recursiv.

Afișarea în subprograme recursive

Uneori, ar putea fi nevoie să realizăm diferite afișări în interiorul funcției recursive. În funcție de poziția afișării față de apelul recursiv, putem determina diferite modele de afișare. Spre exemplu:

Afișarea înainte de apelul recursiv

Atunci când afișarea se situează înainte de apelul recursiv, vom vedea rezultatele în ordinea în care se execută (apelează) subprogramele.


void f(int n){
    if(!n) return;
    cout << n % 10;
    f(n / 10);
}

n = 123456; f(n):
654321

Ca și caz de bază (condiția de oprire a recursivității), vom returna atunci când parametrul n ajunge la valoarea 0.

Afișarea după apelul recursiv

Dacă se afișează după apelul recursiv, vom vedea rezultatele în ordinea inversă executării funcțiilor apelate recursiv.


void f(int n){
    if(!n) return;
    f(n / 10);
    cout << n % 10;
}

n = 123456; f(n):
123456

Putem ține cont de această particularitate pentru a oferi o soluție elegantă în anumite scenarii, precum următoarele:

inversarea cifrelor unui număr;
afișarea elementelor unui vector de la început la sfârșit, sau invers;
parcurgerea în preordine / postordine a arborilor binari.