Invatare Atomica

Recursivitate — Toate tipurile

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei stapani recursivitatea in toate formele cerute la BAC: directa, indirecta, cu stiva de apeluri, probleme clasice (factorial, Fibonacci, CMMDC, Hanoi, putere rapida) si analiza complexitatii.

Dupa aceasta lectie vei putea:

  • Sa definesti recursivitatea si sa identifici cazul de baza si cazul recursiv in orice functie
  • Sa trasezi manual stiva de apeluri pentru o functie recursiva cu cel mult 5 niveluri
  • Sa scrii in C++ functii recursive pentru factorial, CMMDC, Fibonacci si suma cifrelor
  • Sa rezolvi problema Turnurilor Hanoi si sa explici de ce necesita 2n−1 mutari
  • Sa implementezi puterea rapida recursiva cu complexitate O(log n)
  • Sa distingi recursivitatea directa de cea indirecta si sa identifici riscul de stack overflow

Incearca singur!

Provocare de incalzire:

Calculeaza manual: care este valoarea returnata de apelul f(4) daca functia f este definita astfel?

int f(int n) {
    if (n == 0) return 0;
    return n + f(n - 1);
}
💡 Ai nevoie de un indiciu?

Urmareste lantul de apeluri: f(4) = 4 + f(3) = 4 + 3 + f(2) = 4 + 3 + 2 + f(1) = 4 + 3 + 2 + 1 + f(0).

f(0) returneaza 0 (cazul de baza). Rezultatul este suma 4+3+2+1+0 = 10. Aceasta functie calculeaza suma 1+2+...+n.

1

1. Ce este recursivitatea?

O functie este recursiva daca se apeleaza pe sine insasi (direct sau indirect) pentru a rezolva o versiune mai mica a aceleiasi probleme. Orice functie recursiva corecta contine doua parti obligatorii:
  • Cazul de baza — conditia care opreste recursivitatea (returneaza direct, fara apel recursiv)
  • Cazul recursiv — reduce problema la o versiune mai simpla si se apeleaza pe sine
Analogie sigura: cutia in cutie

Imagine ca ai o cutie care contine fie o alta cutie (mai mica), fie un bilet cu raspunsul. Cauti raspunsul deschizand cutii pana gasesti biletul. Biletul = cazul de baza. Cutia din cutie = cazul recursiv.

Structura universala in C++ EXCLUSIV INTENSIV
tip_returnat functie(parametri) {
    // CAZUL DE BAZA - opreste recursivitatea
    if (conditie_simpla) {
        return valoare_directa;
    }
    // CAZUL RECURSIV - reduce la subproblema mai mica
    return ... + functie(parametri_redusi);
}

Atentie BAC: Daca lipseste cazul de baza sau parametrii nu se reduc spre el, functia ruleaza la infinit si programul se opreste cu eroare de stack overflow (stiva plina).

2

2. Factorial si stiva de apeluri EXCLUSIV INTENSIV

Factorial: n! = n × (n−1) × ... × 1, cu 0! = 1.
Definitia recursiva: factorial(n) = n × factorial(n−1), caz de baza: factorial(0) = 1.
Complexitate timp: O(n) — n apeluri recursive.
Complexitate spatiu: O(n) — stiva de apeluri creste cu n cadre. 
#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0) return 1; // caz de baza
    return n * factorial(n - 1); // caz recursiv
}

int main() {
    cout << "factorial(0) = " << factorial(0) << endl;
    cout << "factorial(1) = " << factorial(1) << endl;
    cout << "factorial(5) = " << factorial(5) << endl;
    cout << "factorial(10) = " << factorial(10) << endl;
    return 0;
}
Output real (g++ -std=c++17, rulat):
factorial(0) = 1
factorial(1) = 1
factorial(5) = 120
factorial(10) = 3628800
Trasarea stivei de apeluri pentru factorial(4):
=== Trasarea stivei pentru factorial(4) ===
factorial(4) apelat
  factorial(3) apelat
    factorial(2) apelat
      factorial(1) apelat
        factorial(0) apelat
        factorial(0) returneaza 1
      factorial(1) returneaza 1
    factorial(2) returneaza 2
  factorial(3) returneaza 6
factorial(4) returneaza 24
Rezultat final: 24

Citire trasare (tip BAC): La fiecare apel se suspenda executia functiei curente si se trece la cea nou apelata. Rezultatele se calculeaza la intoarcerea din recursie (de jos in sus). Apelul factorial(0) intoarce 1, care permite factorial(1)=1*1=1, factorial(2)=2*1=2, factorial(3)=3*2=6, factorial(4)=4*6=24.

3

3. CMMDC recursiv si Fibonacci EXCLUSIV INTENSIV

