Recursivitate în C++

Ce este Recursivitatea?

O funcție recursivă este o funcție care se apelează pe sine însăși.

Structura unei Funcții Recursive

Copiază
1void functieRecursiva(parametri) {
2    // 1. Condiție de oprire (baza recursiei)
3    if (conditie_oprire) {
4        return rezultat_baza;
5    }
6    
7    // 2. Apel recursiv (cu parametri modificați)
8    return functieRecursiva(parametri_modificati);
9}

Exemple Clasice

Factorial

Copiază
1int factorial(int n) {
2    if (n <= 1) return 1;           // Condiție de oprire
3    return n * factorial(n - 1);     // Apel recursiv
4}
5// factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

Suma Cifrelor

Copiază
1int sumaCifre(int n) {
2    if (n == 0) return 0;
3    return n % 10 + sumaCifre(n / 10);
4}
5// sumaCifre(123) = 3 + 2 + 1 = 6

Fibonacci

Copiază
1int fibonacci(int n) {
2    if (n <= 1) return n;
3    return fibonacci(n - 1) + fibonacci(n - 2);
4}

Căutare Binară Recursivă

Copiază
1int cautareBinara(int arr[], int st, int dr, int x) {
2    if (st > dr) return -1;
3    
4    int mid = st + (dr - st) / 2;
5    
6    if (arr[mid] == x) return mid;
7    if (arr[mid] > x) return cautareBinara(arr, st, mid - 1, x);
8    return cautareBinara(arr, mid + 1, dr, x);
9}

Turnurile din Hanoi

Copiază
1void hanoi(int n, char sursa, char destinatie, char auxiliar) {
2    if (n == 1) {
3        cout << "Muta discul 1 de pe " << sursa << " pe " << destinatie << endl;
4        return;
5    }
6    
7    hanoi(n - 1, sursa, auxiliar, destinatie);
8    cout << "Muta discul " << n << " de pe " << sursa << " pe " << destinatie << endl;
9    hanoi(n - 1, auxiliar, destinatie, sursa);
10}

Recursivitate vs Iterație

Sfaturi

1. •Întotdeauna definește condiția de oprire prima
2. •Asigură-te că parametrii se modifică spre condiția de oprire
3. •Evită recursivitatea pentru probleme cu multe apeluri (folosește memoization)