ოდესმე დაგიჭერიათ ერთი შეხედვით დაუსრულებელ ციკლში, სადაც პრობლემა იშლება პატარა ფრაგმენტებად?
თუ ასეა, თქვენ შეიძლება მოხვდეთ რეკურსიის მომხიბვლელ სამყაროში. მიუხედავად იმისა, რომ შეიძლება რთული იყოს გაგება, არ ინერვიულოთ! ამ პოსტში ჩვენ წავალთ საინტერესო მოგზაურობას, რათა გავიგოთ რეკურსიების ტიპების შესახებ.
ასე რომ ბალთა up როგორც ჩვენ ვიკვლევთ უამრავ რეკურსიულ მიდგომას. მოემზადეთ რეკურსიის მომხიბლავ სამყაროში შესასვლელად და დააკვირდით მის გასაოცარ უნარს რთული საკითხების გადაჭრაში.
რა არის ზუსტად რეკურსიები?
ძირითადი სიტყვებით, რეკურსია არის მძლავრი პროგრამირების ტექნიკა, რომელიც მოიცავს ფუნქციის გამოძახებას შესრულების დროს. ეს ჰგავს სარკეში ჩახედვას და გამოსახულების შიგნით გამოსახულებას, რაც იწვევს თვითრეფერენციალურ ციკლს.
ჩვენ შეგვიძლია გავუმკლავდეთ დიდ პრობლემებს რეკურსიის გამოყენებით, მათი დაყოფით უფრო მცირე, უფრო მართვად ქვეპრობლემებად.
ეს ჰგავს ჯიგსოლს, სადაც ერთი ნაწილი უერთდება სხვა ნაწილებს სრული სურათის შესაქმნელად. რეკურსია საშუალებას გვაძლევს გადავჭრათ საკითხები ელეგანტურად და ეფექტურად, ინსტრუქციების იგივე ნაკრების გამეორებით სხვადასხვა შეყვანით.
1-პირდაპირი რეკურსია
პირდაპირი რეკურსია არის რეკურსიის ყველაზე ძირითადი ტიპი, რომელშიც ფუნქცია პირდაპირ იძახის საკუთარ თავს. ის გულისხმობს პრობლემური პრობლემის მცირე ქვეპრობლემებად დაყოფას საბაზისო შემთხვევის მიღწევამდე, რაც იწვევს შეწყვეტას.
რეკურსიული ფუნქცია თავის თავს იძახებს სხვადასხვა შეყვანით, რაც საშუალებას აძლევს ინსტრუქციების იგივე ნაკრების განმეორებას. თითოეული გამოძახება ეფუძნება წინას, თანდათან უახლოვდება საბაზისო შემთხვევას, რაც იწვევს რეკურსიის დასრულებას.
მოდით შევამოწმოთ ეს მაგალითი.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
გამოყვანის:
5
4
3
2
1
2-ირიბი რეკურსია
არაპირდაპირი რეკურსია რეკურსიულ გზას დამაინტრიგებელ ელფერს მატებს. პირდაპირი რეკურსიისგან განსხვავებით, რომელიც გულისხმობს ფუნქციის გამოძახებას, არაპირდაპირი რეკურსი მოიცავს ფუნქციის გამოძახების ჯაჭვს.
ერთი ფუნქცია იძახებს მეორეს, რომელსაც შემდეგ შეუძლია გამოიძახოს ორიგინალური ფუნქცია ან ნებისმიერი სხვა ფუნქცია, რომელიც საბოლოოდ დაუბრუნდება ორიგინალს. ფუნქციების ზარების ეს ურთიერთდაკავშირებული ქსელი წარმოქმნის მომხიბვლელ ცეკვას, რომელშიც რამდენიმე ფუნქცია თანამშრომლობს პრობლემის გადასაჭრელად.
მაგალითი:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
გამოყვანის:
A: 3
B: 2
A: 1
3-ხაზოვანი რეკურსია
განიხილეთ მოგზაურობა სწორი მარშრუტით, თითო ნაბიჯით, სანამ არ მიაღწევთ თქვენს მიზანს. ეს თანმიმდევრული ტექნიკა განსახიერებულია წრფივი რეკურსიით, რომელშიც ფუნქცია ასრულებს ერთ რეკურსიულ გამოძახებას თითოეულ ფუნქციის გამეორებაში.
ყოველი რეკურსიული გამოძახებით, რეკურსიული პროცესი უფრო უახლოვდება საბაზისო საქმეს გამოცემის ზომის შემცირებით. იგი მიმდინარეობს მკაფიო და წრფივი გზით, წყვეტს ქვეპრობლემებს სათითაოდ, სანამ საბოლოო პასუხი არ იქნება მიღწეული.
მაგალითი:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
გამოყვანის:
120
4-ხის რეკურსია
როდესაც ფუნქცია განშტოდება რამდენიმე რეკურსიულ ზარად, ჩვენ შევდივართ ხის რეკურსიის სამყაროში. ხის რეკურსიაში ფუნქცია წარმოქმნის ბევრ რეკურსიულ ზარს, რომელთაგან თითოეული წყვეტს ცალკეულ ქვეპრობლემას, ისევე როგორც ხის ტოტები.
ეს განშტოების სტრუქტურა იძლევა რამდენიმე მარშრუტის ერთდროული გამოკვლევის საშუალებას, რაც ეფექტურად დაყოფს რთულ საკითხებს მცირე, ურთიერთდაკავშირებულ კომპონენტებად.
მაგალითი:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
გამოყვანის:
8
5-ჩადგმული რეკურსია
ჩადგმული რეკურსია სირთულის საინტერესო ხარისხს მატებს რეკურსიულ სამყაროს. რეკურსიის ამ ფორმით, ფუნქცია აერთიანებს რეკურსიულ ზარს, როგორც არგუმენტს სხვა რეკურსიული ზარის ფარგლებში.
შიდა რეკურსიული ზარი მოქმედებს მნიშვნელობაზე, რომელიც დამოკიდებულია გარე რეკურსიულ ზარზე. სირთულე იზრდება ყოველი ჩადგმული გამოძახებით, რაც მთავრდება ჩადგმული რეკურსიული ზარების დამაინტრიგებელი ნიმუშით.
მაგალითი:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
შედეგი:
91
6-კუდის რეკურსია
კუდის რეკურსია არის რეკურსიული ალგორითმების ოპტიმიზაციის ტექნიკა, რომელსაც შეუძლია გააუმჯობესოს მათი შესრულება. რეკურსიული გამოძახება ჩნდება, როგორც ფუნქციის საბოლოო მოქმედება კუდის რეკურსიით, რაც ხდება.
იმის გამო, რომ არ არის გამორჩეული ოპერაციები რეკურსიული ზარის შემდეგ, შემდგენელს ან თარჯიმანს შეუძლია გაამარტივოს რეკურსია მისი მარტივი ნახტომით ჩანაცვლებით.
ეს ოპტიმიზაციის მიდგომა, რომელიც ცნობილია როგორც კუდიანი ზარის ოპტიმიზაცია, ამცირებს თითოეული რეკურსიული ზარის მოთხოვნას სტეკის ჩარჩოს შესანარჩუნებლად, რაც იწვევს გაძლიერებულ სიჩქარეს და მეხსიერების შემცირებას.
მაგალითი:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
გასასვლელი:
120
7-არაკუდის რეკურსია
კუდის რეკურსიისგან განსხვავებით, არაკუდის რეკურსია მოიცავს დამატებით აქტივობებს, რომლებიც შესრულებულია ფუნქციის ფარგლებში რეკურსიული ზარის შემდეგ. სხვა მოქმედებების შესრულებამდე, ყოველი რეკურსიული ზარი უნდა დასრულდეს და დაბრუნდეს.
შედეგად, სანამ საბაზისო შემთხვევა არ იქნება მიღწეული და რეკურსიის დასრულება, შენარჩუნებულია გამორჩეული ოპერაციების დასტა. არაკუდის რეკურსია ხშირად იყენებს მეტ მეხსიერებას და ნაკლებად ეფექტურია, ვიდრე კუდის რეკურსია, მაგრამ ის მაინც სასარგებლო ინსტრუმენტია სხვადასხვა საკითხების მოსაგვარებლად.
მაგალითი:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
გამოყვანის:
15
გახვევა
რეკურსია პროგრამირების საინტერესო კონცეფციაა. ის საშუალებას გვაძლევს გავუმკლავდეთ რთულ პრობლემებს რეკურსიული, თვითრეფერენციული გზით.
ის გვთავაზობს პრობლემების შესახებ ფიქრისა და გადაჭრის განსხვავებულ მეთოდს, მათ დაყოფას უფრო მცირე, უფრო მართვად ნაწილებად. თუმცა, რეკურსიასთან მუშაობისას მნიშვნელოვანია გამოიყენოს ყურადღება მიაქციეთ ზოგიერთ პუნქტს.
თქვენ უნდა გამოავლინოთ შესაბამისი საბაზისო შემთხვევები, რომლებიც საშუალებას აძლევს რეკურსიის დასრულებას. თუ ისინი არ არიან, ფუნქციამ შეიძლება სამუდამოდ განაგრძოს თავის გამოძახება.
მეორე, არსებული სცენარიდან გამომდინარე, შესაბამისი ტიპის რეკურსიის არჩევამ შეიძლება გამოიწვიოს უფრო ეფექტური და ელეგანტური გადაწყვეტილებები. შეეცადეთ იპოვოთ ის, რაც საუკეთესოდ მუშაობს ხელის პრობლემაზე. როდესაც მუშაობთ უზარმაზარ რეკურსიულ სიღრმეებთან, გაითვალისწინეთ პოტენციური საფრთხეები, როგორიცაა სტეკის გადინება.
დატოვე პასუხი