Algoritmul lui Euclid (recursiv): cmmdc(a, b) = cmmdc(b, a % b), caz de baza: cmmdc(a, 0) = a.
Complexitate timp: O(log min(a,b)) — mult mai eficient decat scaderile repetate O(max/min).

Fibonacci recursiv: fib(n) = fib(n-1) + fib(n-2), cazuri de baza: fib(0)=0, fib(1)=1.
Atentie: Fibonacci recursiv naiv are complexitate O(2n) — extrem de ineficient pentru n mare. 
#include <iostream>
using namespace std;

// CMMDC recursiv - O(log min(a,b))
int cmmdc(int a, int b) {
    if (b == 0) return a; // caz de baza
    return cmmdc(b, a % b); // caz recursiv
}

int main() {
    cout << "cmmdc(12, 8) = " << cmmdc(12, 8) << endl;
    cout << "cmmdc(100, 75) = " << cmmdc(100, 75) << endl;
    cout << "cmmdc(17, 13) = " << cmmdc(17, 13) << endl;
    return 0;
}
Output real (g++ -std=c++17, rulat):
cmmdc(12, 8) = 4
cmmdc(100, 75) = 25
cmmdc(17, 13) = 1
Fibonacci recursiv (Python) — output real (python):
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13

Capcana BAC — Fibonacci ineficient: fib(5) calculeaza fib(3) de doua ori, fib(2) de trei ori etc. Pentru n=43 se fac peste un miliard de apeluri (~1,40 mld); pentru n=40 se fac peste 300 de milioane de apeluri. Solutia corecta la concurs: iterativ sau memoizare.

Arbore de apeluri pentru fib(4):
               fib(4)
             /        \
         fib(3)       fib(2)
        /     \       /    \
    fib(2)  fib(1) fib(1) fib(0)
    /    \
fib(1) fib(0)
4

4. Probleme cu cifre si recursivitate indirecta EXCLUSIV INTENSIV

Recursivitate directa: functia se apeleaza pe sine (f apeleaza f).
Recursivitate indirecta: f apeleaza g, iar g apeleaza f (ciclul poate fi mai lung).
Ambele tipuri necesita cazuri de baza in fiecare functie implicata. 
#include <iostream>
using namespace std;

// Suma cifrelor unui numar - recursiv direct
int sumaCifre(int n) {
    if (n < 10) return n; // caz de baza: o singura cifra
    return n % 10 + sumaCifre(n / 10); // ultima cifra + rest
}

// Inversul unui numar - recursiv, afisare directa
void inversNumar(int n) {
    if (n == 0) return; // caz de baza
    cout << n % 10;           // afiseaza ultima cifra
    inversNumar(n / 10);       // continua cu restul
}

int main() {
    cout << "sumaCifre(1234) = " << sumaCifre(1234) << endl;
    cout << "sumaCifre(9999) = " << sumaCifre(9999) << endl;
    cout << "invers(1234) = ";
    inversNumar(1234);
    cout << endl;
    return 0;
}
Output real (g++ -std=c++17, rulat):
sumaCifre(1234) = 10
sumaCifre(9999) = 36
invers(1234) = 4321
Recursivitate indirecta: par/impar EXCLUSIV INTENSIV
bool este_par(int n);
bool este_impar(int n);

bool este_par(int n) {
    if (n == 0) return true;
    return este_impar(n - 1);
}
bool este_impar(int n) {
    if (n == 0) return false;
    return este_par(n - 1);
}

Output real: este_par(4) = true | este_par(7) = false | este_impar(3) = true

Observatie importanta: La recursivitatea indirecta, declaratiile (prototipurile) functiilor trebuie sa apara inainte de definitii (altfel compilatorul nu stie ca este_impar exista cand compileaza este_par).

5

5. Turnurile Hanoi — problema clasica BAC EXCLUSIV INTENSIV

Problema: Muta n discuri de pe tija A pe tija C, folosind tija B ca auxiliar, fara a pune un disc mai mare peste unul mai mic.
Solutia recursiva:
  • Muta n−1 discuri de pe A pe B (folosind C)
  • Muta discul n (cel mai mare) de pe A pe C
  • Muta n−1 discuri de pe B pe C (folosind A)
Complexitate: O(2n) — numarul exact de mutari este 2n−1. 
#include <iostream>
using namespace std;

void hanoi(int n, char sursa, char destinatie, char auxiliar) {
    if (n == 1) {
        cout << "Muta discul 1 din " << sursa << " in " << destinatie << endl;
        return; // caz de baza: un singur disc
    }
    hanoi(n - 1, sursa, auxiliar, destinatie); // muta n-1 pe auxiliar
    cout << "Muta discul " << n << " din " << sursa << " in " << destinatie << endl;
    hanoi(n - 1, auxiliar, destinatie, sursa); // muta n-1 de pe auxiliar
}

