რეკურსია

რუსული თოჯინები — მატრიოშკები — გინახავთ? თავიდან მხოლოდ ერთ ფიგურას ხედავთ, რომელიც ძირითადად არის შეღებილი ხე და ამგვარად გამოიყურება:

შეგიძლიათ, პირველ თოჯინას ზედა ნახევარი მოხსნათ, და რას ხედავთ შიგნით? კიდევ ერთი, მაგრამ ოდნავ უფრო პატარა მატრიოშკა!

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

ერთხელაც დაამატეთ:

შეგიძლიათ, ასე გააგრძელოთ მანამ, სანამ პაწაწინა თოჯინამდე მიხვალთ. ის მხოლოდ ერთი ნაწილისგან შედგება და, შესაბამისად, არ იხსნება:

დავიწყეთ ერთი დიდი მატრიოშკით და ვნახეთ უფრო და უფრო პატარა თოჯინები მანამ, სანამ იმდენად პატარა თოჯინას არ მივადექით, რომელიც სხვა თოჯინას ვეღარ დაიტევდა.

რა საერთო აქვს მატრიოშკებსა და ალგორითმებს? ისევე, როგორც ერთ მატრიოშკაში არის მეორე, უფრო პატარა მატრიოშკა, რომელიც შეიცავს კიდევ უფრო პატარა მატრიოშკას და ასე გრძელდება პაწაწინა მატრიოშკამდე, რომელიც უკვე ვეღარ შეიცავს სხვა თოჯინას, ვნახავთ, როგორ დავწეროთ ალგორითმი, რომელიც ამოცანას ხსნის იმავე ამოცანის უფრო პატარა შემთხვევის ამოხსნით, გარდა იმ შემთხვევისა, როცა ამოცანა იმდენად პატარაა, რომ მისი ამოხსნა პირდაპირ შეგვიძლია. ამ ტექნიკას რეკურსიას ვუწოდებთ.

რეკურსიას ძალიან ბევრი გამოყენება აქვს. ამ მოდულში ვნახავთ, როგორ გამოვიყენოთ რეკურსია ფაქტორიალის ფუნქციის ამოსახსნელად, ასევე იმის გასარკვევად, არის თუ არა მოცემული სიტყვა პალინდრომი, რიცხვის ხარისხების გამოსათვლელად, ფრაქტალის ტიპის დასახატად და ჰანოის უძველესი კოშკების ამოცანის ამოსახსნელად. შემდეგ მოდულებში რეკურსიას გამოვიყენებთ სხვა ამოცანების ამოსახსნელად, მათ შორის სორტირებისთვის.

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