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ă.

Apelul factorial(4) generează 5 frame-uri pe stivă. La revenire, valorile se calculează de jos în sus.

factorial(4) → 4 × factorial(3)

↓

factorial(3) → 3 × factorial(2)

↓

factorial(2) → 2 × factorial(1)

↓

factorial(1) → 1 × factorial(0)

↓

factorial(0) → 1 ← caz de bază!

Revenire: 1 → 1×1=1 → 2×1=2 → 3×2=6 → 4×6=24

factorial(4) = 4 × 3 × 2 × 1 × 1 = 24

🔢

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)

🗼

Turnurile din Hanoi

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.

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

🔍

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 =

⚖️

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 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 tip BAC — recursivitate

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