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

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა

კომპიუტერული მეცნიერება

თემა 1: გაკვეთილი 6

რეკურსიული ალგორითმები

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

n-ის დადებითი მნიშვნელობებისთვის დავწეროთ n, !, როგორც ადრე ვქენით, როგორც ნამრავლი n-იდან 1-მდე: n, ! = n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. მაგრამ აღვნიშნოთ, რომ left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 არის left parenthesis, n, minus, 1, right parenthesis, !-ის ჩაწერის ერთ-ერთი გზა და, შესაბამისად, შეგვიძლია, ვთქვათ, რომ n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, !. ნახეთ, რა ვქენით? n, ! ჩავწერეთ ნამრავლად, რომელთაგან ერთ-ერთი მამრავლი არის left parenthesis, n, minus, 1, right parenthesis, !. ჩვენ ვთქვით, რომ n, !-ის გამოთვლა შეგიძლიათ left parenthesis, n, minus, 1, right parenthesis, !-ის გამოთვლით და შემდეგ left parenthesis, n, minus, 1, right parenthesis, !-ის შედეგის გამრავლებით n-ზე. n-ის ფაქტორიალის ფუნქციის გამოთვლა შეგიძლიათ ჯერ n, minus, 1-ის გამოთვლით. ვამბობთ, რომ left parenthesis, n, minus, 1, right parenthesis, !-ის გამოთვლა არის ქვეამოცანა, რომელიც უნდა ამოვხსნათ n!-ის გამოსათვლელად.
მოდით, შევხედოთ მაგალითს: 5!-ის გამოთვლა.
  • შეგიძლიათ, 5! გამოთვალოთ, როგორც 5, dot, 4, !.
  • ახლა თქვენ უნდა ამოხსნათ 4!-ის გამოთვლის ქვეამოცანა, რომლის გამოთვლაც შეგიძლიათ, როგორც 4, dot, 3!.
  • ახლა თქვენ უნდა ამოხსნათ 3!-ის გამოთვლის ქვეამოცანა, რომელიც არის 3, dot, 2, !.
  • ახლა 2!, რომელიც არის 2, dot, 1, !.
  • ახლა უნდა გამოთვალოთ 1!. შეგიძლიათ, თქვათ, რომ 1! უდრის 1-ს, ვინაიდან ის არის ყველა მთელი რიცხვის ნამრავლი 1-იდან 1-მდე. ან შეგიძლიათ, გამოიყენოთ ფორმულა: 1, !, equals, 1, dot, 0, !. გავაკეთოთ ეს ფორმულის გამოყენებით.
  • ჩვენ განვსაზღვრეთ, რომ 0! უდრის 1-ს.
  • ახლა შეგიძლიათ, გამოთვალოთ 1, !, equals, 1, dot, 0, !, equals, 1.
  • მას შემდეგ, რაც გამოვთვალეთ 1, !, equals, 1, შეგვიძლია, გამოვთვალოთ 2, !, equals, 2, dot, 1, !, equals, 2.
  • 2, !, equals, 2-ის გამოთვლის შემდეგ შეგვიძლია, გამოვთვალოთ 3, !, equals, 3, dot, 2, !, equals, 6.
  • 3, !, equals, 6-ის გამოთვლის შემდეგ შეგვიძლია, გამოვთვალოთ 4, !, equals, 4, dot, 3, !, equals, 24.
  • ბოლოს, 4, !, equals, 24-ის გამოთვლის შემდეგ შეგვიძლია, დავასრულოთ 5, !, equals, 5, dot, 4, !, equals, 120-ით.
ანუ, ახლა ჩვენ გვაქვს n, !-ის გამოთვლაზე ფიქრის კიდევ ერთი გზა ყველა არაუარყოფითი მთელი რიცხვი n-ისთვის:
  • თუ n, equals, 0, მაშინ ვაცხადებთ, რომ n, !, equals, 1.
  • წინააღმდეგ შემთხვევაში, n უნდა იყოს დადებითი. ამოხსენით left parenthesis, n, minus, 1, right parenthesis, !-ის გამოთვლის ქვეამოცანა, გაამრავლეთ ეს შედეგი n-ზე და გამოაცხადეთ n, ! ამ ნამრავლის ტოლად.
როდესაც ვითვლით n, !-ს ამ გზით, პირველ შემთხვევას, რომელზე პასუხიც დაუყოვნებლივ ვიცით, ვეძახით ბაზისს და მეორე შემთხვევას, რომელშიც უნდა გამოვთვალოთ იგივე ფუნქცია, მაგრამ სხვა მნიშვნელობაზე, ვეძახით რეკურსიულ შემთხვევას.

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