Recursivitate — Informatică Liceu

🔄

Ce este recursivitatea?

🪆 Analogie: Recursivitatea = Păpuși Matrioșka

Imaginează-ți că deschizi o păpușă Matrioșka: înăuntru găsești alta mai mică, înăuntru alta și mai mică, până la cea mai mică care nu mai are nimic înăuntru. Recursivitatea funcționează la fel:

Fiecare apel al funcției rezolvă o problemă mai mică
Cel mai mic caz se rezolvă direct (cazul de bază)
Rezultatele se întorc în lanț spre apelul inițial

O funcție este recursivă dacă se apelează pe sine însuși, direct sau indirect, pentru a rezolva o versiune mai mică a aceluiași subproblemă.

Structura oricărei funcții recursive:
1. Cazul de bază (baza recursiei) — condiție de oprire, returnează direct un rezultat
2. Pasul recursiv — apel recurent pe o versiune mai mică a problemei

Atenție: Fără caz de bază → recursie infinită → stack overflow!

// Structura generală
tip_returnat functie(parametri) {
    if (caz_de_baza)
        return valoare_directa;    // oprim recursivitatea
    return functie(parametri_mai_mici);  // pasul recursiv
}

📚

Stiva de apeluri (Call Stack)

La fiecare apel de funcție, sistemul creează un cadru (frame) pe stivă care reține: parametrii, variabilele locale și adresa de întoarcere. La revenire, cadrul este scos de pe stivă.

Cum funcționează: Apelul factorial(4) generează 5 frame-uri pe stivă (push). La revenire, valorile se calculează de jos în sus (pop).

▲ PUSH (construire stivă)

factorial(0) → 1

caz de bază — returnează

factorial(1) → 1 × 1 = 1

factorial(2) → 2 × 1 = 2

factorial(3) → 3 × 2 = 6

factorial(4) → 4 × 6 = 24

▼ POP (întoarcere valori)

factorial(4) = 4 × 3 × 2 × 1 × 1 = 24 — 5 frame-uri, 5 returnări

🔢

Factorial — implementare C++

long long factorial(int n) {
    if (n == 0 || n == 1)
        return 1;         // cazul de bază
    return n * factorial(n - 1);  // pasul recursiv
}

Complexitate timp: O(n)

Se execută n apeluri recursive

Complexitate spațiu: O(n)

n cadre pe stivă simultan

n	n!
0	1
1	1
5	120
10	3 628 800
20	2 432 902 008 176 640 000

Pentru n > 20 rezultatul depășește long long. Folosiți unsigned long long sau tipuri de precizie arbitrară pentru valori mai mari.

🌀

Fibonacci — recursiv simplu și memoizat

Varianta recursivă simplă — O(2ⁿ)

int fib(int n) {
    if (n <= 1) return n;  // fib(0)=0, fib(1)=1
    return fib(n-1) + fib(n-2);
    // PROBLEMA: recalculează aceleași subprobleme!
}

Problemă: fib(50) execută miliarde de apeluri! fib(5) calculează fib(3) de 2 ori, fib(2) de 3 ori etc.

Arborele de recursie pentru fib(5)

fib(5)

├── fib(4)

│   ├── fib(3)

│   │   ├── fib(2) → fib(1)+fib(0)

│   │   └── fib(1)

│   └── fib(2) → fib(1)+fib(0)  ← RECALCULAT

└── fib(3) ← RECALCULAT COMPLET

├── fib(2) → ...

└── fib(1)

🎮 Demo interactiv — arborele de recursie fib(n)

Bifează Memoizare și compară numărul de apeluri. Pentru n=8 fără memoizare apar peste 60 de apeluri, cu memoizare doar 15.

⚡ Viteză: Normal

n: Memoizare Apeluri: 0

în curs caz de bază calculat memo hit ⚡

Problema: Mută n discuri de pe tija A pe tija C folosind tija B ca intermediar. Regulă: nu se poate pune un disc mai mare pe unul mai mic.

🗼

Turnurile din Hanoi

🗼 Hanoi = mută turnul pe altă tijă

Ai 3 tije (A, B, C) și n discuri de dimensiuni diferite așezate pe tija A în ordine descrescătoare. Trebuie să muți toate discurile pe tija C, respectând regulile:

Poți muta un singur disc odată
Nu poți pune un disc mai mare peste unul mai mic
Folosești tija B ca intermediar

void hanoi(int n, char sursa, char dest, char intermediar) {
    if (n == 1) {
        cout << "Mută disc 1 de pe " << sursa << " pe " << dest << endl;
        return;  // caz de bază
    }
    hanoi(n-1, sursa, intermediar, dest);  // mută n-1 discuri pe B
    cout << "Mută disc " << n << " de pe " << sursa << " pe " << dest << endl;
    hanoi(n-1, intermediar, dest, sursa);  // mută n-1 discuri pe C
}

