De ce contează?
Ai văzut vreodată o păpușă matrioșka? O deschizi și înăuntru e o păpușă identică, dar mai mică. O deschizi și pe aceea, și iar găsești una mai mică — până ajungi la cea minusculă, care nu se mai deschide. Recursivitatea gândește exact așa: ca să rezolvi problema mare, o reduci la aceeași problemă, dar pe o intrare mai mică. Te oprești când ajungi la „păpușa care nu se mai deschide" — cazul de bază.
Intuiția
Vrei suma 1 + 2 + ... + n. În loc să strângi totul dintr-o dată, observă că suma
până la n este pur și simplu n adunat la suma până la n-1. Adică problema
pentru n conține în ea aceeași problemă, dar pentru n-1. Continui să cobori:
n-1 se sprijină pe n-2, și tot așa, până la s(0) = 0, unde nu mai rămâne
nimic de adunat. Acesta e tiparul recursiv: problema mare = o problemă mai mică + un pas.
Vezi cum funcționează
Folosește ← și → ca să pășești prin algoritm, sau Redă pentru animație. Urmărește două faze: întâi apelurile se adaugă pe stivă (coborârea spre bază), apoi rezultatele se întorc de jos în sus (urcarea).
Prima idee: o buclă simplă. s = 0; for (int i = 1; i <= n; i++) s += i;. Pentru
suma 1..n merge perfect și e chiar mai economică ca memorie.
Bucla e ușoară aici fiindcă problema e liniară. Dar la baraj apar structuri care se
ramifică: un arbore cu fii, o împărțire în jumătăți (divide-et-impera), o stare care
depinde de stări mai mici (programare dinamică). Acolo „următorul pas" nu e un simplu
i++ — trebuie să intri în mai multe sub-probleme deodată, iar bucla devine greoaie
sau imposibil de scris natural.
Definește rezultatul în funcție de el însuși, pe o intrare mai mică, plus o
oprire. Pentru sumă: s(n) = n + s(n-1), iar oprirea e s(0) = 0. Nu mai descrii
cum parcurgi totul — descrii doar legătura dintre un nivel și cel de sub el.
Scrii o funcție s(n) care: dacă n == 0 întoarce 0 (cazul de bază), altfel
întoarce n + s(n-1) (pasul recursiv). Restul îl face calculatorul, repetând singur
reducerea până la bază și adunând la întoarcere.
Algoritmul pas cu pas
Să urmărim s(4). Mai întâi coborârea: fiecare apel îl cheamă pe cel mai mic și
îl așteaptă, punând un cadru pe stivă, până la cazul de bază s(0) = 0.
Când s(0) întoarce 0, oprirea declanșează urcarea: rezultatele se întorc de
jos în sus, fiecare adunând valoarea lui n la ce a primit de dedesubt.
| rezultat | 0 | 1 | 3 | 6 | 10 |
| apel | s(0) | s(1) | s(2) | s(3) | s(4) |
baza | final |
Deci s(4) = 4 + s(3) = 4 + 3 + 2 + 1 + 0 = 10. Reține mecanismul stivei: apelurile
se adaugă la coborâre (toate cele 5 cadre coexistă, niciunul n-a terminat încă),
iar cazul de bază e singurul care poate întoarce o valoare fără să mai aștepte. De
acolo stiva se golește invers (LIFO): ultimul intrat, primul care iese.
Recursia a desfăcut o problemă în sub-probleme identice mai mici și a recombinat soluțiile la întoarcere — exact ideea pe care o vei reîntâlni la divide-et-impera (împarți în jumătăți) și la programarea dinamică (un rezultat se sprijină pe rezultate mai mici).
Când recursia se ramifică: Fibonacci
s(n) face un singur apel recursiv, deci stiva e un lanț drept: n+1 apeluri,
O(n). Dar multe probleme de baraj nu sunt liniare — se ramifică. Fibonacci e exemplul
clasic: fib(n) = fib(n-1) + fib(n-2), cu fib(0) = 0 și fib(1) = 1. Aici fiecare
apel cheamă doi copii, iar apelurile nu mai formează un lanț, ci un arbore.
Privește arborele: fib(2) apare de două ori, iar pentru n mai mare aceleași
valori se recalculează de tot mai multe ori. De aici O(2^n) — explozie exponențială
de muncă repetată. Declicul (pe care îl vei numi mai târziu memoizare, apoi
programare dinamică) e simplu: calculezi fiecare fib(k) o singură dată și îl
reții, coborând costul înapoi la O(n).
Implementare C++
#include <iostream>
using namespace std;
// suma 1 + 2 + ... + n, definita recursiv
long long s(int n) {
if (n == 0) return 0; // caz de baza: nu mai e nimic de adunat
return n + s(n - 1); // pas recursiv: n plus suma pana la n-1
}
int main() {
cout << s(4) << endl; // 10
cout << s(100) << endl; // 5050
return 0;
}Funcția nu conține nicio buclă: descrie doar legătura s(n) = n + s(n-1) și oprirea
s(0) = 0. Calculatorul face restul, coborând și apoi urcând prin stiva de apeluri.
Complexitate
| Recursie | Timp | Spațiu (adâncime stivă) |
|---|---|---|
Liniară — s(n) | O(n) | O(n) |
Ramificată naivă — fib(n) | O(2^n) | O(n) |
Ramificată cu memoizare — fib(n) | O(n) | O(n) |
La s(n) sunt n+1 apeluri, fiecare cu o singură adunare, deci timpul e O(n). Spațiul
e tot O(n), pentru că toate cele n+1 cadre stau simultan pe stivă până se atinge
baza (varianta cu buclă ar folosi O(1), o singură variabilă — recursia plătește memoria
pentru eleganță). La fib(n) naiv timpul explodează la O(2^n) din munca repetată, dar
adâncimea stivei rămâne O(n): pe orice ramură cobori cel mult n niveluri deodată.
Capcanele clasice ale recursiei la baraj:
- Lipsa cazului de bază. Dacă uiți
if (n == 0) return 0;, funcția apeleazăs(-1),s(-2)... la nesfârșit → recursie infinită → stack overflow. - Caz de bază greșit. Scrii
if (n == 1) return 1;în loc den == 0. La un apel cun = 0, condiția e falsă, se coboară las(-1)și iar nu se oprește. Cazul de bază trebuie să fie chiar valoarea la care recursia ar trece „dincolo". - Adâncime prea mare. Chiar cu caz de bază corect, un
nfoarte mare (de ordinul sutelor de mii) îngrămădește prea multe cadre pe stivă → tot stack overflow. Când adâncimea recursiei e uriașă, treci la varianta iterativă sau la o reformulare.