Proprietățile algoritmilor recursivi

Iată care este ideea de bază din spatele algoritmilor recursivi:

Când am calculat $n!$‍, am rezolvat problema $n!$‍ (cea inițială) rezolvând o subproblemă de calcul factorial pentru un număr mai mic, adică $(n-1)!$‍ (o instanță mai mică a aceleiași probleme). Apoi, am folosit soluția subproblemei pentru a calcula valoarea lui $n!$‍.

Pentru ca un algoritm recursiv să funcționeze, problemele mai mici trebuie să se finalizeze cu un caz elementar (de bază). Pentru $n!$‍ subproblemele au devenit din ce în ce mai mici, până când am ajuns la $0!$‍. Trebuie să ne asigurăm că la un moment dat se ajunge la cazul elementar.

De exemplu, dacă am fi încercat să calculăm factorialul dintr-un număr negativ folosind metoda recursivă? Pentru a calcula $(-1)!$‍, ar trebui ca mai înainte să știm cât este $(-2)!$‍ ca să îl înmulțim cu $-1$‍. Dar, pentru a calcula $(-2)!$‍ ar trebui să știm cât este $(-3)!$‍ astfel încât să îl putem înmulți cu $-2$‍. Mai departe, ca să calculăm $(-3)!$‍ ar fi trebuit... Desigur, numerele devin tot mai mici, dar în aceeași măsură se și depărtează de cazul elementar $0!$‍. Ca urmare, niciodată nu vom ajunge la un rezultat.

Chiar și atunci când avem garanția că valoarea lui $n$‍ nu este negativă, putem da de necaz dacă nu micșorăm subproblemele progresiv. Iată un exemplu. Hai să luăm formula $n!=n\cdot (n-1)!$‍ și să împărțim ambele părți la $n$‍; obținem $n!/n=(n-1)!$‍. Acum, să luăm o nouă variabilă $m$‍ și să îi atribuim valoarea $n+1$‍. Deoarece formula se aplică oricărui număr pozitiv, hai să îl înlocuim pe $n$‍ cu $m$‍. Obținem $m!/m=(m-1)!$‍. Deoarece $m=n+1$‍, acum avem $(n+1)!/(n+1)=(n+1-1)!$‍. Observând că $n+1-1=n$‍, obținem $n!=(n+1)!/(n+1)$‍. Această formulă ne face să credem că putem calcula $n!$‍ aflând mai întâi pe $(n+1)!$‍, al cărui rezultat să îl împărțim mai apoi la $n+1$‍. Dar, pentru a calcula $(n+1)!$‍, ar trebui ca mai întâi să îl avem pe $(n+2)!$‍, apoi pe $(n+3)!$‍ și tot așa. În felul acesta, nu vom ajunge niciodată la cazul elementar 0. De ce nu? Deoarece fiecare subproblemă recursivă necesită calcularea valorii unui număr mai mare, nu a unuia mai mic. Dacă $n$‍ este pozitiv, nu vom ajunge niciodată la cazul elementar 0.

Putem extrage ideea recursivității respectând două reguli simple:

Să ne întoarcem la păpușile rusești. Chiar dacă nu seamănă cu un algoritm, putem vedea că fiecare păpușă conține toate celelalte păpuși mai mici (analog unui apel recursiv), până când cea mai mică păpușă nu mai conține nimic (cazul elementar).

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.