Proprietățile algoritmilor recursivi

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

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

Pentru ca un algoritm recursiv să funcționeze, problemele mai mici trebuie să se finalizeze cu un caz elementar (de bază). Pentru $n!$n, ! subproblemele au devenit din ce în ce mai mici, până când am ajuns la $0!$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)!$left parenthesis, minus, 1, right parenthesis, !, ar trebui ca mai înainte să știm cât este $(-2)!$left parenthesis, minus, 2, right parenthesis, ! ca să îl înmulțim cu $-1$minus, 1. Dar, pentru a calcula $(-2)!$left parenthesis, minus, 2, right parenthesis, ! ar trebui să știm cât este $(-3)!$left parenthesis, minus, 3, right parenthesis, ! astfel încât să îl putem înmulți cu $-2$minus, 2. Mai departe, ca să calculăm $(-3)!$left parenthesis, minus, 3, right parenthesis, ! ar fi trebuit... Desigur, numerele devin tot mai mici, dar în aceeași măsură se și depărtează de cazul elementar $0!$0, !. Ca urmare, niciodată nu vom ajunge la un rezultat.

Chiar și atunci când avem garanția că valoarea lui $n$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)!$n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! și să împărțim ambele părți la $n$n; obținem $n! / n = (n-1)!$n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !. Acum, să luăm o nouă variabilă $m$m și să îi atribuim valoarea $n+1$n, plus, 1. Deoarece formula se aplică oricărui număr pozitiv, hai să îl înlocuim pe $n$n cu $m$m. Obținem $m! / m = (m-1)!$m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !. Deoarece $m = n+1$m, equals, n, plus, 1, acum avem $(n+1)! / (n+1) = (n+1-1)!$left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis, equals, left parenthesis, n, plus, 1, minus, 1, right parenthesis, !. Observând că $n+1-1 = n$n, plus, 1, minus, 1, equals, n, obținem $n! = (n+1)! / (n+1)$n, !, equals, left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis. Această formulă ne face să credem că putem calcula $n!$n, ! aflând mai întâi pe $(n+1)!$left parenthesis, n, plus, 1, right parenthesis, !, al cărui rezultat să îl împărțim mai apoi la $n+1$n, plus, 1. Dar, pentru a calcula $(n+1)!$left parenthesis, n, plus, 1, right parenthesis, !, ar trebui ca mai întâi să îl avem pe $(n+2)!$left parenthesis, n, plus, 2, right parenthesis, !, apoi pe $(n+3)!$left parenthesis, n, plus, 3, right parenthesis, ! ș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$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ă a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.