If you're seeing this message, it means we're having trouble loading external resources on our website.

Dacă sunteţi în spatele unui filtru de web, vă rugăm să vă asiguraţi că domeniile *. kastatic.org şi *. kasandbox.org sunt deblocate.

Conţinutul principal

Proprietățile algoritmilor recursivi

Iată care este ideea de bază din spatele algoritmilor recursivi:
Pentru a rezolva o problemă, rezolvăm o subproblemă care este o instanță de ordin mai mic a aceleiași probleme, apoi folosim soluția instanței mai mici pentru a rezolva problema inițială.
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ă 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, !.
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 left parenthesis, minus, 1, right parenthesis, !, ar trebui ca mai înainte să știm cât este left parenthesis, minus, 2, right parenthesis, ! ca să îl înmulțim cu minus, 1. Dar, pentru a calcula left parenthesis, minus, 2, right parenthesis, ! ar trebui să știm cât este left parenthesis, minus, 3, right parenthesis, ! astfel încât să îl putem înmulți cu minus, 2. Mai departe, ca să calculăm 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, !. 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, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! și să împărțim ambele părți la n; obținem n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !. Acum, să luăm o nouă variabilă m și să îi atribuim valoarea n, plus, 1. Deoarece formula se aplică oricărui număr pozitiv, hai să îl înlocuim pe n cu m. Obținem m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !. Deoarece m, equals, n, plus, 1, acum avem 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, plus, 1, minus, 1, equals, n, obținem 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, ! aflând mai întâi pe left parenthesis, n, plus, 1, right parenthesis, !, al cărui rezultat să îl împărțim mai apoi la n, plus, 1. Dar, pentru a calcula left parenthesis, n, plus, 1, right parenthesis, !, ar trebui ca mai întâi să îl avem pe left parenthesis, n, plus, 2, right parenthesis, !, apoi pe 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 este pozitiv, nu vom ajunge niciodată la cazul elementar 0.
Putem extrage ideea recursivității respectând două reguli simple:
  1. Fiecare apel recursiv ar trebui să fie o instanță mai mică a aceleiași probleme, adică o subproblemă mai mică.
  2. Apelurile recursive trebuie să se termine cu un caz elementar, care poate fi rezolvat fără alte apeluri recursive.
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.