1
1. Ce este recursivitatea?
Recursivitatea este tehnica prin care o functie se apeleaza pe sine insasi pentru a rezolva o versiune mai mica a aceleiasi probleme. Executia se opreste cand se atinge cazul de baza, un caz suficient de simplu incat sa fie rezolvat direct, fara un nou apel recursiv.
Structura generala a unei functii recursive:
def functie_recursiva(parametru): # Cazul de baza: problema cea mai simpla if <conditie_stop>: return <valoare_directa> # Cazul recursiv: problema mai mare -> problema mai mica return <combinatie> + functie_recursiva(parametru_mai_mic)
Analogie sigura:
Gandeste-te la un dictionar: cauti cuvantul "algoritm" si definitia spune "vezi: procedura"; cauti "procedura" si spune "vezi: secventa de pasi"; cauti "secventa" si gasesti explicatia directa. Fiecare cautare te redirectioneaza la o intrare mai simpla, pana ajungi la una care nu mai are redirectionari (cazul de baza).
2
2. Cazul de baza — ancora recursiei
Cazul de baza este conditia care opreste recursivitatea. Fara el, functia s-ar apela la infinit, epuizand memoria disponibila pentru stiva de apeluri. In Python, aceasta produce o eroare de tip
RecursionError.
GRESIT — functie recursiva fara caz de baza:
# ATENTIE: acest cod produce RecursionError! def numar_infinit(n): return n + numar_infinit(n - 1) # niciodata nu se opreste
CORECT — cu caz de baza explicit:
def numar_corect(n): if n == 0: # caz de baza: stop! return 0 return n + numar_corect(n - 1) # caz recursiv: n mai mic
Regula: la fiecare apel recursiv, argumentul trebuie sa se apropie de cazul de baza (sa scada, sa creasca spre limita, sau sa simplifice problema). Altfel, recursivitatea nu converge.
3
3. Factorial recursiv — exemplul canonic
Definitia matematica a factorialului se preteaza perfect la implementarea recursiva:
0! = 1 (cazul de baza)
n! = n × (n−1)! pentru n ≥ 1 (cazul recursiv)
0! = 1 (cazul de baza)
n! = n × (n−1)! pentru n ≥ 1 (cazul recursiv)
# Factorial recursiv in Python def factorial(n): if n == 0: # caz de baza: 0! = 1 return 1 return n * factorial(n - 1) # caz recursiv: n! = n * (n-1)! print("factorial(0) =", factorial(0)) print("factorial(1) =", factorial(1)) print("factorial(5) =", factorial(5)) print("factorial(10) =", factorial(10))
Output real (rulat cu python):
factorial(0) = 1 factorial(1) = 1 factorial(5) = 120 factorial(10) = 3628800
Urmarirea stivei de apeluri pentru factorial(4):
factorial(4) apelat
factorial(3) apelat
factorial(2) apelat
factorial(1) apelat
factorial(0) apelat
caz de baza: return 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
Observa ca apelurile se adancesc pana la cazul de baza (coborare), apoi rezultatele se combina la intoarcere (urcare). Aceasta structura dubla (dus-intors) este caracteristica recursivitati.
Complexitate factorial recursiv: O(n) timp, O(n) spatiu (stiva creste cu n cadre de apel).
4
4. Sirul Fibonacci recursiv
Sirul Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Definitia matematica recursiva:
fib(0) = 0 (caz de baza 1)
fib(1) = 1 (caz de baza 2)
fib(n) = fib(n−1) + fib(n−2) pentru n ≥ 2 (caz recursiv)
Definitia matematica recursiva:
fib(0) = 0 (caz de baza 1)
fib(1) = 1 (caz de baza 2)
fib(n) = fib(n−1) + fib(n−2) pentru n ≥ 2 (caz recursiv)
# Fibonacci recursiv in Python def fibonacci(n): if n == 0: # caz de baza 1 return 0 if n == 1: # caz de baza 2 return 1 return fibonacci(n - 1) + fibonacci(n - 2) # caz recursiv for i in range(10): print(f"fibonacci({i}) = {fibonacci(i)}")
Output real (rulat cu python):
fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(2) = 1 fibonacci(3) = 2 fibonacci(4) = 3 fibonacci(5) = 5 fibonacci(6) = 8 fibonacci(7) = 13 fibonacci(8) = 21 fibonacci(9) = 34
Atentie la complexitate! Fibonacci recursiv naiv are complexitate O(2n) — exponentiala. Pentru fib(40), se fac peste un miliard de apeluri, deoarece aceeasi subproblema (ex. fib(20)) este calculata de mii de ori. Aceasta problema se rezolva prin memoizare sau programare dinamica (lecti viitoare).
5
5. Suma cifrelor — recursivitate pe cifre
Suma cifrelor unui numar natural: extragem ultima cifra (
n % 10), o adaugam, si apelam recursiv pentru restul numarului (n // 10). Cazul de baza: un numar cu o singura cifra este chiar suma sa.
# Suma cifrelor unui numar - varianta recursiva def suma_cifre(n): if n < 10: # caz de baza: cifra unica return n return n % 10 + suma_cifre(n // 10) # ultima cifra + suma restului print("suma_cifre(7) =", suma_cifre(7)) print("suma_cifre(123) =", suma_cifre(123)) print("suma_cifre(9876) =", suma_cifre(9876))
Output real (rulat cu python):
suma_cifre(7) = 7 suma_cifre(123) = 6 suma_cifre(9876) = 30
Urmarire manuala pentru suma_cifre(123):
suma_cifre(123) = 3 + suma_cifre(12)
suma_cifre(12) = 2 + suma_cifre(1)
suma_cifre(1) = 1 (caz de baza: 1 < 10)
intoarcere:
suma_cifre(12) = 2 + 1 = 3
suma_cifre(123) = 3 + 3 = 6
6
6. Factorial recursiv in C++ EXCLUSIV INTENSIV
⚡ Sectiune exclusiv pentru intensiv informatica
La profilul intensiv vei implementa recursivitatea si in C++. Diferente fata de Python: tipurile se declara explicit; functia recursiva are tipul de retur precizat in antet; nu exista limita dinamica de stiva setata software (Python ~1000 cadre), dar stiva hardware este limitata — apeluri prea adanci produc stack overflow.
#include <iostream> using namespace std; long long factorial(int n) { if (n == 0) return 1; // caz de baza: 0! = 1 return n * factorial(n - 1); // caz recursiv } int main() { cout << "factorial(0) = " << factorial(0) << endl; cout << "factorial(1) = " << factorial(1) << endl; cout << "factorial(5) = " << factorial(5) << endl; cout << "factorial(10) = " << factorial(10) << endl; return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
factorial(0) = 1 factorial(1) = 1 factorial(5) = 120 factorial(10) = 3628800
Comparatie Python vs C++: Structura recursiva este identica. In C++ declari tipul (
long long pt valori mari) si parametrul (int n). In Python, tipurile sunt implicite. Algoritmul — cazul de baza + cazul recursiv — este acelasi in ambele limbaje.