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, !-ის გამოთვლის ამოცანა (თავდაპირველი ამოცანა) უფრო მცირე რიცხვის ფაქტორიალის გამოთვლის ქვეამოცანის ამოხსნით, ანუ, გამოვთვალეთ left parenthesis, n, minus, 1, right parenthesis, ! (იმავე ამოცანის უფრო მცირე შემთხვევა), შემდეგ კი ამ შედეგის გამოყენებით n, !-ის მნიშვნელობის გამოსათვლელად.
იმისთვის, რომ რეკურსიულმა ალგორითმმა იმუშაოს, უფრო მცირე შემთხვევები საბოლოოდ უნდა დავიდნენ ბაზისამდე. როდესაც ვითვლით n, !-ს, ქვეამოცანები უფრო და უფრო მცირდება მანამ, სანამ არ გამოვთვლით 0, !-ს. აუცილებლად უნდა დახვიდეთ საბოლოოდ ბაზისამდე.
მაგალითად, რა მოხდებოდა იმ შემთხვევაში, თუ უარყოფითი რიცხვის ფაქტორიალის გამოთვლას შევეცდებოდით ჩვენი რეკურსიული მეთოდის გამოყენებით? left parenthesis, minus, 1, right parenthesis, !-ის გამოსათვლელად ჯერ შეეცდებოდით left parenthesis, minus, 2, right parenthesis, !-ის გამოთვლას, რათა გაგემრავლებინათ შედეგი minus, 1-ზე. მაგრამ left parenthesis, minus, 2, right parenthesis, !-ის გამოსათვლელად, ჯერ შეეცდებოდით left parenthesis, minus, 3, right parenthesis, !-ის გამოთვლას, რათა შემდეგ შედეგი გაგემრავლებინათ minus, 2-ზე. და შემდეგ შეეცდებოდით გამოგეთვალათ left parenthesis, minus, 3, right parenthesis, ! და ა.შ. რა თქმა უნდა, რიცხვები უფრო და უფრო მცირდება, მაგრამ ისინი აგრეთვე უფრო და უფრო შორდებიან ბაზის 0, !-ს. ვერასდროს მიიღებდით პასუხს.
Even if you can guarantee that the value of n is not negative, you can still get into trouble if you don't make the subproblems progressively smaller. Here's an example. Let's take the formula n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! and divide both sides by n, giving n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !. Let's make a new variable, m, and set it equal to n, plus, 1. Since our formula applies to any positive number, let's substitute m for n, giving m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !. რადგანაც m, equals, n, plus, 1, we now have left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis, equals, left parenthesis, n, plus, 1, minus, 1, right parenthesis, !. Switching sides and noting that n, plus, 1, minus, 1, equals, n gives us n, !, equals, left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis. This formula leads us to believe that you can compute n, ! by first computing left parenthesis, n, plus, 1, right parenthesis, ! and then dividing the result by n, plus, 1. But to compute left parenthesis, n, plus, 1, right parenthesis, !, you would have to compute left parenthesis, n, plus, 2, right parenthesis, !, then left parenthesis, n, plus, 3, right parenthesis, !, and so on. You would never get to the base case of 0. რატომ არა? Because each recursive subproblem asks you to compute the value of a larger number, not a smaller number. If n is positive, you would never hit the base case of 0.
რეკურსიის იდეის ზოგადი სურათის წარმოდგენა შეგვიძლია ორი მარტივი წესით:
  1. რეკურსიის ყოველი გამოძახება უნდა იყოს იმავე ამოცანის შემცირებული ვერსია, ანუ, უფრო მცირე ზომის ქვეამოცანა.
  2. რეკურსიული გამოძახებები საბოლოოდ უნდა დავიდნენ ბაზისამდე, რომელიც იხსნება კერძოდ.
დავუბრუნდეთ მატრიოშკებს (რუსულ თოჯინებს). მიუხედავად იმისა, რომ ისინი არცერთ ალგორითმს არ ასრულებენ, ხედავთ, რომ ყოველი თოჯინა ყველა უფრო პატარა თოჯინას მოიცავს (რეკურსიული შემთხვევის ანალოგიური) მანამ, სანამ ყველაზე პატარა თოჯინა არ მოიცავს არცერთ სხვა თოჯინას (როგორც ბაზისი).

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