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
Factorialul recursiv
Pentru valorile pozitive ale lui n hai să scriem n, ! ca fiind produsul tuturor numerelor de la n până la 1: n, ! = n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. Dar să observăm că left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 este de fapt left parenthesis, n, minus, 1, right parenthesis, !; așadar, putem spune că n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. Ce zici? L-am scris pe n, ! ca produs având unul dintre factori left parenthesis, n, minus, 1, right parenthesis, !. Deci îl putem calcula pe n, ! determinând mai întâi left parenthesis, n, minus, 1, right parenthesis, ! și înmulțindu-l apoi cu n. Poți calcula funcția factorial de n prin calcularea factorialului de n, minus, 1. Putem spune că problema left parenthesis, n, minus, 1, right parenthesis, ! este o subproblemă a calculării lui n!.
Hai să luăm un exemplu: calcularea lui 5!.
- Putem calcula 5! înmulțind 5, dot, 4, !.
- Acum trebuie să rezolvăm subproblema calculării lui 4!, pe care o putem privi ca fiind 4, dot, 3!.
- Dar acum trebuie să calculăm 3!, care este 3, dot, 2, !.
- Avem 2!, care este 2, dot, 1, !.
- Ne trebuie 1!. Putem spune că 1! este egal cu 1, deoarece este produsul tuturor numerelor de la 1 la 1. Sau, am putea aplica formula conform căreia 1, !, equals, 1, dot, 0, !. Să aplicăm formula.
- Am stabilit că 0! este egal cu 1.
- Acum putem să calculăm 1, !, equals, 1, dot, 0, !, equals, 1.
- Știind că 1, !, equals, 1, putem calcula 2, !, equals, 2, dot, 1, !, equals, 2.
- Mai departe, pentru că 2, !, equals, 2,putem calcula 3, !, equals, 3, dot, 2, !, equals, 6.
- Înlocuind 3, !, equals, 6, putem calcula 4, !, equals, 4, dot, 3, !, equals, 24.
- În sfârșit, pentru că 4, !, equals, 24, putem finaliza calculul 5, !, equals, 5, dot, 4, !, equals, 120.
Avem încă o modalitate de a calcula valoarea lui n, ! pentru toate numerele n naturale:
- Dacă n, equals, 0, atunci spunem că n, !, equals, 1.
- Altfel, n trebuie să fie pozitiv. Rezolvăm subproblema calculării lui left parenthesis, n, minus, 1, right parenthesis, !, înmulțim rezultatul cu n și concluzionăm că n, ! este egal cu rezultatul acestui produs.
Când calculăm n, ! în acest mod, mai întâi apelăm primul caz, cel pentru care știm direct răspunsul, caz pe care îl numim caz elementar, apoi apelăm al doilea caz, cel pentru care trebuie să calculăm aceeași funcție dar pentru o altă valoare; acesta se numește caz recursiv.
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.
Vrei să te alături conversației?
Nici o postare încă.