De ce contează?
Ai văzut vreodată păpușile Matrioșka? Deschizi una și înăuntru găsești alta mai mică, apoi alta și mai mică, până ajungi la cea minusculă care nu se mai deschide. O funcție recursivă lucrează exact așa: ca să rezolve o problemă, deschide una mai mică din aceeași familie — până dă de cea minusculă, pe care o știe direct.
Ce este o funcție recursivă?
O funcție este recursivă când, ca să rezolve o problemă, se apelează pe ea însăși pe o problemă mai mică din aceeași familie. Nu e magie: în loc să faci tot lucrul dintr-o dată, spui „rezolvă mai întâi varianta mai mică, apoi eu adaug puțin peste rezultatul ei”.
Ca să funcționeze, ai nevoie de două ingrediente obligatorii:
- Cazul de bază — cea mai mică problemă, pe care o știi direct, fără să mai apelezi nimic. El oprește recursivitatea.
- Pasul recursiv — exprimi problema curentă prin aceeași problemă, dar mai mică, care se apropie de cazul de bază.
Dacă lipsește cazul de bază, funcția nu se oprește niciodată. Dacă pasul recursiv nu micșorează problema, la fel — nu ajungi la oprire. Ambele trebuie să existe și să fie corecte.
Exemplu pas cu pas: suma 1 + 2 + ... + n
Vrem suma primelor n numere naturale. Observă relația:
suma(n) = n + suma(n - 1)
adică suma până la n este n plus suma până la n - 1. Cazul de bază e
suma(1) = 1 (mai jos nu mai coborâm). Hai să calculăm suma(3) desfășurat:
suma(3) = 3 + suma(2)suma(2) = 2 + suma(1)suma(1) = 1(caz de bază — oprire)
Acum răspunsurile urcă înapoi, de jos în sus:
suma(1)dă1suma(2) = 2 + 1 = 3suma(3) = 3 + 3 = 6
Deci suma(3) = 6. Observă cum problema s-a tot micșorat (3 → 2 → 1) până la
cazul de bază, apoi rezultatele s-au combinat la întoarcere.
Implementare în C++
#include <iostream>
using namespace std;
int suma(int n) {
if (n == 1) return 1; // caz de baza: oprire
return n + suma(n - 1); // pas recursiv: problema mai mica
}
int main() {
cout << suma(3) << "\n"; // 6
cout << suma(5) << "\n"; // 15
cout << suma(10) << "\n"; // 55
return 0;
}Toată logica încape în două rânduri: primul e cazul de bază, al doilea e pasul recursiv. Funcția nu ține o variabilă de tip „total” ca la o buclă — totalul se construiește singur din lanțul de apeluri.
Complexitate
Pentru suma(n) se fac exact n apeluri (de la n până la 1), fiecare cu un pic
de lucru constant.
| Mărime | Timp | De ce |
|---|---|---|
suma(n) | O(n) | un apel pentru fiecare valoare de la n la 1 |
| memorie | O(n) | apelurile se rețin pe stivă până la cazul de bază |
Cum se adună apelurile pe stivă și cum se calculează exact recurența — sunt
subiectul altor lecții (stiva apelurilor și relațiile de recurență). Aici reține
doar ordinul: liniar în n.
Cele două ingrediente NU sunt opționale și nici interschimbabile. Cazul de bază spune când te oprești; pasul recursiv spune cum te apropii de el. Dacă unul lipsește sau e greșit, recursivitatea fie nu se termină, fie dă un rezultat greșit.
| apel | 3 | 2 | 1 |
start | baza |
- Lipsește cazul de bază: scrii doar
return n + suma(n - 1);fără condiția de oprire. Funcția coboară la0,-1,-2, ... la nesfârșit — recursie infinită și stack overflow. - Pasul nu se apropie de bază: apelezi
suma(n)din nou cu acelașin(sau cun + 1). Argumentul nu se micșorează, deci nu atingi niciodată cazul de bază. - Tip de return greșit: pui
voidîn loc deintși încerci să folosești valoarea, sau alegi un tip prea mic care depășește la valori mari. Funcția trebuie să returneze rezultatul, cu un tip potrivit. - Recursie unde iterația e mai simplă: pentru o sumă banală, o buclă
fore mai clară și nu încarcă stiva. Folosește recursivitatea când problema se descompune natural în subprobleme, nu de dragul ei.
Recapitulare
- O funcție recursivă se apelează pe sine pe o problemă mai mică din aceeași familie.
- Are mereu două ingrediente: cazul de bază (oprirea) și pasul recursiv (care se apropie de bază); ambele sunt obligatorii.
- Recursivitatea are sens când problema se descompune natural — altfel o buclă simplă poate fi mai clară și mai ieftină.