Recursivitate

Ce se întâmplă când o funcție se apelează pe sine, cum arată condiția de oprire și cum urmărești pe hârtie un apel recursiv.

Ideea

O funcție recursivă se apelează pe ea însăși, pentru un caz mai mic al aceleiași probleme.

int factorial(int n) {
    if (n == 0) return 1;           // cazul de bază
    return n * factorial(n - 1);    // pasul recursiv
}

Definiția matematică este n! = n · (n-1)!, cu 0! = 1, iar programul o transcrie cuvânt cu cuvânt.

Cele două părți obligatorii

Cazul de bază este situația care se rezolvă direct, fără alt apel. Aici, n == 0.

Pasul recursiv reduce problema la un caz mai mic, mai apropiat de cazul de bază.

Dacă lipsește cazul de bază sau dacă pasul nu se apropie de el, apelurile continuă până când programul se oprește brusc. E același lucru ca o buclă infinită.

int gresit(int n) {
    return n * gresit(n - 1);    // nu se oprește niciodată
}

Ce se întâmplă efectiv

Fiecare apel are propriile variabile, păstrate separat. Apelurile se așază unul peste altul și se rezolvă în ordine inversă.

Pentru factorial(4):

factorial(4) → 4 * factorial(3)
               factorial(3) → 3 * factorial(2)
                              factorial(2) → 2 * factorial(1)
                                             factorial(1) → 1 * factorial(0)
                                                            factorial(0) → 1

și apoi înapoi: 1 → 1·1 = 1 → 2·1 = 2 → 3·2 = 6 → 4·6 = 24.

Reține: înmulțirea cu n se face la întoarcere, nu la coborâre. Când te uiți la un algoritm recursiv, întreabă-te mereu dacă lucrul se face înainte sau după apel. De asta depinde ordinea rezultatelor.

Înainte sau după apel

Compară cele două funcții:

void a(int n) {
    if (n == 0) return;
    cout << n << " ";
    a(n - 1);
}

void b(int n) {
    if (n == 0) return;
    b(n - 1);
    cout << n << " ";
}

Pentru n = 4, prima afișează 4 3 2 1, a doua 1 2 3 4.

Aceleași două linii, puse în ordine inversă, dau rezultate inverse. La Subiectul I, o bună parte din itemii despre recursivitate verifică exact diferența asta.

Prima variantă afișează la coborâre, a doua la întoarcere.

Cum urmărești pe hârtie

Nu încerca să ții toate apelurile în minte. Desenează-le indentat, ca în schema de mai sus, fiecare apel nou mai la dreapta și cu valorile parametrilor. Când un apel ajunge la cazul de bază, scrie ce returnează și urcă.

E singura metodă sigură și devine rapidă după ce te obișnuiești cu ea.

Exemple

Suma cifrelor

int sc(int n) {
    if (n == 0) return 0;
    return n % 10 + sc(n / 10);
}

Cmmdc

int cmmdc(int a, int b) {
    if (b == 0) return a;
    return cmmdc(b, a % b);
}

Poate e cea mai curată funcție recursivă din toată programa de bac, pentru că e chiar definiția matematică, scrisă direct.

Ridicarea la putere

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

Verificarea unei proprietăți

bool toateCifrelePare(int n) {
    if (n == 0) return true;
    if ((n % 10) % 2 != 0) return false;
    return toateCifrelePare(n / 10);
}

Aici sunt două cazuri de bază, unul de succes și unul de eșec. Tiparul acesta apare des.

Recursivitate sau iterație?

Orice funcție recursivă se poate scrie cu bucle și invers.

Recursivitatea câștigă când problema este definită recursiv (cmmdc, parcurgeri de arbori, backtracking). Codul iese mult mai scurt și mai aproape de definiție.

Iterația câștigă aproape în rest: nu consumă memorie suplimentară și nu riscă să oprească programul la adâncime mare.

Fiecare apel ocupă memorie, iar zona în care se păstrează apelurile este limitată, de obicei la ordinul zecilor sau sutelor de mii de apeluri imbricate. O recursivitate de adâncime n = 10⁶ se oprește brusc, chiar dacă e corectă logic.

Un avertisment concret

int fib(int n) {
    if (n <= 2) return 1;
    return fib(n-1) + fib(n-2);
}

Codul e corect și elegant, dar inutilizabil. fib(50) face peste un miliard de apeluri, pentru că aceleași valori se recalculează de nenumărate ori. Varianta iterativă, cu trei variabile, face 50 de pași.

Recursivitatea e mai bună doar când structura problemei o cere.

De reținut

Orice funcție recursivă are un caz de bază și un pas care se apropie de el.
Lucrul făcut înainte de apel dă o ordine, cel făcut după dă ordinea inversă.
Urmărește apelurile desenându-le indentat, nu din memorie.
Fiecare apel consumă memorie, iar o adâncime mare oprește programul.
Recursivitatea naivă poate recalcula de nenumărate ori aceleași valori, ca la Fibonacci.