Subprograme Recursive în C++

Teorie despre subprograme recursive

Subprogramele recursive sunt funcții care se autoapelează pentru a rezolva o problemă. Ele sunt utile atunci când problema poate fi împărțită în subprobleme de același tip.

O funcție recursivă trebuie să aibă un caz de bază care oprește recursivitatea. În lipsa acestuia, funcția poate intra într-un ciclu infinit și poate cauza stack overflow.

Exemplu de caz de bază: pentru factorial, dacă n==0, returnăm 1.

Al doilea element este apelul recursiv: funcția se apelează pe sine cu parametri mai simpli, până când se ajunge la cazurile de bază.

Recursivitatea poate fi directă (funcția se apelează pe sine) sau indirectă (funcția A apelează B, care apelează A).

Fiecare apel recursiv creează un cadru activ în stiva de apeluri, care reține valorile parametrilor și variabilelor locale.

Execuția unui apel recursiv continuă după autoapel, începând cu instrucțiunea următoare apelului.

Stiva de apeluri este importantă pentru înțelegerea recursivității: ultima funcție apelată este prima care își termină execuția (LIFO).

Recursivitatea este utilă pentru probleme matematice (factorial, Fibonacci), algoritmi de sortare (merge sort, quick sort) și parcurgerea structurilor de date (liste, arbori).

Avantaje: cod mai scurt, logică clară pentru probleme repetitive.

Dezavantaje: poate consuma multă memorie, performanță mai scăzută decât iterativ în unele cazuri.

Exemple de funcții recursive: calcul factorial, calcul suma numerelor naturale, afișarea cifrelor unui număr, inversarea unui șir de caractere.

Este important să înțelegem cum se modifică stiva la fiecare apel și cum se construiește rezultatul pe măsură ce execuția revine din apelurile recursive.

Debugging-ul recursivității se face de obicei urmărind stiva de apeluri și output-ul fiecărui pas.

Recursivitatea poate fi combinată cu condiții și bucle interne pentru a rezolva probleme mai complexe.

Exercițiile practice ajută la consolidarea conceptului și la înțelegerea fluxului de execuție.

În concluzie, recursivitatea este un instrument puternic, dar trebuie folosit cu atenție la cazurile de bază și gestionarea stivei de apeluri.

Exemple de funcții recursive rezolvate

Funcția 1 – Exemplu cu stivă și output (cadre active)

void f1(int x) {
    while(x>2) {
        x--;
        f1(x);
    }
    cout << x;
}

int main() {
    f1(5);
}

Output final: 1 2 2 1 2 ✅

Funcția 2 – Exemplu simplu

void f2(int x) {
    if(x<=0) return;
    cout << x << " ";
    f2(x-1);
}

int main() {
    f2(4);
}

Output final: 4 3 2 1 ✅

Funcția 3 – Exemplu simplu

void f3(int x) {
    if(x<=1) return;
    f3(x-1);
    cout << x << " ";
}

int main() {
    f3(4);
}

Output final: 2 3 4 ✅

Funcții recursive – execuție pas cu pas

void exemplu3a(int x) {
    if(x<=0) return;
    exemplu3a(x-1);
    cout << x << " ";
}
int main() { exemplu3a(4); }

void exemplu3b(int x) {
    if(x<=0) return;
    exemplu3b(x-1);
    cout << x*x << " ";
}
int main() { exemplu3b(3); }

int factorial(int n) {
    if(n==0) return 1;
    return n * factorial(n-1);
}
int main() { cout << factorial(5); }

int suma(int n) {
    if(n==0) return 0;
    return n + suma(n-1);
}
int main() { cout << suma(5); }

int fibonacci(int n) {
    if(n==0) return 0;
    if(n==1) return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}
int main() { cout << fibonacci(6); }

int maxim(int v[], int n) {
    if(n==1) return v[0];
    int m = maxim(v, n-1);
    if (v[n-1] > m) 
         return v[n-1];
    else return m;
}
int main() {
    int v[] = {3,7,2,9,4};
    cout << maxim(v,5);
}