Complexitate timp: O(2ⁿ)

Numărul de mutări = 2ⁿ - 1

Complexitate spațiu: O(n)

Adâncimea stivei de apeluri

n discuri	Mutări necesare
1	1
3	7
10	1 023
20	1 048 575
64	18 446 744 073 709 551 615

Legendă: Cu 64 de discuri, călugării din mit ar avea nevoie de ~585 miliarde de ani la o mutare/secundă. Recursivitatea e elegantă dar poate fi extrem de costisitoare!

🔍

Căutare binară — variantă recursivă

int cautareBinaraRec(int v[], int st, int dr, int x) {
    if (st > dr) return -1;  // caz de bază: nu am găsit

    int mij = (st + dr) / 2;

    if (v[mij] == x) return mij;  // caz de bază: am găsit
    if (v[mij] < x)
        return cautareBinaraRec(v, mij+1, dr, x);   // jumătatea dreaptă
    return cautareBinaraRec(v, st, mij-1, x);  // jumătatea stângă
}

// Apel: cautareBinaraRec(v, 0, n-1, valoare_cautata)

Complexitate: O(log n) timp, O(log n) spațiu (adâncimea recursiei = log₂n)

🎬

Demo — Stiva de apeluri Factorial

Introdu un număr și apasă Rulează pentru a vizualiza cum se construiește și se desfășoară stiva de apeluri.

⚡ Viteză: Normal

n =

Viteză pași demo Ready

Demo 2: Fibonacci simplu vs memoizat

Compară numărul de apeluri recursive pentru același n.

n =

Demo 3: CMMDC recursiv (Euclid)

Vezi pașii recursivi până la cazul de bază b=0.

Demo 4: Căutare binară recursivă

Introduce un vector sortat și valoarea căutată.

Demo 5: Sumă cifre recursiv

Descompune n în ultima cifră + restul numărului.

⚖️

Recursiv vs. Iterativ

Criteriu	Recursiv	Iterativ
Lizibilitate	✅ Mai clar pentru probleme de tip divide-et-impera	Poate fi mai greu de urmărit
Memorie	❌ Stiva de apeluri consumă O(adâncime) extra	✅ De obicei O(1) extra
Viteză	Overhead la fiecare apel de funcție	✅ Mai rapid în practică
Stack overflow	❌ Risc pentru n mare	✅ Fără risc
Potrivit pentru	Arbori, backtracking, divide-et-impera	Bucle simple, iterare lineară

Factorial iterativ — O(1) spațiu

long long factorialIterativ(int n) {
    long long rez = 1;
    for (int i = 2; i <= n; i++)
        rez *= i;
    return rez;
    // O(n) timp, O(1) spațiu — fără stivă de apeluri
}

🧠

Memoizare — optimizarea recursivității

Memoizarea înseamnă salvarea rezultatelor calculate pentru a evita recalcularea lor. Este primul pas spre programare dinamică.

Fibonacci memoizat — O(n)

int memo[100];  // memo[i] = -1 (necalculat) sau valoarea fib(i)

void initMemo() {
    for (int i = 0; i < 100; i++) memo[i] = -1;
}

int fibMemo(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // deja calculat!
    memo[n] = fibMemo(n-1) + fibMemo(n-2);
    return memo[n];
    // O(n) timp — fiecare valoare calculată o singură dată
}

Comparație: fib(40) recursiv simplu = ~330 milioane apeluri. fib(40) cu memoizare = 79 apeluri!

Fibonacci iterativ — O(1) spațiu

long long fibIterativ(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
    // O(n) timp, O(1) spațiu — cel mai eficient
}

🧩

Probleme rezolvate — recursivitate

5 probleme clasice, fiecare urmărind tiparul: caz de bază + pas recursiv.

1 Sumă cifre recursiv Ușor

Scrie o funcție recursivă care calculează suma cifrelor unui număr natural n.

Intrare:

Ieșire:

💡 Vezi soluția

int sumCifre(int n) {
    if (n == 0) return 0;        // caz de bază
    return n % 10 + sumCifre(n / 10);
}

Idee: ultima cifră = n%10; restul cifrelor formează n/10. Recursia se oprește când n=0 (nu mai sunt cifre).

2 Putere a^b recursiv Ușor

Calculează a^b folosind recursivitatea, fără a folosi pow.

Intrare:

2 10

Ieșire:

💡 Vezi soluția

long long putere(int a, int b) {
    if (b == 0) return 1;          // a^0 = 1
    return a * putere(a, b - 1);
}

