რეკურსიული ფაქტორიალი

$n$n-ის დადებითი მნიშვნელობებისთვის დავწეროთ $n!$n, !, როგორც ადრე ვქენით, როგორც ნამრავლი $n$n-იდან 1-მდე: $n!$n, ! = $n \cdot (n-1) \cdots 2 \cdot 1$n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. მაგრამ აღვნიშნოთ, რომ $(n-1) \cdots 2 \cdot 1$left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 არის $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !-ის ჩაწერის ერთ-ერთი გზა და, შესაბამისად, შეგვიძლია, ვთქვათ, რომ $n! = n \cdot (n-1)!$n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. ნახეთ, რა ვქენით? $n!$n, ! ჩავწერეთ ნამრავლად, რომელთაგან ერთ-ერთი მამრავლი არის $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !. ჩვენ ვთქვით, რომ $n!$n, !-ის გამოთვლა შეგიძლიათ $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !-ის გამოთვლით და შემდეგ $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !-ის შედეგის გამრავლებით $n$n-ზე. $n$n-ის ფაქტორიალის ფუნქციის გამოთვლა შეგიძლიათ ჯერ $n-1$n, minus, 1-ის გამოთვლით. ვამბობთ, რომ $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !-ის გამოთვლა არის ქვეამოცანა, რომელიც უნდა ამოვხსნათ $n$n!-ის გამოსათვლელად.

მოდით, შევხედოთ მაგალითს: 5!-ის გამოთვლა.

ანუ, ახლა ჩვენ გვაქვს $n!$n, !-ის გამოთვლაზე ფიქრის კიდევ ერთი გზა ყველა არაუარყოფითი მთელი რიცხვი $n$n-ისთვის:

როდესაც ვითვლით $n!$n, !-ს ამ გზით, პირველ შემთხვევას, რომელზე პასუხიც დაუყოვნებლივ ვიცით, ვეძახით ბაზისს და მეორე შემთხვევას, რომელშიც უნდა გამოვთვალოთ იგივე ფუნქცია, მაგრამ სხვა მნიშვნელობაზე, ვეძახით რეკურსიულ შემთხვევას.

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.