Exerciții cu Recursivitate
Exemple clasice rezolvate cu explicații detaliate ale logicii recursive.
Enunț
Calculați produsul primelor n numere naturale nenule. Aceasta este una dintre cele mai simple aplicații ale recursivității.
Logica Recursivă
Cazul de bază: 0! = 1 (condiția de oprire)
Pasul recursiv: n! = n × (n-1)!
Exemplu: 5! = 5 × 4! = 5 × (4 × 3!) = 5 × 4 × 3 × 2 × 1 = 120
Traseul de Execuție
factorial(5) → 5 × factorial(4) → 5 × 4 × factorial(3) → 5 × 4 × 3 × factorial(2) → 5 × 4 × 3 × 2 × factorial(1) → 5 × 4 × 3 × 2 × 1 × factorial(0) → 5 × 4 × 3 × 2 × 1 × 1 = 120Implementare C++
#include <iostream>
using namespace std;
long long factorial(int n) {
// Cazul de bază: condiția de oprire
if (n == 0) return 1;
// Pasul recursiv: descompunem problema în subprobleme mai mici
return n * factorial(n - 1);
}
int main() {
int n;
cout<<"n="; cin>>n;
cout << "Factorialul lui " << n << " este " << factorial(n);
return 0;
}Enunț
Afișați al n-lea termen din șirul lui Fibonacci, unde fiecare număr este suma celor două precedente.
Logica Recursivă
Cazurile de bază: fib(0) = 0, fib(1) = 1
Pasul recursiv: fib(n) = fib(n-1) + fib(n-2)
Exemplu: fib(5) = fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1))
Traseul de Execuție
fib(5) = fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1)) = ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1) = 5Implementare C++
#include <iostream>
using namespace std;
int fibonacci(int n) {
// Cazurile de bază: primii doi termeni ai șirului
if (n <= 1) return n;
// Pasul recursiv: fiecare termen este suma celor doi anteriori
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n;
cout<<"n="; cin>>n;
cout << "Al " << n << "-lea termen Fibonacci este " << fibonacci(n);
return 0;
}Enunț
Calculați suma cifrelor unui număr natural dat.
Logica Recursivă
Cazul de bază: suma(0) = 0
Pasul recursiv: suma(n) = (n % 10) + suma(n / 10)
Explicație: Extragem ultima cifră (n % 10) și o adunăm cu suma cifrelor rămase (n / 10)
Traseul de Execuție
suma(12345) = 5 + suma(1234) = 5 + 4 + suma(123) = 5 + 4 + 3 + suma(12) = 5 + 4 + 3 + 2 + suma(1) = 5 + 4 + 3 + 2 + 1 + suma(0) = 15Implementare C++
#include <iostream>
using namespace std;
int sumaCifrelor(int n) {
// Cazul de bază: când nu mai avem cifre
if (n == 0) return 0;
// Pasul recursiv: ultima cifră + suma cifrelor rămase
// n % 10 extrage ultima cifră
// n / 10 elimină ultima cifră
return (n % 10) + sumaCifrelor(n / 10);
}
int main() {
int n;
cout<<"n="; cin>>n;
cout << "Suma cifrelor lui " << n << " este " << sumaCifrelor(n);
return 0;
}Enunț
Calculați Cel Mai Mare Divizor Comun a două numere folosind algoritmul lui Euclid.
Logica Recursivă
Cazul de bază: cmmdc(a, 0) = a
Pasul recursiv: cmmdc(a, b) = cmmdc(b, a % b)
Principiu: Restul împărțirii lui a la b devine noul b, iar b devine noul a
Traseul de Execuție
cmmdc(48, 18) = cmmdc(18, 12) = cmmdc(12, 6) = cmmdc(6, 0) = 6Implementare C++
#include <iostream>
using namespace std;
int cmmdc(int a, int b) {
// Cazul de bază: când b este 0, a este CMMDC-ul
if (b == 0) return a;
// Pasul recursiv: algoritmul lui Euclid
// Schimbăm: a devine b, b devine restul împărțirii
return cmmdc(b, a % b);
}
int main() {
int a, b;
cout<<"a="; cin>>a;
cout<<"b="; cin>>b;
cout << "CMMDC dintre " << a << " și " << b << " este " << cmmdc(a, b);
return 0;
}Enunț
Construiți oglinditul (inversul) unui număr natural.
Logica Recursivă
Cazul de bază: oglindit(0, inv) = inv (inv este rezultatul acumulat)
Pasul recursiv: oglindit(n, inv) = oglindit(n/10, inv*10 + n%10)
Explicație: Extragem ultima cifră și o adunăm la rezultatul inversat, apoi continuăm cu restul
Traseul de Execuție
oglindit(12345, 0) → oglindit(1234, 5) → oglindit(123, 54) → oglindit(12, 543) → oglindit(1, 5432) → oglindit(0, 54321) = 54321Implementare C++
#include <iostream>
using namespace std;
// Funcție ajutătoare cu parametru suplimentar pentru rezultat
int oglindit(int n, int inv = 0) {
// Cazul de bază: când n devine 0, inv conține rezultatul
if (n == 0) return inv;
// Pasul recursiv: construim inversul pas cu pas
// n % 10 extrage ultima cifră
// inv * 10 + n % 10 adaugă cifra la rezultat
return oglindit(n / 10, inv * 10 + n % 10);
}
int main() {
int n;
cout<<"n="; cin>>n;
cout << "Oglinditul lui " << n << " este " << oglindit(n);
return 0;
}