Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 6: Recursivitate- Recursivitatea
- Funcția factorial
- Provocare: factorialul iterativ
- Factorialul recursiv
- Provocare: factorial recursiv
- Proprietățile algoritmilor recursivi
- Folosirea recursivității pentru a determina dacă un cuvânt este sau nu palindrom
- Provocare: este un șir palindrom?
- Provocare: puteri recursive
- Recursie multiplă cu triunghiul lui Sierpinski
- Îmbunătățirea eficienței funcțiilor recursive
- Proiect: artă recursivă
© 2023 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie
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 , am rezolvat problema (cea inițială) rezolvând o subproblemă de calcul factorial pentru un număr mai mic, adică (o instanță mai mică a aceleiași probleme). Apoi, am folosit soluția subproblemei pentru a calcula valoarea lui .
Pentru ca un algoritm recursiv să funcționeze, problemele mai mici trebuie să se finalizeze cu un caz elementar (de bază). Pentru subproblemele au devenit din ce în ce mai mici, până când am ajuns la . 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 , ar trebui ca mai înainte să știm cât este ca să îl înmulțim cu . Dar, pentru a calcula ar trebui să știm cât este astfel încât să îl putem înmulți cu . Mai departe, ca să calculăm ar fi trebuit... Desigur, numerele devin tot mai mici, dar în aceeași măsură se și depărtează de cazul elementar . Ca urmare, niciodată nu vom ajunge la un rezultat.
Chiar și atunci când avem garanția că valoarea lui nu este negativă, putem da de necaz dacă nu micșorăm subproblemele progresiv. Iată un exemplu. Hai să luăm formula și să împărțim ambele părți la ; obținem . Acum, să luăm o nouă variabilă și să îi atribuim valoarea . Deoarece formula se aplică oricărui număr pozitiv, hai să îl înlocuim pe cu . Obținem . Deoarece , acum avem . Observând că , obținem . Această formulă ne face să credem că putem calcula aflând mai întâi pe , al cărui rezultat să îl împărțim mai apoi la . Dar, pentru a calcula , ar trebui ca mai întâi să îl avem pe , apoi pe ș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ă este pozitiv, nu vom ajunge niciodată la cazul elementar 0.
Putem extrage ideea recursivității respectând două reguli simple:
- Fiecare apel recursiv ar trebui să fie o instanță mai mică a aceleiași probleme, adică o subproblemă mai mică.
- 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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.
Vrei să te alături conversației?
Nici o postare încă.