Funcții recursive – exerciții 10–14

void afisCifre(int n) {
    if(n<10) {
        cout << n << " ";
    } else {
        afisCifre(n/10);
        cout << n%10 << " ";
    }
}
int main() { afisCifre(1234); }

void inversare(char s[], int i) {
    if(i < 0) return;
    cout << s[i];
    inversare(s, i - 1);
}

int main() {
    char s[30] = "ABC";
    inversare(s, 2); // afișează CBA
}

int putere(int a, int n) {
    if(n==0) return 1;
    return a*putere(a,n-1);
}
int main() { cout << putere(2,3); }

int nrCifre(int n) {
    if(n==0) return 0;
    return 1+nrCifre(n/10);
}
int main() { cout << nrCifre(12345); }

int oglindit(int n, int rev=0) {
    if(n==0) return rev;
    return oglindit(n/10, rev*10+n%10);
}
int main() { cout << oglindit(1234); }

#include <iostream>
using namespace std;

int factorial(int x) {
    if (x == 0) return 1;
    return x * factorial(x - 1);
}

int main() {
    cout << factorial(5); // Output: 120
    return 0;
}

#include <iostream>
using namespace std;

void afisCifreStanga(int n) {
    if (n == 0) return;
    afisCifreStanga(n / 10);
    cout << n % 10 << " ";
}

int main() {
    afisCifreStanga(1234); // Output: 1 2 3 4
    return 0;
}

#include <iostream>
using namespace std;

int sumaPrimeleN(int n) {
    if (n == 0) return 0;
    return n + sumaPrimeleN(n - 1);
}

int main() {
    cout << sumaPrimeleN(5); // Output: 15
    return 0;
}

Exerciții propuse

1. Funcția 1:Ce afiseaza programul C++ de mai jos?

   
   void pozitie(long n, int idx) {
       if(n != 0) {
           if(n % 3 != 0) {
               cout << idx;
           }
           pozitie(n / 3, idx + 1);
       }
   }
   int main() {
       pozitie(121, 1);
   }
   

2. Funcția 2: Ce afiseaza programul C++ de mai jos?

   
   void afisCifre(long n) {
       cout << n % 10;
       if(n != 0) {
           afisCifre(n / 100);
           cout << n % 10;
       }
   }
   int main() {
       afisCifre(12345);
   }
   

3. Funcția 3:Ce afiseaza programul C++ de mai jos?

   
   void cifreSpeciale(int x) {
       if(x > 0) {
           if(x % 4 == 0) {
               cout << 'A';
               cifreSpeciale(x - 1);
           } else {
               cifreSpeciale(x / 3);
               cout << 'B';
           }
       }
   }
   int main() {
       cifreSpeciale(26);
   }
   

4. Funcția 4: Ce afiseaza programul C++ de mai jos?

   
   void incrementRec(int n, int x) {
       if(x > n) cout << 0;
       else if(x % 4 <= 1) incrementRec(n, x + 1);
       else {
           incrementRec(n, x + 3);
           cout << 1;
       }
   }
   int main() {
       incrementRec(15, 2);
   }
   

5. Funcția 5: Ce afiseaza programul C++ de mai jos?

   
   void simbolRec(int a, int b) {
       if(a <= b) {
           simbolRec(a + 1, b - 2);
           cout << '*';
       } else {
           cout << b;
       }
   }
   int main() {
       simbolRec(3, 17);
   }
   

6. Funcția 6: Ce afiseaza programul C++ de mai jos?

   
   int divSucc(int a, int b) {
       if(a < 1) return -1;
       else if(a % b == 0) return 1 + divSucc(a / b, b);
       else return 0;
   }
   int main() {
       cout << divSucc(15, 2) << " " << divSucc(128, 2);
   }
   

7. Funcția 7: Ce afiseaza programul C++ de mai jos?

   
   void afisPare(long n) {
       if(n != 0) {
           if(n % 2 == 0) cout << n % 10;
           afisPare(n / 10);
       }
   }
   int main() {
       afisPare(12345);
   }
   

