Stiva de apeluri

Pentru a înțelege cu adevărat recursivitatea, trebuie să vezi ce se întâmplă în memorie în timpul execuției. Cheia e stiva de apeluri (call stack).

Ce e stiva de apeluri?

Stiva de apeluri e o zonă specială de memorie unde programul reține contextul fiecărei funcții active:

• Parametrii funcției
• Variabilele locale
• Adresa unde să se întoarcă după ce termină

Când o funcție e apelată, se adaugă un cadru (frame) pe vârful stivei. Când se termină, cadrul e scos.

Stiva:
┌─────────────┐
│  main()     │  ← cadrul apelat primul
└─────────────┘

main() apeleaza f()
┌─────────────┐
│  f()        │  ← adaugat in varf
├─────────────┤
│  main()     │
└─────────────┘

f() apeleaza g()
┌─────────────┐
│  g()        │  ← adaugat in varf
├─────────────┤
│  f()        │
├─────────────┤
│  main()     │
└─────────────┘

Când g() termină, cadrul ei e scos și controlul se întoarce la f().

Recursivitatea și stiva

La fiecare apel recursiv, un nou cadru e adăugat pe stivă. Până la cazul de bază, stiva crește. Apoi cadrele se scot pe rând.

Exemplu: factorial(3)

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

Execuția pas cu pas:

Pas 1: main() apeleaza factorial(3)
┌──────────────────┐
│ factorial(n=3)   │
├──────────────────┤
│ main()           │
└──────────────────┘

Pas 2: factorial(3) apeleaza factorial(2)
┌──────────────────┐
│ factorial(n=2)   │
├──────────────────┤
│ factorial(n=3)   │
├──────────────────┤
│ main()           │
└──────────────────┘

Pas 3: factorial(2) apeleaza factorial(1)
┌──────────────────┐
│ factorial(n=1)   │
├──────────────────┤
│ factorial(n=2)   │
├──────────────────┤
│ factorial(n=3)   │
├──────────────────┤
│ main()           │
└──────────────────┘

Pas 4: factorial(1) apeleaza factorial(0)
┌──────────────────┐
│ factorial(n=0)   │ ← caz de baza!
├──────────────────┤
│ factorial(n=1)   │
├──────────────────┤
│ factorial(n=2)   │
├──────────────────┤
│ factorial(n=3)   │
├──────────────────┤
│ main()           │
└──────────────────┘

Pas 5: factorial(0) returneaza 1
┌──────────────────┐
│ factorial(n=1)   │ ← primeste 1, calculeaza 1 * 1 = 1
├──────────────────┤
│ factorial(n=2)   │
├──────────────────┤
│ factorial(n=3)   │
├──────────────────┤
│ main()           │
└──────────────────┘

Pas 6: factorial(1) returneaza 1
┌──────────────────┐
│ factorial(n=2)   │ ← primeste 1, calculeaza 2 * 1 = 2
├──────────────────┤
│ factorial(n=3)   │
├──────────────────┤
│ main()           │
└──────────────────┘

Pas 7: factorial(2) returneaza 2
┌──────────────────┐
│ factorial(n=3)   │ ← primeste 2, calculeaza 3 * 2 = 6
├──────────────────┤
│ main()           │
└──────────────────┘

Pas 8: factorial(3) returneaza 6
┌──────────────────┐
│ main()           │ ← primeste 6
└──────────────────┘

Fiecare apel “așteaptă” până primește răspunsul de la apelul său. Asta e motivul pentru care recursivitatea folosește memorie.

Memoria folosită

Pentru un apel recursiv cu adâncimea d, stiva are d cadre active.

Fiecare cadru consumă ~câteva zeci-sute de bytes (depinde de variabile locale). Deci:

• factorial(100) → stiva are 100 de cadre, ~10 KB
• factorial(10000) → ~1 MB
• factorial(100000) → poate depăși limita stivei (~1-8 MB)

Stack overflow

Când stiva se umple, programul crapă cu “stack overflow”:

int infinit(int n) {
    return infinit(n + 1); // nu se opreste niciodata
}

