Stiva apelurilor — memoria recursivității

Ce e un cadru și ce e stiva apelurilor

Când programul cheamă o funcție, sistemul îi rezervă în memorie un cadru (stack frame): un mic spațiu cu parametrii și variabilele locale ale acelui apel, plus adresa la care trebuie să se întoarcă după return.

Toate cadrele stau unul peste altul într-o structură numită stiva apelurilor (call stack). E o stivă reală, cu același principiu LIFO pe care l-ai văzut la stivă: ultimul cadru pus e primul scos.

• Când un apel începe → se face push la cadrul lui pe stivă (coborâre).
• Când apelul se termină cu return → se face pop la cadrul lui (urcare).

Aici nu repetăm ce valoare se calculează (asta e la apelul recursiv) — ne uităm la ce se întâmplă în memorie în timp ce recursia coboară și urcă.

Exemplu pas cu pas: cadrele la factorial(4)

Pornim de la factorial(n) = n * factorial(n-1), cu cazul de bază factorial(0) = 1. La coborâre, fiecare apel pune un cadru nou deasupra:

Fiecare cadru își ține propriul n: cadrul lui factorial(4) are n = 4, cel de deasupra are n = 3, și tot așa. Sunt valori separate, nu una comună.

• Coborâre (push): f(4) → f(3) → f(2) → f(1) → f(0).
• f(0) returnează 1 și e scos (pop).
• Urcare (pop): f(1) returnează 1, f(2) returnează 2, f(3) returnează 6, f(4) returnează 24. Stiva se golește de sus în jos.

Adâncimea maximă a stivei pentru factorial(4) este 5 cadre simultan.

Implementare C++

#include <iostream>
using namespace std;

long long factorial(int n) {
    // fiecare apel are propriul cadru: copia lui de n traieste aici
    long long local;                  // variabila locala a ACESTUI cadru
    if (n == 0) {
        return 1;                     // caz de baza: cadrul se scoate (pop)
    }
    local = factorial(n - 1);         // push: un cadru nou intra deasupra
    return n * local;                 // dupa pop-ul de sus, calculam si returnam
}

int main() {
    cout << factorial(4) << endl;     // 24
    cout << factorial(0) << endl;     // 1
    return 0;
}

La linia factorial(n - 1), cadrul curent rămâne „în așteptare” pe stivă, cu n și local ale lui intacte, în timp ce deasupra crește un cadru nou. Când cel de deasupra face return, controlul revine exact aici, la valorile cadrului tău.

Stack overflow: când și de ce

Stiva apelurilor are o dimensiune fixă și limitată (tipic câteva mii până la câteva zeci de mii de cadre, în funcție de sistem). Dacă recursia coboară prea adânc, cadrele se acumulează până nu mai au loc — programul se oprește cu stack overflow.

Apare în două situații:

• Recursie infinită: lipsește cazul de bază sau nu te apropii de el (ex. factorial(n) apelat fără să scadă n). Cadrele cresc la infinit.
• Recursie validă, dar prea adâncă: ex. o recursie liniară pe n = 1.000.000. E corectă logic, dar adâncimea depășește capacitatea stivei.

Vizualizare

Urmărește cum fiecare apel pune un cadru pe stivă la coborâre și cum cadrele se scot de sus în jos la urcare, până stiva se golește:

Recapitulare

• Fiecare apel are propriul cadru pe stiva apelurilor, cu parametrii și variabilele lui locale — separate de celelalte apeluri.
• Coborârea face push la cadre, urcarea face pop (LIFO); adâncimea recursiei e înălțimea maximă a stivei.
• Recursia prea adâncă sau infinită umple stiva → stack overflow; iterativul folosește O(1) spațiu pe stivă.