8. Funcția 8: Ce afiseaza programul C++ de mai jos?

   
   int countDigit(long n, int k) {
       if(n == 0) return 0;
       if(n % 10 == k) return 1 + countDigit(n / 10, k);
       else return countDigit(n / 10, k);
   }
   int main() {
       cout << countDigit(1213111, 1);
   }
   

9. Funcția 9: Ce afiseaza programul C++ de mai jos?

   
   int sumIndex(int n, int y) {
       if(n == 0) return 0;
       y = y + 1;
       return y + sumIndex(n - 1, y);
   }
   int main() {
       cout << sumIndex(3, 1);
   }
   

10. Funcția 10: Ce afiseaza programul C++ de mai jos?

    
    int minDigit(int n) {
        if(n == 0) return 9;
        int c = minDigit(n / 10);
        if(n % 10 < c) return n % 10;
        else return c;
    }
    int main() {
        cout << minDigit(23159);
    }
    

11. Funcția 11: Ce afiseaza programul C++ de mai jos?

    
    long g(long x) {
        if(x > 9) return (x/10 + x%10);
        else return x;
    }
    long f(int c) {
        if(c < 1) return 1;
        else return g(c + f(c - 1));
    }
    int main() {
        cout << f(6) << " " << g(11);
    }
    

12. Funcția 12: Ce afiseaza programul C++ de mai jos?

    
    int F(int n) {
        if(n==0 || n==1) return 1;
        return 2*F(n-1) + 2*F(n-2);
    }
    int main() {
        cout << F(3);
    }
    

13. Funcția 13: Ce afiseaza programul C++ de mai jos?

    
    void divSelect(long n) {
        if(n > 9) {
            cout << n/100;
            divSelect(n/10);
        }
    }
    int main() {
        divSelect(12345);
    }
    

14. Funcția 14: Ce afiseaza programul C++ de mai jos?

    
    void cifreRec(long n, int i) {
        if(i < n%10) {
            cout << n%10;
            cifreRec(n/10, i+1);
        }
    }
    int main() {
        cifreRec(12345, 0);
    }
    

15. Funcția 15: Ce afiseaza programul C++ de mai jos?

    
    int F2(int x) {
        if(x <= 1) return x;
        return x + F2(x-2);
    }
    int main() {
        cout << F2(18);
    }
    

16. Scrieți o funcție recursivă factorial care primește prin parametrul x un număr natural și returnează factorialul acestuia. Exemplu: Pentru x=5, factorial(5)=120.


17. Scrieți o funcție recursivă afisCifreStanga care primește un număr natural n și afișează toate cifrele sale de la stânga la dreapta. Exemplu: Pentru n=1234, afișează: 1 2 3 4


18. Scrieți o funcție recursivă afisCifreDreapta care primește un număr natural n și afișează toate cifrele sale de la dreapta la stânga. Exemplu: Pentru n=1234, afișează: 4 3 2 1


19. Scrieți o funcție recursivă sumaPrimeleN care primește un număr natural n și returnează suma primelor n numere naturale. Exemplu: Pentru n=5, sumaPrimeleN(5)=15


20. Scrieți o funcție recursivă palindrom care primește un șir de caractere s și returnează true dacă șirul este palindrom, false altfel. Exemplu: Pentru s="radar", palindrom("radar")=true


21. Scrieți o funcție recursivă maxVector care primește un vector de numere și returnează elementul maxim. Exemplu: Pentru v={3,7,2,9,4}, maxVector(v,5)=9


22. Scrieți o funcție recursivă cmmc care primește două numere naturale și returnează cel mai mare divizor comun (CMMDC). Exemplu: Pentru a=12 și b=18, cmmc(12,18)=6


23. Scrieți o funcție recursivă afisVector care primește un vector și afișează elementele acestuia. Exemplu: Pentru v={1,2,3}, afișează: 1 2 3


24. Scrieți o funcție recursivă convertBaza2 care primește un număr natural și afișează reprezentarea sa în baza 2. Exemplu: Pentru n=13, afișează: 1101