Recursivitate si metode recursive de rezolvare

Recursivitatea reprezinta o tehnica fundamentala in programare, prin care o functie se autoapeleaza pentru a rezolva o problema prin descompunerea acesteia in subprobleme mai mici, similare cu problema originala. O functie recursiva trebuie sa contina cel putin o conditie de oprire (caz de baza) si un apel recursiv care aduce problema mai aproape de cazul de baza. Fara caz de baza, functia va rula la infinit, generand o eroare de tip stack overflow.

In contextul programarii, recursivitatea este adesea utilizata pentru parcurgerea arborilor, sortare (QuickSort, MergeSort), calculul factorialului, sirul lui Fibonacci, sau rezolvarea problemelor de tip divide et impera. Avantajele includ scrierea unui cod mai concis si mai usor de inteles, in special pentru structuri de date ierarhice. Dezavantajele pot fi consumul mare de memorie (stack) si timpul de executie mai lent fata de solutii iterative, din cauza overhead-ului apelurilor de functii.

In programare, fiecare apel recursiv genereaza un nou cadru pe stiva de executie, care contine variabilele locale si adresa de return. Cand conditia de oprire este indeplinita, functia returneaza un rezultat si cadrele sunt sterse treptat. Este important sa se inteleaga ca orice solutie recursiva poate fi transformata intr-una iterativa (folosind stive sau bucle), dar uneori simplitatea solutiei recursive este preferabila.

In Bacalaureat, elevii trebuie sa stie sa scrie functii recursive simple (factorial, suma cifrelor, cmmdc) si sa analizeze complexitatea acestora. De asemenea, este important sa inteleaga notiunea de backtracking, care este o metoda recursiva de cautare sistematica a solutiilor. Pentru a deveni proficienti, recomand exersarea implementarii recursive a unor algoritmi clasici si analiza manuala a stivei de apeluri.

Exemple

• Exemplul 1: Factorialul unui numar. Definitie: n! = 1 * 2 * ... * n, iar recursiv: n! = n * (n-1)! pentru n>0, iar 0! = 1. Implementare in C++: int factorial(int n) { if (n==0) return 1; else return n * factorial(n-1); } Pentru n=4, stiva: factorial(4) -> 4*factorial(3) -> 3*factorial(2) -> 2*factorial(1) -> 1*factorial(0) returneaza 1, apoi se inmulteste pe rand: 1*1=1, 2*1=2, 3*2=6, 4*6=24.
• Exemplul 2: Suma cifrelor unui numar natural. Recursiv: suma_cifre(n) = n % 10 + suma_cifre(n/10), iar caz de baza: daca n<10, returneaza n. Implementare: int sumaCifre(int n) { if (n < 10) return n; else return n % 10 + sumaCifre(n / 10); } Pentru n=123, apelurile: sumaCifre(123) -> 3 + sumaCifre(12) -> 2 + sumaCifre(1) -> 1, rezultatul final 3+2+1=6.
• Exemplul 3: Algoritmul lui Euclid pentru CMMDC. Definitie recursiva: cmmdc(a,b) = a, daca b=0; altfel cmmdc(b, a % b). Cod: int cmmdc(int a, int b) { if (b == 0) return a; else return cmmdc(b, a % b); } De exemplu, pentru a=12, b=18: cmmdc(12,18) -> cmmdc(18,12%18=12) -> cmmdc(12,18%12=6) -> cmmdc(6,12%6=0) -> returneaza 6.

Concepte cheie: Caz de baza (baza recursivitatii), Autoapelul functiei, Stiva de apeluri (call stack), Divide et impera (impartirea problemei in subprobleme), Transformarea recursiv-iterativ