Recursivitate: adâncimea nu este numărul de apeluri
Calculează separat adâncimea stivei și numărul total de apeluri recursive. Exemplul Fibonacci arată de ce aceeași stare poate fi refăcută repetat.
În acest material
O funcție recursivă se apelează pe ea însăși pentru subprobleme mai mici. Pentru a-i analiza resursele, trebuie să separi două întrebări: câte apeluri sunt active simultan și câte apeluri sunt executate în total.
O ramură și întregul arbore
Adâncimea este lungimea maximă a unui lanț de apeluri care nu s-au încheiat încă. Numărul total de apeluri include toate ramurile, chiar dacă ele sunt executate pe rând. O adâncime mică nu garantează un număr mic de operații.
În calculul recursiv direct al lui Fibonacci, F(n) cere F(n-1) și F(n-2). Pentru F(5), apelul F(3) apare atât sub F(4), cât și direct ca a doua ramură. Mai jos, aceleași subprobleme se repetă din nou.
De ce timpul crește repede
Fără memorare, arborele de apeluri are multe ramuri repetate. Numărul apelurilor crește exponențial în n, deși adâncimea maximă este liniară. Nu înmulți pur și simplu adâncimea cu două pentru a estima toate nodurile arborelui.
Un desen pentru n=5 sau n=6 face repetările vizibile. Marchează fiecare apariție a aceleiași valori a parametrului. Observi că programul nu folosește rezultatul deja calculat într-o altă ramură, deoarece nu l-a păstrat într-o structură comună.
În calculul recursiv direct F(5)=F(4)+F(3), ramura F(4)=F(3)+F(2) recalculează F(3). Memoizarea păstrează rezultatul pentru reutilizare.Mărește schema ↗
Memorarea schimbă numărul de calcule
Memorarea rezultatelor subproblemelor, numită memoizare, păstrează valoarea lui F(k) după prima calculare. La următoarea cerere pentru același k, rezultatul este reutilizat. Pentru această recurență, fiecare stare relevantă este calculată o singură dată.
O variantă iterativă poate calcula valorile în ordine crescătoare și poate păstra doar ultimele două, dacă nu ai nevoie de toate rezultatele intermediare. Aceasta schimbă și memoria auxiliară, nu doar forma sintactică a programului.
Limita tipului numeric rămâne separată
Un algoritm mai rapid poate ajunge mai repede la valori care nu încap în tipul ales. Optimizarea timpului nu rezolvă depășirea numerică. Stabilește dacă problema cere valoarea exactă, un rest modulo un număr sau o reprezentare cu mai multe cifre.
La verificare, numără apelurile pentru câteva valori mici și compară cu numărul stărilor distincte. Apoi urmărește separat adâncimea maximă. Aceste două măsurători explică resurse diferite și nu trebuie amestecate.
Continuă cu recursivitatea, programarea dinamică și complexitatea.
Întrebări frecvente
Care este diferența dintre adâncimea recursiei și numărul apelurilor?
Adâncimea este numărul maxim de apeluri active simultan pe un lanț. Numărul total include toate apelurile executate pe toate ramurile, chiar dacă acestea se desfășoară pe rând.
De ce Fibonacci recursiv simplu este lent?
Recalculează aceleași valori în ramuri diferite. Numărul apelurilor crește exponențial, deși adâncimea maximă este liniară în n. Memoizarea sau calculul iterativ evită repetarea subproblemelor.
Memoria stivei este dată de numărul total de apeluri?
Nu. Contează numărul apelurilor active simultan și memoria fiecărui cadru de apel. Apelurile deja încheiate nu își păstrează toate cadrele pe stivă.