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

აი, რეკურსიული ალგორითმების მთავარი იდეა:

$n!$‍-ის გამოთვლისას, ჩვენ ამოვხსენით $n!$‍-ის გამოთვლის ამოცანა (თავდაპირველი ამოცანა) უფრო მცირე რიცხვის ფაქტორიალის გამოთვლის ქვეამოცანის ამოხსნით, ანუ, გამოვთვალეთ $(n-1)!$‍ (იმავე ამოცანის უფრო მცირე შემთხვევა), შემდეგ კი ამ შედეგის გამოყენებით $n!$‍-ის მნიშვნელობის გამოსათვლელად.

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

მაგალითად, რა მოხდებოდა იმ შემთხვევაში, თუ უარყოფითი რიცხვის ფაქტორიალის გამოთვლას შევეცდებოდით ჩვენი რეკურსიული მეთოდის გამოყენებით? $(-1)!$‍-ის გამოსათვლელად ჯერ შეეცდებოდით $(-2)!$‍-ის გამოთვლას, რათა გაგემრავლებინათ შედეგი $-1$‍-ზე. მაგრამ $(-2)!$‍-ის გამოსათვლელად, ჯერ შეეცდებოდით $(-3)!$‍-ის გამოთვლას, რათა შემდეგ შედეგი გაგემრავლებინათ $-2$‍-ზე. და შემდეგ შეეცდებოდით გამოგეთვალათ $(-3)!$‍ და ა.შ. რა თქმა უნდა, რიცხვები უფრო და უფრო მცირდება, მაგრამ ისინი აგრეთვე უფრო და უფრო შორდებიან ბაზის $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!=n\cdot (n-1)!$‍ and divide both sides by $n$‍, giving $n!/n=(n-1)!$‍. Let's make a new variable, $m$‍, and set it equal to $n+1$‍. Since our formula applies to any positive number, let's substitute $m$‍ for $n$‍, giving $m!/m=(m-1)!$‍. რადგანაც $m=n+1$‍, we now have $(n+1)!/(n+1)=(n+1-1)!$‍. Switching sides and noting that $n+1-1=n$‍ gives us $n!=(n+1)!/(n+1)$‍. This formula leads us to believe that you can compute $n!$‍ by first computing $(n+1)!$‍ and then dividing the result by $n+1$‍. But to compute $(n+1)!$‍, you would have to compute $(n+2)!$‍, then $(n+3)!$‍, 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.

რეკურსიის იდეის ზოგადი სურათის წარმოდგენა შეგვიძლია ორი მარტივი წესით:

დავუბრუნდეთ მატრიოშკებს (რუსულ თოჯინებს). მიუხედავად იმისა, რომ ისინი არცერთ ალგორითმს არ ასრულებენ, ხედავთ, რომ ყოველი თოჯინა ყველა უფრო პატარა თოჯინას მოიცავს (რეკურსიული შემთხვევის ანალოგიური) მანამ, სანამ ყველაზე პატარა თოჯინა არ მოიცავს არცერთ სხვა თოჯინას (როგორც ბაზისი).

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