1. Recursivitate simpla vs. recursivitate multipla
Recursivitate simpla (liniara): functia se apeleaza exact o data pe sine. Genereaza un lant de apeluri. Exemple: factorial, suma cifrelor. Complexitate temporala: O(n).
Recursivitate multipla (binara sau n-ara): functia se apeleaza pe sine de doua sau mai multe ori in corpul ei. Genereaza un arbore de apeluri. Exemple: Fibonacci, Hanoi, backtracking. Complexitate temporala: O(2^n) sau mai mult.
Orice functie recursiva corecta are: caz de baza (conditia de oprire, fara apel recursiv), caz recursiv (argument mai simplu) si convergenta garantata catre cazul de baza.
# Recursivitate SIMPLA: un singur apel recursiv -> lant def factorial(n): if n == 0: return 1 return n * factorial(n - 1) # Recursivitate MULTIPLA: doua apeluri recursive -> arbore def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) print("fib(0) =", fib(0)) print("fib(1) =", fib(1)) print("fib(5) =", fib(5)) print("fib(7) =", fib(7))
fib(0) = 0 fib(1) = 1 fib(5) = 5 fib(7) = 13
2. Arborele de recursie si numarul de apeluri
Un arbore de recursie este reprezentarea grafica a tuturor apelurilor generate de o functie recursiva multipla. Fiecare nod = un apel; copiii unui nod = apelurile recursive generate. La recursivitate binara numarul total de noduri creste exponential. Complexitatea temporala este O(2^n).
counter = 0 def fib_count(n): global counter counter += 1 if n <= 1: return n return fib_count(n - 1) + fib_count(n - 2) for n in [5, 10, 15]: counter = 0 result = fib_count(n) print(f"fib({n}) = {result}, apeluri = {counter}")
fib(5) = 5, apeluri = 15 fib(10) = 55, apeluri = 177 fib(15) = 610, apeluri = 1973
depth = 0 def fib_trace(n): global depth indent = " " * depth print(f"{indent}-> fib({n}) apelat") if n <= 1: print(f"{indent}<- fib({n}) returneaza {n}") return n depth += 1 r1 = fib_trace(n - 1) r2 = fib_trace(n - 2) depth -= 1 result = r1 + r2 print(f"{indent}<- fib({n}) returneaza {result}") return result print("Urmarirea stivei pentru fib(4):") print("Rezultat final:", fib_trace(4))
Urmarirea stivei pentru fib(4):
-> fib(4) apelat
-> fib(3) apelat
-> fib(2) apelat
-> fib(1) apelat
<- fib(1) returneaza 1
-> fib(0) apelat
<- fib(0) returneaza 0
<- fib(2) returneaza 1
-> fib(1) apelat
<- fib(1) returneaza 1
<- fib(3) returneaza 2
-> fib(2) apelat
-> fib(1) apelat
<- fib(1) returneaza 1
-> fib(0) apelat
<- fib(0) returneaza 0
<- fib(2) returneaza 1
<- fib(4) returneaza 3
Rezultat final: 3
3. Mecanismul stivei de apeluri (call stack)
Stiva de apeluri (call stack) este o zona de memorie gestionata automat. La fiecare apel de functie se impinge un cadru de stiva (stack frame) care contine:
- Adresa de revenire — unde sa reia executia dupa
return - Parametrii functiei (copii ale valorilor)
- Variabilele locale declarate in corp
- Spatiu rezervat pentru valoarea returnata
La return, cadrul se scoate din stiva si executia continua de la adresa salvata.
# Stiva creste de jos in sus; fiecare rand = un cadru activ simultan # [BAS] fib(4): n=4, asteapta r1 de la fib(3) # fib(3): n=3, asteapta r1 de la fib(2) # fib(2): n=2, asteapta r1 de la fib(1) # [VRF] fib(1): n=1 --> returneaza 1, cadrul este scos # Dupa return: fib(2) primeste r1=1, apeleaza fib(0) # [VRF] fib(0): n=0 --> returneaza 0, cadrul este scos # fib(2) calculeaza r1+r2=1+0=1, returneaza, cadrul scos print("Adancimea maxima a stivei pentru fib(n): n cadre simultan") print("Complexitate spatiala: O(n)")
Adancimea maxima a stivei pentru fib(n): n cadre simultan Complexitate spatiala: O(n)
Complexitate spatiala: Desi numarul total de apeluri este O(2^n), adancimea maxima a stivei este O(n), deoarece orice cale radacina-frunza are lungime cel mult n. In memorie coexista simultan cel mult n+1 cadre.
Stack overflow: Recursivitate prea adanca (>~1000 apeluri simultane in Python) produce RecursionError: maximum recursion depth exceeded.
4. Memoizare — optimizarea recursivitate multiple
Memoizarea (top-down dynamic programming) salveaza rezultatul fiecarui apel recursiv intr-un dictionar. Daca acelasi apel apare din nou, se returneaza valoarea salvata fara a reface calculul. fib fara memoizare recalculeaza fib(2) de 3 ori, fib(3) de 2 ori etc.
memo = {}
counter_memo = 0
def fib_memo(n):
global counter_memo
counter_memo += 1
if n in memo:
return memo[n] # gasit in cache
if n <= 1:
memo[n] = n
return n
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
for n in [5, 10, 15]:
memo = {}
counter_memo = 0
result = fib_memo(n)
print(f"fib_memo({n}) = {result}, apeluri = {counter_memo}")
fib_memo(5) = 5, apeluri = 9 fib_memo(10) = 55, apeluri = 19 fib_memo(15) = 610, apeluri = 29
Comparatie directa pentru n=15: fib(15) fara memoizare: 1973 apeluri, O(2^n). fib_memo(15) cu memoizare: 29 apeluri, O(n). Python ofera si @functools.lru_cache care face memoizare automata.
5. Turnuri Hanoi — recursivitate multipla clasica
Turnurile Hanoi: mutam n discuri de pe tija A pe tija C, folosind B ca auxiliar, fara a pune niciodata un disc mai mare peste unul mai mic. Algoritm: (1) Muta n-1 discuri A->B. (2) Muta discul n A->C. (3) Muta n-1 discuri B->C. Recurenta: T(n) = 2*T(n-1)+1, T(1)=1. Solutia: T(n) = 2^n - 1. Complexitate optima.
def hanoi(n, sursa, destinatie, auxiliar): if n == 1: print(f" Muta disc 1: {sursa} -> {destinatie}") return hanoi(n - 1, sursa, auxiliar, destinatie) # apel 1 print(f" Muta disc {n}: {sursa} -> {destinatie}") hanoi(n - 1, auxiliar, destinatie, sursa) # apel 2 print("Turnuri Hanoi cu 3 discuri:") hanoi(3, "A", "C", "B")
Turnuri Hanoi cu 3 discuri: Muta disc 1: A -> C Muta disc 2: A -> B Muta disc 1: C -> B Muta disc 3: A -> C Muta disc 1: B -> A Muta disc 2: B -> C Muta disc 1: A -> C
7 linii = 7 mutari = 2^3 - 1. Confirmat.
6. Implementare C++ EXCLUSIV INTENSIV
La profilul intensiv, recursivitatea multipla se implementeaza si in C++. Aceeasi logica ca in Python, dar cu tipuri declarate explicit, cout << in loc de print() si ; la sfarsit de instructiune.
#include <iostream> using namespace std; // Fibonacci recursiv in C++ int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } // Turnuri Hanoi in C++ void hanoi(int n, char sursa, char destinatie, char auxiliar) { if (n == 1) { cout << " Muta disc 1: " << sursa << " -> " << destinatie << endl; return; } hanoi(n - 1, sursa, auxiliar, destinatie); cout << " Muta disc " << n << ": " << sursa << " -> " << destinatie << endl; hanoi(n - 1, auxiliar, destinatie, sursa); } int main() { cout << "fib(0) = " << fib(0) << endl; cout << "fib(5) = " << fib(5) << endl; cout << "fib(7) = " << fib(7) << endl; cout << "Turnuri Hanoi cu 3 discuri:" << endl; hanoi(3, 'A', 'C', 'B'); return 0; }
fib(0) = 0 fib(5) = 5 fib(7) = 13 Turnuri Hanoi cu 3 discuri: Muta disc 1: A -> C Muta disc 2: A -> B Muta disc 1: C -> B Muta disc 3: A -> C Muta disc 1: B -> A Muta disc 2: B -> C Muta disc 1: A -> C
Rezultatele sunt identice cu Python. Logica recursiva este aceeasi in ambele limbaje.