Recursivitate

Recursivitatea apare când un subprogram se apelează pe sine pentru o problemă mai mică. Sunt necesare un caz de oprire și un pas care se apropie de el. Pentru factorial, $0!=1$ și $n!=n\cdot (n-1)!$ când $n>0$. Astfel $3!=3\cdot 2\cdot 1=6$.

Condiția de oprire și autoapelul

O funcție recursivă are două părți: cazul simplu, rezolvat direct, și cazul general, în care funcția se autoapelează pentru o problemă mai mică. Fiecare autoapel trebuie să se apropie de cazul simplu: la fact(n - 1), n scade cu 1 la fiecare apel, deci ajunge la 0. Dacă cele două părți sunt corecte, funcția e corectă pentru orice n, la fel ca la o demonstrație prin inducție.

Stiva apelurilor

Fiecare apel are propriile copii ale parametrilor și ale variabilelor locale, păstrate pe stivă. Când fact(3) ajunge la fact(2), apelul fact(3) rămâne „în așteptare”, cu n = 3, până când fact(2) returnează. Apelurile se închid în ordinea inversă deschiderii: ultimul deschis, fact(0), se termină primul. De aceea, instrucțiunile scrise înaintea autoapelului se execută la coborâre (3, 2, 1), iar cele scrise după el, la revenire (1, 2, 3).

Recursiv sau iterativ

Orice funcție recursivă se poate scrie și iterativ, cu o structură repetitivă. Varianta recursivă e potrivită când problema e definită recursiv (factorial, cmmdc, parcurgerea unui graf, backtracking), dar fiecare apel costă timp și memorie pe stivă. Când două autoapeluri recalculează aceleași valori, numărul de apeluri explodează: F(n) = F(n − 1) + F(n − 2), calculat naiv, face 109 apeluri pentru F(10) și 1 664 079 pentru F(30) (exemplul 4).

Exemplu — numărul de apeluri pentru F(5). Dacă $T(n)$ numără apelurile, $T(1)=T(2)=1$, iar $T(n)=1+T(n-1)+T(n-2)$ pentru $n>2$. Rezultă $T(3)=3$, $T(4)=5$ și $T(5)=9$. Calculul include și apelul inițial, nu numai autoapelurile.

Recursivitate directă și indirectă

Dacă subprogramul se apelează pe sine, recursivitatea este directă. Dacă A îl apelează pe B, iar B îl apelează pe A, recursivitatea este indirectă; și aici trebuie să existe o condiție de oprire comună.

Factorialul, limitele lui și varianta iterativă

Exemplu — factorialul lui 4. Implementarea factorialului păstrează câte un cadru pe stiva apelurilor, până la atingerea cazului de bază:

#include <iostream>
using namespace std;
long long factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}
int main() {
    int n;
    cin >> n;
    cout << factorial(n);
    return 0;
}

Pentru intrarea 4, apelurile coboară factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0). Cazul de bază întoarce 1, iar rezultatele urcă: $1\to 1\cdot 1=1\to 2\cdot 1=2\to 3\cdot 2=6\to 4\cdot 6=24$. Ieșirea este 24. Fiecare apel păstrează propria valoare a parametrului n până când apelul interior se încheie. Timpul este proporțional cu $n$, iar stiva ocupă spațiu proporțional cu $n$. Programul presupune $0\le n\le 20$: pentru $n<0$ argumentul s-ar îndepărta de 0 și apelurile nu s-ar opri, iar pentru $n>20$ valoarea depășește tipul long long.

Fiecare apel păstrează propria valoare a parametrului n până când apelul interior se încheie. Când se ajunge la cazul de bază, nu mai apare un apel nou; la revenire, fiecare nivel face o singură înmulțire. Pentru un n admis, timpul este $O(n)$, iar stiva de apeluri ocupă $O(n)$ spațiu. Programul presupune $0\le n\le 20$: la n<0, argumentul s-ar îndepărta de 0 și apelurile nu s-ar opri, iar peste 20 valoarea nu încape în tipul folosit. Varianta iterativă înmulțește $1\cdot 2\cdots n$ de la mic la mare, fără apeluri pe stivă, cu memorie auxiliară $O(1)$.

