Recursivitatea este o tehnică fundamentală de programare în care o funcție se auto-apelează pentru a rezolva o problemă prin descompunerea acesteia în subprobleme mai mici, de același tip. Pentru a defini corect o funcție recursivă, sunt necesare două elemente: un caz de bază care oprește recursia și o regulă de recurență care exprimă soluția problemei în funcție de soluția subproblemelor. Stăpânirea recursivității este esențială pentru orice elev de liceu care se pregătește pentru Bacalaureat și pentru concursuri de informatică.
Recursivitatea este o tehnică în care o funcție se auto-apelează pentru a rezolva o problemă prin descompunerea acesteia în subprobleme mai mici, de același tip. Ideea de bază este că problema inițială poate fi redusă la una sau mai multe probleme similare, dar de dimensiune mai mică, până când se ajunge la un caz de bază care poate fi rezolvat direct, fără recursie.
De exemplu, calculul factorialului: **n! = n * (n-1)!, iar cazul de bază este 0! = 1. La fiecare apel, stiva de apeluri se adâncește; la întoarcere (backtracking**), se evaluează rezultatele.
``
int factorial(int n) {
if (n == 0) return 1;
else return n * factorial(n-1);
}
`
Explicație: pentru n=4, apelurile sunt: factorial(4) -> 4 * factorial(3) -> 3 * factorial(2) -> 2 * factorial(1) -> 1 * factorial(0) -> 1; apoi se întoarce: 1*1=1, 2*1=2, 3*2=6, 4*6=24. Atenție: stiva conține toate apelurile până la cazul de bază.
Problema: se dau 3 tije (A - sursă, B - auxiliară, C - destinație) și n discuri de dimensiuni diferite, așezate inițial pe A în ordine crescătoare (cel mai mare jos). Scopul: mutarea tuturor discurilor pe C, respectând regulile:
`
void hanoi(int n, char src, char aux, char dest) {
if (n == 1) {
cout << "Mută discul 1 de pe " << src << " pe " << dest << endl;
} else {
hanoi(n-1, src, dest, aux);
cout << "Mută discul " << n << " de pe " << src << " pe " << dest << endl;
hanoi(n-1, aux, src, dest);
}
}
`
Pentru n=3, se vor face 7 mutări (2^n - 1). Utilizăm tija auxiliară pentru a muta primele n-1 discuri.
Formula recursivă: C(n,k) = C(n-1,k-1) + C(n-1,k), cu cazuri de bază: C(n,0)=1, C(n,n)=1. Aceasta reflectă alegerea sau nealegerea unui element.
`
long long comb(int n, int k) {
if (k == 0 || k == n) return 1;
else return comb(n-1, k-1) + comb(n-1, k);
}
``
Pentru n=5, k=2: comb(5,2) = comb(4,1)+comb(4,2) = (comb(3,0)+comb(3,1)) + (comb(3,1)+comb(3,2)). Se observă că subproblemele se repetă (de exemplu comb(3,1) apare de două ori), deci este ineficient fără memoizare. O soluție mai bună folosește programare dinamică sau formula directă n!/(k!(n-k)!).
Avantaje:
Dezavantaje:
În programare, recursivitatea se poate transforma în iterație, dar uneori soluția iterativă este mai complexă.
Vrei exerciții pe lecția asta + AI care te ajută pas cu pas?
Cont gratuit — 20 întrebări AI/zi, exerciții nelimitate.