Definițiile cheie ale recursivității
Recursivitate: tehnică de programare în care o funcție se apelează pe ea însăși, direct sau indirect, pentru a rezolva o problemă prin descompunerea ei în subprobleme mai mici și asemănătoare problemei inițiale.
Caz de bază: situația (condiția) care oprește apelurile recursive; este prima verificare din funcție și trebuie atins pentru orice intrare validă. Fără el, funcția se apelează la nesfârșit și stiva se umple.
Pas recursiv: apelul funcției cu un parametru mai mic, care aduce problema tot mai aproape de cazul de bază; dacă parametrul nu scade, recurența nu se termină.
Stiva apelurilor: structură de date de tip LIFO (ultimul introdus, primul scos) în care se memorează parametrii și adresa de revenire la fiecare apel recursiv; instrucțiunile de dinaintea apelului se execută la coborâre, cele de după apel la întoarcere.
Algoritm recurent: algoritm definit prin el însuși, în funcție de o valoare mai mică a datelor (factorial, suma cifrelor, șirul lui Fibonacci, CMMDC). Orice algoritm recurent are aceeași formă: caz de bază + pas recursiv.
| Funcție | Recurența | Caz de bază | Verificare |
|---|---|---|---|
factorial(n) |
n · factorial(n − 1) | n == 0 → 1 | factorial(5) = 120 |
suma_cifre(n) |
n % 10 + suma_cifre(n / 10) | n == 0 → 0 | suma_cifre(1234) = 10 |
fib(n) |
fib(n − 1) + fib(n − 2) | n == 0 → 0; n == 1 → 1 | fib(10) = 55 |
cmmdc(a, b) |
cmmdc(b, a % b) | b == 0 → a | cmmdc(48, 18) = 6 |
numar_cifre(n) |
1 + numar_cifre(n / 10) | n < 10 → 1 | numar_cifre(12345) = 5 |
hanoi(n, s, a, d) |
hanoi(n−1, s, d, a); mutare; hanoi(n−1, a, s, d) | n == 1 → mutare directă | M(3) = 7 mutări |
suma_vector(v, i, n) |
v[i] + suma_vector(v, i + 1, n) | i == n → 0 | suma({1,2,3,4}) = 10 |
suma_matrice(a, n, m, i, j) |
a[i][j] + suma_matrice(i, j + 1); la j == m → i + 1, 0 | i == n → 0 | suma 2 × 3 = 21 |
Cum funcționează stiva: factorial(4) pas cu pas
La fiecare apel, factorial pune pe stivă valoarea parametrului n și adresa de revenire, apoi se apelează cu n - 1. Când se atinge cazul de bază, apelurile se încheie, iar rezultatele se combină în ordine inversă, la întoarcere.
| Apel | Ce se execută | Rezultat întors |
|---|---|---|
factorial(4) |
n = 4 ≠ 0, apelează factorial(3) | 4 · factorial(3) = 4 · 6 = 24 |
factorial(3) |
n = 3 ≠ 0, apelează factorial(2) | 3 · factorial(2) = 3 · 2 = 6 |
factorial(2) |
n = 2 ≠ 0, apelează factorial(1) | 2 · factorial(1) = 2 · 1 = 2 |
factorial(1) |
n = 1 ≠ 0, apelează factorial(0) | 1 · factorial(0) = 1 · 1 = 1 |
factorial(0) |
cazul de bază: n == 0, returnează 1 | 1 |
Observă: rezultatele se calculează de jos în sus, la întoarcerea din apeluri. Ordinea de coborâre pe stivă este 4 → 3 → 2 → 1 → 0, iar ordinea de urcare (deapilare) este inversă.
Algoritmii principali: pseudocod și cod C++
1. Factorialul
long long factorial(int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}
2. Suma cifrelor
int suma_cifre(int n)
{
if (n == 0)
return 0;
return n % 10 + suma_cifre(n / 10);
}
3. Șirul lui Fibonacci
long long fib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
4. CMMDC (algoritmul lui Euclid)
int cmmdc(int a, int b)
{
if (b == 0)
return a;
return cmmdc(b, a % b);
}
5. Turnurile din Hanoi
void hanoi(int n, char sursa, char aux, char destinatie)
{
if (n == 1)
{
cout << sursa << " -> " << destinatie << endl;
return;
}
hanoi(n - 1, sursa, destinatie, aux);
cout << sursa << " -> " << destinatie << endl;
hanoi(n - 1, aux, sursa, destinatie);
}
6. Suma elementelor unui vector
int suma_vector(int v[], int i, int n)
{
if (i == n)
return 0;
return v[i] + suma_vector(v, i + 1, n);
}
Ține minte: programul complet stil BAC adaugă #include <iostream>, using namespace std;, funcția main() cu citirea datelor, apelul funcției și afișarea rezultatului, încheiat cu return 0;.
Recursiv vs. iterativ: comparație
Orice problemă recursivă poate fi scrisă și iterativ (cu bucle), și invers. Varianta recursivă este mai apropiată de definiția matematică și mai lizibilă pentru problemele recurente; varianta iterativă folosește mai puțină memorie (nu umple stiva) și este adesea mai rapidă.
| Criteriu | Recursiv | Iterativ |
|---|---|---|
| Citirea codului | Urmează definiția matematică (n! = n · (n-1)!) | Necesită o variabilă acumulator și o buclă |
| Memorie | Ocupă stiva cu câte un cadru pe apel | O singură variabilă, memorie constantă |
| Risc | Depășirea stivei pentru n mare | Niciun risc de depășire a stivei |
| Folosit când | Probleme definite recurent, parcurgeri, divide et impera | Prelucrări simple, valori mari, eficiență la memorie |
Factorial: recursiv vs. buclă
long long factorial(int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}
long long factorial(int n)
{
long long p = 1;
for (int i = 2; i <= n; i++)
p = p * i;
return p;
}
Comparație: pentru n = 10, ambele variante afișează 3628800. La test sunt acceptate ambele, dacă rezultatul este corect; varianta iterativă evită umplerea stivei pentru valori mari.
Reguli și greșeli frecvente de evitat
Regula de aur: fiecare funcție recursivă trebuie să aibă un caz de bază clar și un pas recursiv care reduce problema către acel caz.
| Greșeală frecventă | Consecință | Corect |
|---|---|---|
| Lipsa cazului de bază | Recursie infinită: stiva se umple, programul se blochează | Prima instrucțiune din funcție este cazul de bază |
Caz de bază greșit (n < 0 în loc de n == 0) |
Rezultate incorecte sau apeluri infinite | Cazul de bază trebuie să se atingă pentru orice intrare validă |
Pas recursiv care nu reduce problema (n + 1) |
Recursie infinită | Parametrul apelului trebuie să se apropie de cazul de bază |
Tip de return int la factorial |
Depășire pentru n ≥ 13 | long long pentru factorial și Fibonacci |
| Afișarea plasată greșit față de apel | Ordinea valorilor afișate se inversează | Înainte de apel = la coborâre; după apel = la întoarcere |
| Vector transmis fără lungime | Funcția nu știe unde se oprește | Parametrii (v, i, n) cu cazul de bază i == n |
Sinteza regulilor de scriere a unei funcții recursive
- Pasul 1: identifică cazul (cazurile) în care problema are răspuns imediat și scrie-l ca bază.
- Pasul 2: scrie pasul recursiv, apelând funcția cu o problemă mai mică.
- Pasul 3: combină rezultatul apelului cu elementul curent (adunare, comparație, afișare).
- Pasul 4: alege tipul de return potrivit și validează intrarea.
- Pasul 5: verifică pe un exemplu mic, urmărind stiva de apeluri.
Recursivitate vs. iterație: recursivitatea este naturală pentru probleme definite recurent și pentru parcurgeri; iterația evită riscul umplerii stivei și este mai eficientă la memorie. În evaluare, ambele variante sunt acceptate dacă rezultatul este corect.
Ce trebuie să știi pentru test
Lista de verificare înainte de test
- Să scrii din memorie cazul de bază și pasul recursiv pentru: factorial, suma cifrelor, Fibonacci, CMMDC, numărul de cifre, suma elementelor unui vector.
- Să construiești un program complet stil BAC:
#include <iostream>,using namespace std;, funcții înainte de main, citire, apel, afișare,return 0;. - Să explici mecanismul stivei: ce se pune pe stivă la fiecare apel și în ce ordine se execută instrucțiunile de dinaintea și de după apel.
- Să urmărești pe hârtie execuția unei funcții recursive pentru o valoare mică (de exemplu factorial(4)).
- Să alegi tipul de return corect (
intsaulong long) și să tratezi cazurile limită: n = 0, n = 1. - Să scrii o parcurgere recursivă de vector și de șir (sumă, maxim, afișare inversă).
- Să compari varianta recursivă cu cea iterativă și să spui când preferi una sau cealaltă.
Greșeli frecvente la test
| Greșeala | Ce pierzi | Cum o eviți |
|---|---|---|
Lipsa #include <iostream> sau a return 0; |
Eroare de compilare, punctaj pierdut la întregul item | Scrie întâi scheletul complet al programului, apoi completează funcțiile |
| Caz de bază greșit (n < 0 în loc de n == 0) | Rezultate incorecte sau apeluri infinite | Testează funcția cu n = 0 și n = 1 înainte de predare |
| Pas recursiv care nu reduce problema (n + 1) | Recursie infinită, stiva se umple | Verifică dacă parametrul apelului se apropie de cazul de bază |
Factorial cu int în loc de long long |
Depășire pentru n ≥ 13 | Folosește long long pentru factorial și Fibonacci |
| Afișare plasată greșit față de apel | Ordinea valorilor afișate se inversează | Înainte de apel = la coborâre; după apel = la întoarcere |
| Nu tratezi cazul n = 0 la vectori și șiruri | Funcția nu se oprește sau citește în afara structurii | Scrie cazul de bază i == n pentru vectori și folosește strlen(s) pentru șiruri |
Exerciții de recapitulare (mini-provocări) cu rezolvare
Provocarea 1: Numărul de cifre
Scrie funcția recursivă numar_cifre(n) care returnează numărul de cifre al lui n. Cazul de bază este n < 10, iar pasul recursiv elimină ultima cifră cu n / 10.
int numar_cifre(int n)
{
if (n < 10)
return 1;
return 1 + numar_cifre(n / 10);
}
Verifică: numar_cifre(12345) = 1 + numar_cifre(1234) = ... = 5.
Provocarea 2: Maximul dintr-un vector
Scrie funcția recursivă maxim(v, i, n) care returnează cel mai mare element dintr-un vector, parcurgând vectorul de la indicele i. Cazul de bază este un singur element (i == n - 1).
int maxim(int v[], int i, int n)
{
if (i == n - 1)
return v[i];
int m = maxim(v, i + 1, n);
if (v[i] > m)
m = v[i];
return m;
}
Verifică: pentru v = {3, 9, 2, 7} și n = 4, maximul este 9.
Provocarea 3: Suma cifrelor pare
Scrie funcția recursivă suma_cifre_pare(n) care returnează suma cifrelor pare ale lui n. Pentru n = 2468 rezultatul este 20, iar pentru n = 1357 rezultatul este 0.
int suma_cifre_pare(int n)
{
if (n == 0)
return 0;
int s = suma_cifre_pare(n / 10);
if (n % 2 == 0)
s = s + n % 10;
return s;
}
Verifică: suma_cifre_pare(2468) = 2 + 4 + 6 + 8 = 20.
Aprofundare: eficiență și tehnici avansate
Memoizarea. Pentru Fibonacci, stocarea rezultatelor calculate într-un vector reduce complexitatea de la exponențial la liniar: înainte de fiecare apel verificăm dacă valoarea este deja cunoscută.
Adâncimea stivei. Fiecare apel consumă memorie; pentru valori mari, recursivitatea liniară poate umple stiva. Divide et impera reduce adâncimea la log₂(n).
CMMMC prin CMMDC. cmmmc(a, b) = (a / cmmdc(a, b)) * b; împărțirea înainte de înmulțire evită depășirea.
Aplicații reale. Recursivitatea apare în parcurgerea fișierelor (foldere în foldere), în algoritmi de căutare (binary search), în compresia datelor (coduri Huffman) și în generarea de combinații.
Mini-plan de repetiție pentru evaluarea finală
Ce să rescrii din memorie
- Cele opt funcții din tabelul rezumativ, cu caz de bază și pas recursiv.
- Programul complet BAC: include, namespace, main, citire, apel, afișare, return 0.
- Mecanismul stivei: ordinea coborârii și a întoarcerii.
Cum să te verifici
- Testează fiecare funcție cu exemplele din tabel: 120, 10, 55, 6, 5, 7 mutări, 10, 21.
- Testează cazurile limită: n = 0, n = 1, vector cu un singur element, matrice 1 × 1.
- Rescrie apoi o problemă integrată completă (număr + vector + șir) și verific-o.