De ce contează?
Imaginează-ți un arbore genealogic, dar nu al unei familii — al apelurilor unei funcții. Fiecare apel este o persoană; „copiii” ei sunt apelurile pe care le face mai departe. Dacă desenezi acest arbore, vezi dintr-o privire cât muncește programul tău și — surpriză — câtă muncă repetă degeaba.
Ce este arborele de recursie
Arborele de recursie este o schiță a tuturor apelurilor pe care le face o funcție recursivă, de la primul apel până la cazurile de bază.
- Un nod = un apel al funcției (ex.
fib(5)). - Copiii unui nod = apelurile pe care le face acel nod (subproblemele lui).
- Frunzele = apelurile care nu mai cheamă pe nimeni: cazurile de bază.
Nu rulezi nimic ca să-l desenezi. E o unealtă de gândire: o faci pe hârtie sau în minte ca să înțelegi ce se întâmplă și cât costă, înainte să te plângi că programul e lent.
Exemplu: arborele lui fib(5)
Fibonacci naiv este definit așa:
int fib(int n) {
if (n <= 1) return n; // caz de baza
return fib(n - 1) + fib(n - 2); // doua subapeluri
}Fiecare apel cheamă alte două apeluri. Desenat cu indentare simplă, arborele lui
fib(5) arată așa (am marcat cu <-- recalculat nodurile care se mai calculaseră
deja o dată în altă parte a arborelui):
fib(5)
fib(4)
fib(3)
fib(2)
fib(1) -> 1
fib(0) -> 0
fib(1) -> 1
fib(2) <-- recalculat (fib(2) iar de la zero)
fib(1) -> 1
fib(0) -> 0
fib(3) <-- recalculat (tot subarborele fib(3) inca o data)
fib(2) <-- recalculat
fib(1) -> 1
fib(0) -> 0
fib(1) -> 1Privește cu atenție: fib(3) apare de 2 ori, fib(2) apare de 3 ori, iar pe
măsură ce crește n lucrurile devin catastrofale. Pentru fib(40), același
fib(2) se recalculează de milioane de ori.
Ce citești din arbore
Arborele desenat îți spune trei lucruri concrete:
- Numărul de noduri = timpul. Câte apeluri se fac în total, atâta muncește
programul. La Fibonacci naiv numărul de noduri aproape se dublează când crește
n, deci complexitatea este exponentială, cam O(2^n). - Nodurile care se repetă = nevoia de memoizare. Dacă același nod
(
fib(2),fib(3)...) apare în mai multe locuri, înseamnă că recalculezi aceeași subproblemă. Asta e semnalul clar că ai subprobleme care se suprapun. - Adâncimea = stiva de apeluri. Cel mai lung lanț de la rădăcină până la o
frunză îți spune câte apeluri stau simultan pe stivă. La
fib(n)adâncimea esten, deci memoria de pe stivă crește liniar — chiar dacă timpul crește exponential.
Recalcularea repetată este toată problema. Dacă reții rezultatul fiecărui
fib(k) prima dată când îl calculezi (o tehnică numită memoizare), a doua
oară îl iei gata făcut, fără să mai cobori deloc în subarbore. Arborele „gras”
de mai sus se subțiază: fiecare valoare se calculează o singură dată, iar
complexitatea cade de la O(2^n) la O(n). Memoizarea o studiezi pe larg la
capitolul de programare dinamică — aici e destul să vezi de ce e nevoie de ea.
Greșeli reale legate de arborele de recursie:
- Nu observi recalcularea și folosești Fibonacci naiv pe
nmare: lan = 45programul deja se blochează minute întregi, deși formula pare „simplă”. - Confunzi adâncimea cu numărul de noduri: crezi că stiva ține tot arborele. Nu — pe stivă stă doar drumul curent în jos (adâncimea); restul nodurilor au fost deja calculate și au ieșit de pe stivă.
- Crezi că recursia e mereu lentă: nu este. E lentă doar când subproblemele se suprapun. O parcurgere de arbore sau un divide-et-impera echilibrat (ex. merge sort) au noduri distincte și sunt perfect eficiente.
- Uiți că memoizarea cere memorie: câștigi timp, dar trebuie să stochezi rezultatele (un vector sau o tabelă). Pe subprobleme foarte multe, asta poate însemna multă memorie — nu e magie gratuită.
Recapitulare
- Desenează arborele: nod = apel, copii = subapeluri, frunze = cazuri de bază — și înțelegi dintr-o privire ce face recursia.
- Numărul de noduri = timpul, adâncimea = stiva, nodurile repetate = semnalul că ai nevoie de memoizare.
- Recursia nu e lentă în sine; doar suprapunerea subproblemelor o face exponentială, iar memoizarea o readuce la O(n).