Exemple rezolvate

Exemplul 1: factorialul, cu apelurile urmărite

Calculează 5! recursiv.

1. fact(5) = 5 · fact(4) = 5 · 4 · fact(3) = … = 5 · 4 · 3 · 2 · 1 · fact(0).
2. fact(0) returnează 1, apoi valorile se înmulțesc la revenire: 1, 1, 2, 6, 24, 120.

#include <iostream>
using namespace std;

int fact(int n) {
    if (n == 0)
        return 1;                  // conditia de oprire
    return n * fact(n - 1);        // autoapelul, pentru o valoare mai mica
}

int main() {
    cout << fact(5) << "\n";
    return 0;
}

Programul afișează:

120

Exemplul 2: suma cifrelor, recursiv

Suma cifrelor lui n este ultima cifră plus suma cifrelor lui n / 10, iar suma cifrelor lui 0 este 0.

#include <iostream>
using namespace std;

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

int main() {
    cout << sc(52816) << "\n";
    return 0;
}

Programul afișează:

22

Aceeași funcție, scrisă iterativ, este în lecția despre subprograme.

Exemplul 3: ordinea afișărilor

Ce afișează apelul f(3)?

#include <iostream>
using namespace std;

void f(int n) {
    if (n > 0) {
        cout << n;      // la coborare
        f(n - 1);
        cout << n;      // la revenire
    }
}

int main() {
    f(3);
    cout << "\n";
    return 0;
}

1. La coborâre se afișează 3, 2, 1, câte o cifră înaintea fiecărui autoapel.
2. f(0) nu face nimic. La revenire, fiecare apel își afișează propriul n, de la ultimul deschis la primul: 1, 2, 3.

321123

Exemplul 4: câte apeluri face Fibonacci, scris naiv

Șirul lui Fibonacci are F(1) = F(2) = 1 și F(n) = F(n − 1) + F(n − 2). Câte apeluri face funcția recursivă pentru F(10)?

1. Fiecare apel pentru n > 2 face două autoapeluri, iar valorile mici se recalculează de multe ori: F(8) se calculează de 2 ori, F(7) de 3 ori.
2. Numărând toate apelurile, inclusiv pe cel inițial, se obțin 109 apeluri pentru F(10) = 55.

#include <iostream>
using namespace std;

int apeluri = 0;

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

int main() {
    int n;
    cin >> n;
    int r = fib(n);
    cout << r << " " << apeluri << "\n";
    return 0;
}

Pentru intrarea 10, programul afișează valoarea și numărul de apeluri:

55 109

Pentru 30 afișează 832040 1664079. O buclă care ține doar ultimii doi termeni face 28 de pași pentru același rezultat.

Exemplul 5: nivel de examen, o funcție recursivă pe cifre

Se consideră funcția de mai jos. Ce valoare returnează f(2468013) și câte apeluri ale lui f se fac în total?

#include <iostream>
using namespace std;

int nr = 0;

int f(int n) {
    nr++;
    if (n == 0)
        return 0;
    if (n % 2 == 0)
        return f(n / 10) + 1;
    return f(n / 10);
}

int main() {
    cout << f(2468013) << " " << nr << "\n";
    return 0;
}

1. Funcția elimină câte o cifră la fiecare apel și adaugă 1 când ultima cifră e pară, deci numără cifrele pare.
2. Cifrele pare ale lui 2468013 sunt 2, 4, 6, 8 și 0: funcția returnează 5.
3. Numărul are 7 cifre, deci sunt 7 apeluri care elimină câte o cifră, plus apelul final cu n = 0: 8 apeluri.

5 8

Pentru intrarea 4, stiva primește în ordine argumentele 4, 3, 2, 1, 0. Revenirea calculează în ordine 1, 1, 2, 6, 24, iar rezultatul este 24. Varianta iterativă pornește cu produs = 1 și înmulțește succesiv cu 1, 2, 3, 4; obține tot 24, în timp proporțional cu $n$ și cu spațiu auxiliar constant. Pentru orice recursie, verifică atât cazul de bază, cât și faptul că argumentul fiecărui apel se apropie de el. Când o funcție afișează înainte sau după apelul recursiv, ordinea afișărilor diferă: afișarea dinaintea apelului produce valorile în ordinea apelurilor, iar cea de după, în ordinea revenirilor. Pentru void scrie(int n) cu afișarea înainte de apel, scrie(3) produce 321; cu afișarea după apel, produce 123. Dacă un apel are două apeluri recursive, ca la Fibonacci, desenează arborele apelurilor și numără frunzele.

