De ce contează?
Gândește-te la un arbore genealogic: tu ești în vârf, sub tine sunt cei doi părinți, sub fiecare părinte alți doi bunici, și tot așa. O funcție recursivă arată exact la fel — doar că „strămoșii" sunt apelurile pe care funcția le face mai departe. Dacă desenezi acest arbore, vezi cu ochii cât timp pierde programul: e un lanț subțire care coboară lin, sau o tufă care se umflă exploziv la fiecare nivel?
Ideea-cheie
Când vezi recursie, nu urmări apelurile în minte ca pe o listă lungă — desenează-le ca pe un arbore. Regula de traducere e simplă și mereu aceeași:
- fiecare apel al funcției = un nod;
- apelurile pe care le face acel apel = copiii nodului;
- cazul de bază (apelul care nu mai cheamă pe nimeni) = o frunză;
- numărul de noduri din arbore = numărul total de apeluri — adică exact câtă muncă face programul.
Aceasta nu e o tehnică nouă, ci o lentilă. Odată ce vezi recursia ca arbore, complexitatea nu mai trebuie memorată: o citești din formă. Un arbore care coboară ca un fir are puține noduri (cost mic); un arbore care se ramifică la fiecare pas are noduri câte frunze de copac (cost mare).
Tradu mereu: apel = nod, copiii nodului = apelurile pe care le face, caz de bază = frunză. Atunci „cât costă recursia?" devine întrebarea ușoară „câte noduri are arborele?". Costul nu stă în adâncime, ci în câte noduri sunt în total.