// Optimizat: O(log b) — exponențiere rapidă
long long putereRapid(long long a, int b) {
    if (b == 0) return 1;
    long long h = putereRapid(a, b / 2);
    return (b % 2) ? h * h * a : h * h;
}

Trucul O(log b): a^b = (a^b/2)² dacă b par, sau a·(a^b/2)² dacă b impar. Reduce numărul de înmulțiri de la b la log b.

3 CMMDC recursiv (Euclid) Mediu

Calculează cel mai mare divizor comun a două numere folosind algoritmul lui Euclid, recursiv.

Intrare:

48 36

Ieșire:

💡 Vezi soluția

int cmmdc(int a, int b) {
    if (b == 0) return a;
    return cmmdc(b, a % b);
}
// cmmdc(48, 36) → cmmdc(36, 12) → cmmdc(12, 0) → 12

Idee: CMMDC(a, b) = CMMDC(b, a mod b). Cazul de bază: când b=0, a este răspunsul. Complexitate O(log min(a,b)).

4 Verifică palindrom recursiv Mediu

Verifică dacă un șir este palindrom folosind doar recursivitate (fără bucle).

Intrare:

radar

Ieșire:

DA

💡 Vezi soluția

bool estePalRec(const string& s, int l, int r) {
    if (l >= r) return true;              // 0 sau 1 caracter rămas
    if (s[l] != s[r]) return false;        // nepotrivire
    return estePalRec(s, l + 1, r - 1);  // avansăm spre centru
}
// Apel: estePalRec(s, 0, s.length()-1)

Idee: doi pointeri (l, r) care converg. Cazul de bază: când se intersectează ⇒ palindrom. Adâncime stivă O(n/2).

5 Inversare număr recursiv Dificil

Inversează cifrele unui număr natural folosind recursivitate. Ex: 1234 → 4321.

Intrare:

Ieșire:

💡 Vezi soluția

// Versiunea cu acumulator (helper)
int invHelper(int n, int acc) {
    if (n == 0) return acc;
    return invHelper(n / 10, acc * 10 + n % 10);
}
int inverseaza(int n) { return invHelper(n, 0); }

// Trace pentru n=1234:
// invHelper(1234, 0)  → invHelper(123, 4)
// invHelper(123, 4)   → invHelper(12, 43)
// invHelper(12, 43)   → invHelper(1, 432)
// invHelper(1, 432)   → invHelper(0, 4321) → 4321

De ce un helper: avem nevoie de un al doilea parametru (acumulatorul) ca să construim cifră cu cifră noul număr. Funcția principală îl ascunde pornind de la 0.

💪 Pentru și mai multe probleme rezolvate vezi secțiunea BAC de mai jos și quiz-ul interactiv.

📝

Probleme tip BAC — recursivitate

Problemă 1: Scrieți o funcție recursivă care calculează suma cifrelor unui număr natural n.

Soluție:

int sumaCifre(int n) {
    if (n < 10) return n;   // caz de bază: număr de o cifră
    return n % 10 + sumaCifre(n / 10);
}
// sumaCifre(1234) = 4 + sumaCifre(123) = 4+3+sumaCifre(12) = 4+3+2+1 = 10

Problemă 2: Scrieți o funcție recursivă care calculează c.m.m.d.c. a două numere (algoritmul lui Euclid).

Soluție:

int cmmdc(int a, int b) {
    if (b == 0) return a;  // caz de bază
    return cmmdc(b, a % b);
    // cmmdc(48,18) → cmmdc(18,12) → cmmdc(12,6) → cmmdc(6,0) → 6
}

Problemă 3: Scrieți o funcție recursivă care calculează aⁿ (putere) eficient în O(log n).

Soluție (exponentiere rapidă):

long long putere(long long a, int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long jum = putere(a, n/2);
        return jum * jum;  // aⁿ = (aⁿ/²)²
    }
    return a * putere(a, n-1);
    // O(log n) în loc de O(n)
}

💪

🔄 Recursivitate

Ce este recursivitatea?

Stiva de apeluri (Call Stack)

Factorial — implementare C++

Fibonacci — recursiv simplu și memoizat

Varianta recursivă simplă — O(2ⁿ)

Arborele de recursie pentru fib(5)

Turnurile din Hanoi

Căutare binară — variantă recursivă

Demo — Stiva de apeluri Factorial

Recursiv vs. Iterativ

Factorial iterativ — O(1) spațiu

Memoizare — optimizarea recursivității

Fibonacci memoizat — O(n)

Fibonacci iterativ — O(1) spațiu

Probleme rezolvate — recursivitate

Probleme tip BAC — recursivitate

Exerciții interactive — testează cunoștințele