Exemplu în formatul examenului. Ce se afișează în urma executării programului de mai jos?

#include <iostream>
using namespace std;
int f(int n) {
    if (n <= 0) return 0;
    return n % 10 + f(n / 10);
}
int main() {
    cout << f(2345);
    return 0;
}

• a) 5
• b) 14
• c) 5432
• d) 2345

Răspunsul corect este b). Apelurile sunt f(2345), f(234), f(23), f(2) și f(0). Funcția adună ultima cifră a fiecărui argument: $5+4+3+2=14$, iar f(0) întoarce 0. Varianta c) ar fi un număr format din cifrele în ordine inversă, nu o sumă, iar varianta a) ar apărea dacă funcția ar returna numai prima cifră extrasă.

Cazul de bază contribuie la rezultat: dacă funcția din exemplu ar întoarce 1, nu 0, pentru $n\le 0$, atunci f(2345) ar fi $5+4+3+2+1=15$, nu 14.

Unde apare la examen

• Bacalaureatul, informatică, matematică-informatică: programa de examen are un capitol „Recursivitate” (prezentare generală, proceduri și funcții recursive), iar metoda backtracking poate fi implementată recursiv (programa de examen, anexa 2 la OMECTS 4800/2010). La sesiunea din iunie–iulie 2026, al doilea item al Subiectului I a cerut completarea autoapelului unui subprogram recursiv, astfel încât apelul dat să afișeze o valoare cerută (subiectele și baremele Bac 2026). Formatul descris este cel din 2026; potrivit proiectului de ordin pentru Bacalaureatul 2027, programa rămâne aceeași.
• Programa școlară: pe programa veche, recursivitatea este la clasa a XI-a, împreună cu subprogramele (programa de clasa a XI-a, OMECI 5099/2009); pe programa nouă, subprogramele recursive sunt la clasa a X-a, din 2027–2028, în Python (OMEC 4370/2026).

Greșeli frecvente

• Greșit: o funcție recursivă nu are nevoie de un caz de oprire.
  Corect: fără caz de bază apelurile nu se mai opresc.
• Greșit: apelurile recursive nu ocupă memorie suplimentară.
  Corect: fiecare apel adaugă un cadru pe stiva apelurilor.
• Greșit: cazul de bază este întotdeauna n = 1.
  Corect: depinde de problemă; la factorial este n = 0, cu 0! = 1.
• Greșit: cazul de bază este opțional, iar lipsa condiției de oprire nu strică.
  Corect: fără o oprire atinsă, funcția se autoapelează la nesfârșit, până se umple stiva și programul se oprește cu eroare.
• Greșit: fact(n) în loc de fact(n - 1), sau o funcție pe cifre care nu împarte la 10.
  Corect: autoapelul se apropie de oprire; altfel funcția nu se termină niciodată.
• Greșit: fact(n - 1); return n;.
  Corect: rezultatul autoapelului trebuie folosit, deci scrii return n * fact(n - 1);.
• Greșit: ce e scris după autoapel se execută în ordinea apelurilor.
  Corect: se execută la revenire, adică în ordinea inversă apelurilor (exemplul 3).
• Greșit: la numărarea apelurilor se omite primul apel.
  Corect: se numără și apelul inițial, cel din main.
• Greșit: Fibonacci recursiv naiv pentru valori mari, când există o soluție iterativă simplă.
  Corect: pentru n = 50 face miliarde de apeluri.
• Greșit: factorial(4) întoarce 4 la prima intrare în funcție.
  Corect: așteaptă rezultatul apelului cu 3.
• Greșit: toate apelurile folosesc aceeași variabilă locală n.
  Corect: fiecare apel are propria instanță.

Înainte și după

Întrebări frecvente