De ce contează?
Imaginează-ți că rezolvi o problemă și, la mijloc, te trezești că trebuie să rezolvi
mai întâi o sub-problemă. Lași pe birou un bilețel: „revino aici după". Apoi apare o
sub-sub-problemă: încă un bilețel deasupra. Teancul de bilețele crește. Când termini
ultima problemă, iei bilețelul de DEASUPRA și revii exact unde rămăsese acel apel.
Calculatorul face fix asta când o funcție cheamă altă funcție — doar că teancul lui
de bilețele are un nume: stiva de apeluri. Aceeași regulă LIFO pe care ai
declarat-o cu mâna ta într-un stack, calculatorul o folosește pe ascuns la fiecare apel.
Ideea-cheie
Ai învățat stiva ca structură de date: un teanc unde pui și scoți doar de la vârf (LIFO — ultimul intrat, primul ieșit). Surpriza e că ai folosit deja o stivă chiar și fără s-o declari: de fiecare dată când o funcție cheamă altă funcție.
Când funcția A cheamă funcția B, calculatorul trebuie să țină minte unde să se
întoarcă în A și ce valori avea A în acel moment. Le împachetează într-un cadru
(engl. stack frame) și îl pune pe vârful unei stive speciale din memorie, stiva de
apeluri. Când B se termină, cadrul lui se scoate de pe vârf și execuția revine în
A, exact de unde rămăsese. Apeluri imbricate, revenire în ordine inversă: e exact
comportamentul LIFO al unei stive.
Trei idei care se leagă într-un lanț:
- Fiecare apel = un cadru pe stiva de apeluri. Când apelul se termină, cadrul se scoate de pe vârf. Apeluri imbricate, revenire în ordine inversă: pur LIFO.
- Recursivitatea = o stivă implicită. O funcție recursivă nu folosește o stivă „nouă" — pune pe exact aceeași stivă de apeluri multe cadre ale aceleiași funcții, câte unul pentru fiecare nivel de coborâre.
- De aici, stack overflow. Teancul are o limită. O recursie prea adâncă pune mai multe cadre decât încape și pică cu eroarea stack overflow — nu pentru că logica e greșită, ci pentru că a umplut stiva.
Asta leagă cele două capitole: stiva pe care o declari cu mâna ta și recursivitatea sunt același mecanism — LIFO. Una e explicită (o vezi în cod), cealaltă e implicită (o întreține calculatorul pentru tine).