int main() {
    cout << infinit(1); // Runtime Error: stack overflow
}

La un moment dat, sistemul spune “destul” și programul e oprit.

Variabile locale în recursivitate

Fiecare apel are propriile variabile locale. Ele nu se amestecă.

void test(int n) {
    int x = n * 2;
    cout << "Apel cu n=" << n << ", x=" << x << "\n";
    if (n > 0) test(n - 1);
    cout << "Revin la n=" << n << ", x=" << x << "\n";
}

Pentru test(3):

Apel cu n=3, x=6
Apel cu n=2, x=4
Apel cu n=1, x=2
Apel cu n=0, x=0
Revin la n=0, x=0
Revin la n=1, x=2
Revin la n=2, x=4
Revin la n=3, x=6

x din fiecare apel e independent - stocat în cadrul propriu pe stivă.

“Înainte” și “după” apelul recursiv

Codul unei funcții recursive poate executa înainte și după apelul recursiv:

void afisare(int n) {
    if (n == 0) return;
    cout << n << " ";      // ÎNAINTE de apel
    afisare(n - 1);
    cout << n << " ";      // DUPĂ apel
}

Pentru afisare(3):

Apel afisare(3): "3 " [inainte]
  Apel afisare(2): "2 " [inainte]
    Apel afisare(1): "1 " [inainte]
      Apel afisare(0): return
    "1 " [dupa]
  "2 " [dupa]
"3 " [dupa]

Iesire: 3 2 1 1 2 3

Asta e util pentru parcurgerile de arbori (preorder, inorder, postorder).

Recursivitatea ca “întoarcere în timp”

Când un apel recursiv returnează, execuția revine la cadrul părinte, exact unde a rămas. Variabilele locale sunt exact cum le-a lăsat.

Cum să vizualizezi execuția

Opțiunea 1: scrie variabilele

int factorial(int n) {
    cout << "Intru in factorial(" << n << ")\n";
    if (n == 0) {
        cout << "Caz de baza: return 1\n";
        return 1;
    }
    int r = n * factorial(n - 1);
    cout << "Ies din factorial(" << n << "), return " << r << "\n";
    return r;
}

Asta îți arată fluxul exact.

Opțiunea 2: desenează stiva pe hârtie

Desenează cadrele pe măsură ce sunt adăugate/scoase. E cel mai bun mod să înțelegi.

Când e OK să folosești recursivitate?

• Adâncime mică (până la ~10^4).
• Problema e natural recursivă (arbori, subprobleme mai mici).
• Memoria nu e o problemă.

Pentru adâncime mare sau probleme în care iterativul e mai clar, preferă iterativul.

Greșeli frecvente

1. Folosirea variabilelor globale greșit

int x = 0;

void f(int n) {
    if (n == 0) return;
    x = n;         // x se modifica
    f(n - 1);
    cout << x;     // x e mereu 1, nu n! (ultimul apel l-a modificat)
}

Dacă vrei ca fiecare apel să aibă propria valoare, folosește variabile locale, nu globale.

2. Apeluri recursive în bucle adânci

void f(int n) {
    if (n == 0) return;
    for (int i = 0; i < n; i++)
        f(n - 1);  // apeluri multiple - creste exponential!
}

Verifică dacă toate apelurile sunt necesare - poate duce la complexitate exponențială.

3. Uitarea return în caz de bază

int f(int n) {
    if (n == 0) /* uitat return */ 1;  // nu returneaza nimic!
    return n * f(n - 1);
}

În C++, comportament nedefinit - poate crăpa sau da rezultat aiurea.

Ce să reții

• Stiva de apeluri ține contextul fiecărei funcții active.
• La fiecare apel recursiv, un cadru nou se adaugă pe stivă.
• Cadrele sunt scoase în ordinea inversă (LIFO) când funcțiile returnează.
• Variabilele locale sunt independente per cadru.
• Stack overflow când stiva se umple (~10^4-105 apeluri).
• Codul “înainte” vs “după” apelul recursiv are efecte diferite (preorder vs postorder).
• Adâncimea recursivității = memoria folosită.