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

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(n1)21. Dar să observăm că (n1)21 este de fapt (n1)!; așadar, putem spune că n!=n(n1)!. Ce zici? L-am scris pe n! ca produs având unul dintre factori (n1)!. Deci îl putem calcula pe n! determinând mai întâi (n1)! și înmulțindu-l apoi cu n. Poți calcula funcția factorial de n prin calcularea factorialului de n1. Putem spune că problema (n1)! este o subproblemă a calculării lui n!.
Hai să luăm un exemplu: calcularea lui 5!.
  • Putem calcula 5! înmulțind 54!.
  • Acum trebuie să rezolvăm subproblema calculării lui 4!, pe care o putem privi ca fiind 43!.
  • Dar acum trebuie să calculăm 3!, care este 32!.
  • Avem 2!, care este 21!.
  • 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!=10!. Să aplicăm formula.
  • Am stabilit că 0! este egal cu 1.
  • Acum putem să calculăm 1!=10!=1.
  • Știind că 1!=1, putem calcula 2!=21!=2.
  • Mai departe, pentru că 2!=2,putem calcula 3!=32!=6.
  • Înlocuind 3!=6, putem calcula 4!=43!=24.
  • În sfârșit, pentru că 4!=24, putem finaliza calculul 5!=54!=120.
Avem încă o modalitate de a calcula valoarea lui n! pentru toate numerele n naturale:
  • Dacă n=0, atunci spunem că n!=1.
  • Altfel, n trebuie să fie pozitiv. Rezolvăm subproblema calculării lui (n1)!, î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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.