Bun venit la cea mai fascinantă și mai mind-bending lecție din programare! Dacă funcțiile normale sunt ca niște muncitori care-și fac treaba, funcțiile recursive sunt ca păpușile rusești (matrioșka) care se conțin pe ele însele!
1. Ce este Recursivitatea? “Oglinda în Oglindă”
Analogie cu viața reală:
Imaginează-ți că stai între două oglinzi față în față. Ce vezi?
- O oglindă arată o oglindă care arată o oglindă care arată…
- Aceasta este recursivitate în natură!
Definiție simplă:
O funcție recursivă este o funcție care se apelează pe ea însăși.
Cum gândește calculatorul:
f(5) = 5 * f(4)
= 5 * (4 * f(3))
= 5 * (4 * (3 * f(2)))
= 5 * (4 * (3 * (2 * f(1))))
= 5 * (4 * (3 * (2 * 1)))
= 1202. Structura unei Funcții Recursive: “Regulile Jocului”
Orice funcție recursivă are DOUĂ părți esențiale:
#include <iostream>
using namespace std;
void functieRecursiva(int n) {
// 1. CONDIȚIA DE BAZĂ (cazul de oprire)
// FĂRĂ ASTA - INFINITATE!
if(n <= 0) {
return; // OPREȘTE recursivitatea!
}
// 2. APELUL RECURSIV (pasul recursiv)
// cu un argument MAI MIC
functieRecursiva(n - 1);
}
int main() {
functieRecursiva(5);
return 0;
}Analogie cu scarile:
void urca_scari(int trepte) {
if(trepte == 0) {
cout << "Am ajuns sus!";
return;
}
cout << "Urc o treaptă... " << trepte << " rămase\n";
urca_scari(trepte - 1); // Urci și mai apoi urci și mai apoi...
}3. Primul Exemplu: “Contorul Invers”
#include <iostream>
using namespace std;
// Funcție care numără de la N la 1
void numaraInvers(int n) {
// CONDIȚIA DE BAZĂ
if(n <= 0) {
cout << "GATA!\n";
return;
}
// AFIȘEAZĂ numărul curent
cout << n << "... ";
// APELEAZĂ-TE cu numărul MAI MIC
numaraInvers(n - 1);
}
int main() {
cout << "=== CONTOR INVERS RECURSIV ===\n\n";
cout << "Număr de la 5 la 1:\n";
numaraInvers(5);
cout << "\nNumăr de la 3 la 1:\n";
numaraInvers(3);
return 0;
}Output:
=== CONTOR INVERS RECURSIV ===
Număr de la 5 la 1:
5... 4... 3... 2... 1... GATA!
Număr de la 3 la 1:
3... 2... 1... GATA!Cum funcționează în memorie:
numaraInvers(3)
│
├── Afișează: 3...
│ └── numaraInvers(2)
│ │
│ ├── Afișează: 2...
│ │ └── numaraInvers(1)
│ │ │
│ │ ├── Afișează: 1...
│ │ │ └── numaraInvers(0)
│ │ │ │
│ │ │ └── Afișează: GATA!
│ │ └── ← se întoarce
│ └── ← se întoarce
└── ← se întoarce4. FACTORIAL – Exemplul Clasic
Ce este factorial?
5! = 5 × 4 × 3 × 2 × 1 = 120
4! = 4 × 3 × 2 × 1 = 24
1! = 1
0! = 1 (by definition)Implementare recursivă:
#include <iostream>
using namespace std;
// Funcție care calculează factorialul
int factorial(int n) {
// CONDIȚIA DE BAZĂ
if(n <= 1) {
return 1; // 0! = 1 și 1! = 1
}
// APEL RECURSIV
return n * factorial(n - 1);
}
int main() {
cout << "=== FACTORIAL RECURSIV ===\n\n";
cout << "Factorialul lui 5:\n";
cout << "5! = " << factorial(5) << endl;
cout << "\nCalcul pas cu pas:\n";
cout << "factorial(5)\n";
cout << "= 5 * factorial(4)\n";
cout << "= 5 * (4 * factorial(3))\n";
cout << "= 5 * (4 * (3 * factorial(2)))\n";
cout << "= 5 * (4 * (3 * (2 * factorial(1))))\n";
cout << "= 5 * (4 * (3 * (2 * 1)))\n";
cout << "= 5 * (4 * (3 * 2))\n";
cout << "= 5 * (4 * 6)\n";
cout << "= 5 * 24\n";
cout << "= 120\n";
// Teste cu alte numere
cout << "\nAlte teste:\n";
cout << "0! = " << factorial(0) << endl;
cout << "1! = " << factorial(1) << endl;
cout << "6! = " << factorial(6) << endl;
return 0;
}5. FIBONACCI – “Familia de Iepuri”
Șirul lui Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Regula: f(n) = f(n-1) + f(n-2)#include <iostream>
using namespace std;
int fibonacci(int n) {
// CONDIȚIILE DE BAZĂ
if(n == 0) return 0;
if(n == 1) return 1;
// APEL RECURSIV DUBLU
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
cout << "=== FIBONACCI RECURSIV ===\n\n";
cout << "Primii 10 termeni Fibonacci:\n";
for(int i = 0; i < 10; i++) {
cout << "f(" << i << ") = " << fibonacci(i) << endl;
}
cout << "\nCum se calculează f(4):\n";
cout << "f(4) = f(3) + f(2)\n";
cout << " = (f(2) + f(1)) + (f(1) + f(0))\n";
cout << " = ((f(1) + f(0)) + 1) + (1 + 0)\n";
cout << " = ((1 + 0) + 1) + 1\n";
cout << " = (1 + 1) + 1\n";
cout << " = 2 + 1\n";
cout << " = 3\n";
return 0;
}Problema cu Fibonacci recursiv:
// ATENȚIE! Această implementare este INEFICIENTĂ!
// Calculează aceleași valori de multe ori!
// Pentru n = 5:
// f(5) = f(4) + f(3)
// f(4) = f(3) + f(2) ← f(3) calculat DIN NOU!
// f(3) = f(2) + f(1) ← f(2) calculat DIN NOU!
// ... și tot așa...6. Suma Cifrelor unui Număr
#include <iostream>
using namespace std;
int sumaCifre(int n) {
// CONDIȚIA DE BAZĂ
if(n == 0) {
return 0;
}
// APEL RECURSIV
// Ultima cifră + suma cifrelor rămase
return (n % 10) + sumaCifre(n / 10);
}
int main() {
cout << "=== SUMA CIFRELOR RECURSIV ===\n\n";
int numar = 12345;
cout << "Suma cifrelor lui " << numar << ":\n";
cout << sumaCifre(numar) << endl;
cout << "\nCum funcționează:\n";
cout << "sumaCifre(12345)\n";
cout << "= 5 + sumaCifre(1234)\n";
cout << "= 5 + (4 + sumaCifre(123))\n";
cout << "= 5 + (4 + (3 + sumaCifre(12)))\n";
cout << "= 5 + (4 + (3 + (2 + sumaCifre(1))))\n";
cout << "= 5 + (4 + (3 + (2 + (1 + sumaCifre(0)))))\n";
cout << "= 5 + (4 + (3 + (2 + (1 + 0))))\n";
cout << "= 5 + (4 + (3 + (2 + 1)))\n";
cout << "= 5 + (4 + (3 + 3))\n";
cout << "= 5 + (4 + 6)\n";
cout << "= 5 + 10\n";
cout << "= 15\n";
return 0;
}7. CMMDC (Cel Mai Mare Divizor Comun)
Algoritmul lui Euclid:
cmmdc(a, b) = cmmdc(b, a % b)
cmmdc(a, 0) = a#include <iostream>
using namespace std;
int cmmdc(int a, int b) {
// CONDIȚIA DE BAZĂ
if(b == 0) {
return a;
}
// APEL RECURSIV
return cmmdc(b, a % b);
}
int main() {
cout << "=== CMMDC RECURSIV (Euclid) ===\n\n";
cout << "cmmdc(48, 18) = " << cmmdc(48, 18) << endl;
cout << "cmmdc(56, 98) = " << cmmdc(56, 98) << endl;
cout << "cmmdc(17, 13) = " << cmmdc(17, 13) << endl;
cout << "\nExplicație pentru cmmdc(48, 18):\n";
cout << "cmmdc(48, 18)\n";
cout << "= cmmdc(18, 48 % 18) = cmmdc(18, 12)\n";
cout << "= cmmdc(12, 18 % 12) = cmmdc(12, 6)\n";
cout << "= cmmdc(6, 12 % 6) = cmmdc(6, 0)\n";
cout << "= 6\n";
return 0;
}8. Parcurgerea unui Vector
#include <iostream>
using namespace std;
// Afișează elementele unui vector recursiv
void afiseazaVector(int v[], int n) {
// CONDIȚIA DE BAZĂ
if(n == 0) {
return;
}
// Afișează PRIMUL element
cout << v[0] << " ";
// Apel recursiv cu RESTUL vectorului
afiseazaVector(v + 1, n - 1);
}
// Calculează suma elementelor
int sumaVector(int v[], int n) {
if(n == 0) {
return 0;
}
return v[0] + sumaVector(v + 1, n - 1);
}
// Găsește maximul
int maximVector(int v[], int n) {
if(n == 1) {
return v[0];
}
int maxRest = maximVector(v + 1, n - 1);
if(v[0] > maxRest) {
return v[0];
} else {
return maxRest;
}
}
int main() {
cout << "=== OPERAȚII CU VECTORI RECURSIV ===\n\n";
int vector[] = {5, 2, 8, 1, 9, 3};
int lungime = 6;
cout << "Vectorul: ";
afiseazaVector(vector, lungime);
cout << endl;
cout << "Suma: " << sumaVector(vector, lungime) << endl;
cout << "Maxim: " << maximVector(vector, lungime) << endl;
return 0;
}9. Turnurile din Hanoi
Problema clasică de recursivitate:
Avem 3 tije: A, B, C
Și n discuri de dimensiuni diferite pe tija A
Reguli:
1. Mută un singur disc odată
2. Nu pune disc mare peste disc mic
3. Mută toate discurile pe tija C#include <iostream>
using namespace std;
void hanoi(int n, char sursa, char destinatie, char auxiliar) {
// CONDIȚIA DE BAZĂ
if(n == 1) {
cout << "Mută disc 1 de pe " << sursa << " pe " << destinatie << endl;
return;
}
// APELURI RECURSIVE
// 1. Mută n-1 discuri de pe sursa pe auxiliar
hanoi(n - 1, sursa, auxiliar, destinatie);
// 2. Mută discul n de pe sursa pe destinatie
cout << "Mută disc " << n << " de pe " << sursa << " pe " << destinatie << endl;
// 3. Mută n-1 discuri de pe auxiliar pe destinatie
hanoi(n - 1, auxiliar, destinatie, sursa);
}
int main() {
cout << "=== TURNURILE DIN HANOI ===\n\n";
cout << "Soluția pentru 3 discuri:\n";
hanoi(3, 'A', 'C', 'B');
cout << "\nNumărul minim de mutări pentru n discuri: 2^n - 1\n";
cout << "3 discuri: 2^3 - 1 = 7 mutări\n";
cout << "5 discuri: 2^5 - 1 = 31 mutări\n";
cout << "64 discuri: 2^64 - 1 ≈ 18.4 trilioane mutări!\n";
return 0;
}10. Căutarea Binară Recursivă
#include <iostream>
using namespace std;
int cautareBinara(int v[], int stanga, int dreapta, int x) {
// CONDIȚIA DE BAZĂ
if(stanga > dreapta) {
return -1; // Nu s-a găsit
}
// Calculează mijlocul
int mijloc = stanga + (dreapta - stanga) / 2;
// Dacă l-am găsit
if(v[mijloc] == x) {
return mijloc;
}
// Dacă x e mai mic, căutăm în stânga
if(x < v[mijloc]) {
return cautareBinara(v, stanga, mijloc - 1, x);
}
// Dacă x e mai mare, căutăm în dreapta
return cautareBinara(v, mijloc + 1, dreapta, x);
}
int main() {
cout << "=== CĂUTARE BINARĂ RECURSIVĂ ===\n\n";
int vector[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int lungime = 10;
int caut = 13;
int pozitie = cautareBinara(vector, 0, lungime - 1, caut);
if(pozitie != -1) {
cout << "Am găsit " << caut << " la poziția " << pozitie << endl;
} else {
cout << caut << " nu a fost găsit\n";
}
return 0;
}11. Recursivitate vs Iterativitate
#include <iostream>
using namespace std;
// VERSIUNE RECURSIVĂ
int factorialRecursiv(int n) {
if(n <= 1) return 1;
return n * factorialRecursiv(n - 1);
}
// VERSIUNE ITERATIVĂ
int factorialIterativ(int n) {
int result = 1;
for(int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
int main() {
cout << "=== RECURSIV vs ITERATIV ===\n\n";
cout << "Factorial recursiv vs iterativ:\n";
cout << "5! recursiv = " << factorialRecursiv(5) << endl;
cout << "5! iterativ = " << factorialIterativ(5) << endl;
cout << "\n--- AVANTAJE ---\n";
cout << "RECURSIVITATE:\n";
cout << "+ Cod mai elegant și concis\n";
cout << "+ Natural pentru probleme recursive (arbori, divide-et-impera)\n";
cout << "+ Mai ușor de înțeles pentru anumite probleme\n\n";
cout << "ITERATIVITATE:\n";
cout << "+ Mai rapid (fără overhead de apeluri)\n";
cout << "+ Folosește mai puțină memorie (fără stack)\n";
cout << "+ Nu riscă stack overflow\n";
cout << "\n--- DEZAVANTAJE ---\n";
cout << "RECURSIVITATE:\n";
cout << "- Poate cauza stack overflow pentru adâncimi mari\n";
cout << "- Mai lent din cauza apelurilor de funcții\n";
cout << "- Consumă mai multă memorie\n\n";
cout << "ITERATIVITATE:\n";
cout << "- Cod mai lung și mai complex pentru unele probleme\n";
cout << "- Mai greu de înțeles pentru algoritmi natural recursivi\n";
return 0;
}12. Recursivitate Indirectă: “Dansul Funcțiilor”
#include <iostream>
using namespace std;
// Declarații înainte (forward declarations)
void functieA(int n);
void functieB(int n);
void functieA(int n) {
if(n <= 0) {
return;
}
cout << "A: " << n << endl;
functieB(n - 1);
}
void functieB(int n) {
if(n <= 0) {
return;
}
cout << "B: " << n << endl;
functieA(n - 1);
}
int main() {
cout << "=== RECURSIVITATE INDIRECTĂ ===\n\n";
cout << "A și B se apelează reciproc:\n";
functieA(5);
return 0;
}13. Reguli de Aur pentru Recursivitate
REGULA 1: Mereu ai nevoie de un CAZ DE BAZĂ
// GREȘIT - RECURSIVITATE INFINITĂ!
int factorialGresit(int n) {
return n * factorialGresit(n - 1); // NICIODATĂ nu se oprește!
}
// CORECT
int factorialCorect(int n) {
if(n <= 1) { // CAZ DE BAZĂ
return 1;
}
return n * factorialCorect(n - 1);
}REGULA 2: Argumentul trebuie să se apropie de cazul de bază
// GREȘIT
int recursivitateProasta(int n) {
if(n <= 0) return 0;
return recursivitateProasta(n); // La fel ca înainte - INFINIT!
}
// CORECT
int recursivitateBuna(int n) {
if(n <= 0) return 0;
return recursivitateBuna(n - 1); // Se apropie de 0!
}REGULA 3: Stack Overflow este REAL
int factorialMare(int n) {
if(n <= 1) return 1;
return n * factorialMare(n - 1);
}
// factorialMare(10000) va da STACK OVERFLOW!
// Soluție: folosește iterativ pentru numere mariREGULA 4: Divide et Impera
// Problemele bune pentru recursivitate:
// 1. Se pot împărți în subprobleme mai mici
// 2. Subproblemele sunt similare cu problema inițială
// 3. Există un caz de bază simplu14. Exerciții Practice
#include <iostream>
using namespace std;
// EXERCIȚIU 1: Inversarea unui șir
void inversareSir(char s[], int start, int end) {
if(start >= end) {
return;
}
// Schimbă caracterele
char temp = s[start];
s[start] = s[end];
s[end] = temp;
// Apel recursiv pentru restul
inversareSir(s, start + 1, end - 1);
}
// EXERCIȚIU 2: Puterea unui număr
int putere(int baza, int exponent) {
if(exponent == 0) {
return 1;
}
return baza * putere(baza, exponent - 1);
}
// EXERCIȚIU 3: Verifică palindrom
bool estePalindrom(char s[], int start, int end) {
if(start >= end) {
return true;
}
if(s[start] != s[end]) {
return false;
}
return estePalindrom(s, start + 1, end - 1);
}
int main() {
cout << "=== EXERCIȚII PRACTICE ===\n\n";
// Test inversare șir
char sir[] = "recursivitate";
cout << "Șir original: " << sir << endl;
inversareSir(sir, 0, 12);
cout << "Șir inversat: " << sir << endl;
// Test putere
cout << "\n2^5 = " << putere(2, 5) << endl;
cout << "3^4 = " << putere(3, 4) << endl;
// Test palindrom
char palindrom[] = "capac";
char nonpalindrom[] = "calculator";
cout << "\nVerificare palindrom:\n";
cout << "'capac' este palindrom? "
<< (estePalindrom(palindrom, 0, 4) ? "DA" : "NU") << endl;
cout << "'calculator' este palindrom? "
<< (estePalindrom(nonpalindrom, 0, 9) ? "DA" : "NU") << endl;
return 0;
}15. Concluzie: Când să Folosești Recursivitatea?
FOLOSEȘTE recursivitate când:
- Problema este natural recursivă (arbori, grafuri)
- Codul iterativ ar fi foarte complex
- Performanța nu este critică
- Adâncimea recursivă este mică
EVITĂ recursivitatea când:
- Adâncimea poate fi foarte mare (risc stack overflow)
- Performanța este critică
- Codul iterativ este la fel de simplu
Probleme clasice pentru recursivitate:
✅ Factorial, Fibonacci
✅ Turnurile din Hanoi
✅ Parcurgerea arborilor
✅ Divide et impera (QuickSort, MergeSort)
✅ Backtracking
// Ultimul sfat:
// Recursivitatea este ca un superputere.
// Folosește-o cu înțelepciune!
// Când e bine folosită, creează cod elegant și puternic.
// Când e prost folosită, creează probleme grave.
// Exersază, înțelege, și folosește cu discernământ!
// Happy recursive coding! 🔄🎯Remember: Recursivitatea nu este doar o tehnică de programare – este un mod de gândire! Învață să vezi problemele ca fiind compuse din versiuni mai mici ale lor însele, și vei deveni un programator mult mai bun!