int main() {
    cout << "=== Hanoi cu 3 discuri ===" << endl;
    hanoi(3, 'A', 'C', 'B');
    return 0;
}
Output real (g++ -std=c++17, rulat) — 7 mutari = 23−1:
=== Hanoi cu 3 discuri ===
Muta discul 1 din A in C
Muta discul 2 din A in B
Muta discul 1 din C in B
Muta discul 3 din A in C
Muta discul 1 din B in A
Muta discul 2 din B in C
Muta discul 1 din A in C

De memorat la BAC: Hanoi cu n discuri = 2n−1 mutari. Complexitate exponentiala: pentru n=64 (legenda templului) = 1.8 × 1019 mutari — imposibil in viata umana.

6

6. Puterea rapida recursiva — O(log n) EXCLUSIV INTENSIV

Idee: In loc de n inmultiri (lent, O(n)), exploateaza faptul ca baza2k = (bazak)2.
Se calculeaza jumatatea o singura data si se inmulteste cu ea insasi — reducere la O(log n).
Cazuri:
  • putere(b, 0) = 1                               (caz de baza)
  • putere(b, 2k) = putere(b, k) × putere(b, k)  (exp par — injumatatire)
  • putere(b, 2k+1) = b × putere(b, 2k)             (exp impar)
#include <iostream>
using namespace std;

// Putere rapida - O(log n)
long long putere(long long baza, int exp) {
    if (exp == 0) return 1; // caz de baza
    if (exp % 2 == 0) {
        long long jum = putere(baza, exp / 2); // calculeaza ODATA
        return jum * jum; // inmulteste cu sine, nu apela de doua ori!
    }
    return baza * putere(baza, exp - 1); // exp impar
}

int main() {
    cout << "putere(2, 10) = " << putere(2, 10) << endl;
    cout << "putere(3, 5) = " << putere(3, 5) << endl;
    cout << "putere(2, 0) = " << putere(2, 0) << endl;
    return 0;
}
Output real (g++ -std=c++17, rulat):
putere(2, 10) = 1024
putere(3, 5) = 243
putere(2, 0) = 1
Capcana frecventa — NU scrie asa (apel dublu = O(n) nu O(log n)):
// GRESIT: se fac doua apeluri recursive => complexitate O(n) nu O(log n)!
if (exp % 2 == 0)
    return putere(baza, exp/2) * putere(baza, exp/2); // GRESIT!

Comparatie complexitati:

AlgoritmTimpSpatiu (stiva)n=30
putere lenta (iterativ)O(n)O(1)30 pasi
putere rapida (recursiv)O(log n)O(log n)5 pasi
Fibonacci naivO(2n)O(n)~109 pasi
Fibonacci iterativO(n)O(1)30 pasi

Exercitii practice

Exercitiul 1 (Nivel minim) — Urmarire manuala

Traseaza manual apelurile pentru cmmdc(18, 12) si gaseste rezultatul fara calculator. Scrie fiecare apel pe un rand: cmmdc(18,12) → cmmdc(?,?) → ... pana la caz de baza.

Exercitiul 2 (Nivel standard) — Functie recursiva noua

Scrie in C++ o functie recursiva putere_cifre(n) care calculeaza produsul cifrelor unui numar natural n (ex: putere_cifre(234) = 2*3*4 = 24). Caz de baza: n < 10 returneaza n. Testeaza cu 234, 100, 7.

Exercitiul 3 (Nivel performanta) — BAC 2023 tip Subiectul II

Analizeaza functia de mai jos si raspunde: (a) ce valoare afiseaza apelul f(5, 0)? (b) Care este relatia de recurenta? (c) Rescrie iterativ.
void f(int n, int s) { if(n==0){ cout<<s; return; } f(n/10, s + n%10); }

Ce ai invatat astazi

  • Structura oricarei functii recursive: caz de baza + caz recursiv
  • Trasarea stivei de apeluri (citit de jos in sus la intoarcere)
  • Factorial O(n), CMMDC Euclid O(log n), Fibonacci naiv O(2n)
  • Suma cifrelor si inversul unui numar — recursivitate directa
  • Recursivitate indirecta si necesitatea prototipurilor in C++
  • Turnurile Hanoi: formula 2n−1 mutari, complexitate exponentiala
  • Puterea rapida: O(log n) prin injumatatirea exponentului (un singur apel, nu doua!)

Urmatoarea lectie

Continua cu Backtracking — generare sistematica de solutii, permutari, combinari si probleme clasice BAC.

Backtracking →