რეკურსია და გამოძახებათა სტეკი

ხეები, „დაყავი და იბატონე“ სორტირება, უკუსვლით ძებნა და DFS, ყველა რეკურსიაა. როგორც კი გამოძახებათა სტეკს თვალით დაინახავ, ეს ალგორითმები ჯადოქრობად აღარ მოგეჩვენება.

დამწყები⏱ 12 წთ

←ეყრდნობა

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

გზას უხსნის→

2შერწყმით სორტირება: დაყავი და იბატონეშერწყმით სორტირება თავის თავს იძახებს თითო ნახევარზე და უკან დაბრუნებისას აერთიანებს.3სტეკი (LIFO) და გამოსახულების გამოთვლაგამოძახებათა სტეკი სტეკია: რეკურსია შენიღბული LIFO-ა.4ქვესიმრავლეებისა და გადანაცვლებების გენერაციაქვესიმრავლეების გენერაცია ორად განშტოებადი რეკურსიაა: ავიღოთ ელემენტი თუ გამოვტოვოთ.5ხეები: ცნებები, თვისებები, შემოვლებიხის ყოველი შემოვლა ერთი და იგივე ფუნქციაა, რეკურსიულად გამოძახებული ყოველ შვილზე.6სიღრმეში ძებნა (DFS)რეკურსიულ DFS-ში უკან დასაბრუნებელ გზას გამოძახებათა სტეკი იმახსოვრებს.9უსგ და ერატოსთენეს საცერიუსგ(a, b) = უსგ(b, a mod b) ერთხაზიანი რეკურსიაა.9სწრაფი ახარისხება და მოდულური არითმეტიკაaⁿ = (a^(n/2))² რეკურსიაა, რომელიც ყოველ გამოძახებაზე n-ს ანახევრებს.10დპ-ის საფუძვლები: მემოიზაცია და ცხრილიმემოიზაცია რეკურსიული ფუნქციაა, რომელიც თავის პასუხებს იწერს.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01იგივე ამოცანის პატარა ასლი

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

საბაზისო შემთხვევა: იმდენად პატარა შემავალი მონაცემები, რომ პასუხი პირდაპირ ცნობილია. fact(1) = 1.
რეკურსიული შემთხვევა: ამოცანას ვამცირებთ და ვაერთიანებთ. fact(n) = n × fact(n−1).

წარმოიდგინე ჩადგმული ყუთები: fact(4) შეიცავს fact(3)-ის გამოძახებას, ის fact(2)-ს და ასე fact(1)-მდე, რომელიც მაშინვე პასუხობს. შემდეგ პასუხები გარეთ ბრუნდება: 1, 2, 6, 24.

ხრიკი ისაა, რომ ენდო პატარა გამოძახებას. როცა წერ n × fact(n−1)-ს, ჩათვალე, რომ fact(n−1) უკვე მუშაობს, და იკითხე მხოლოდ: ჩემი ბიჯი მის პასუხს ჩემს პასუხად აქცევს?

02რას აკეთებს სინამდვილეში კომპიუტერი: გამოძახებათა სტეკი

ყოველი გამოძახება საკუთარ ჩარჩოს იღებს: n-ის საკუთარ ასლს და ჩანაწერს, საიდან გააგრძელოს. ჩარჩოები გამოძახებათა სტეკზე ცხოვრობს.

გამოძახება ზემოთ ახალ ჩარჩოს დებს (push). გამომძახებელი ჩერდება და ელოდება.
დაბრუნება ზედა ჩარჩოს იღებს (pop) და მის მნიშვნელობას ქვედა ჩარჩოს გადასცემს, რომელიც მუშაობას აგრძელებს.

fact(4)-ის გამოთვლისას სტეკი ოთხ ჩარჩომდე იზრდება. მუშაობს მხოლოდ ზედა, დანარჩენები პასუხს ელოდებიან. მერე სტეკი ისევ მცირდება, თითო დაბრუნებით.

ეს ნამდვილი სტეკია, „ბოლოს მოვიდა, პირველი წავიდა“. ამიტომაა რეკურსია და ცხადი სტეკი ურთიერთჩანაცვლებადი: ნებისმიერი რეკურსიული ფუნქცია შეიძლება ციკლითა და სტეკით გადაიწეროს, და DFS სწორედ ესაა.

03ღირებულება: სიღრმე და რეკურსიის ხე

რეკურსიულ ფუნქციას ორი რიცხვი აღწერს:

სიღრმე: რამდენად მაღლდება სტეკი. fact(n)-ის სიღრმე n-ია, ამიტომ ის O(n) მეხსიერებას იყენებს.
გამოძახებების რაოდენობა: ყოველი გამოძახება დახატე რეკურსიის ხის წვეროდ. დრო ყველა წვეროს სამუშაოს ჯამია.

fact ყოველ დონეზე ერთ გამოძახებას აკეთებს, ამიტომ ხე ჯაჭვია: O(n) დრო. მაგრამ fib(n) = fib(n−1) + fib(n−2) ორ გამოძახებას აკეთებს და მისი ხე ფეთქდება. fib(5) უკვე fib(3)-ს ორჯერ ითვლის, fib(2)-ს კი სამჯერ; fib(n) დაახლოებით O(2ⁿ) დროს მოითხოვს.

გამოსავალი: დაიმახსოვრე უკვე გამოთვლილი პასუხები (მემოიზაცია). სწორედ ეს იდეაა დინამიური პროგრამირების კარი.

ვარდისფერი და იისფერი წვეროები განმეორებადი ქვეამოცანებია.

04ხაფანგები და როდის გამოვიყენოთ

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

ხშირი შეცდომები:

საბაზისო შემთხვევა აკლია ან მიუღწეველია: გამოძახებები არ ჩერდება და პროგრამა სტეკის გადავსებით (stack overflow) ვარდება.
ამოცანა არ მცირდება: f(n) ისევ f(n)-ს იძახებს და უსასრულოდ ტრიალებს.
ზედმეტად ღრმა: სტეკი შეზღუდულია (ხშირად რამდენიმე MB; Python ნაგულისხმევად 1000-ზე ჩერდება). 10⁶ გამოძახების ჯაჭვმა შეიძლება პროგრამა ჩამოაგდოს, ლოგიკა სწორიც რომ იყოს. გადაწერე ციკლად ან ცხადი სტეკით.
განმეორებითი სამუშაო: fib-ის მსგავს გადაფარულ გამოძახებებს მემოიზაცია სჭირდება.

ფასი ერთი შეხედვით

fact(n) დროO(n)

fact(n) სტეკის სიღრმეO(n)

გულუბრყვილო fib(n)O(2ⁿ)

fib(n) მემოიზაციითO(n)

დაიმახსოვრე

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

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე, როგორ იზრდება სტეკი ჩასვლისას და მცირდება ამოსვლისას; ყოველი დაბრუნება თავის მნიშვნელობას ქვედა ჩარჩოს გადასცემს.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

გამოძახებათა სტეკი: factorial(5)

fact(5)

დაბრუნებული მნიშვნელობები

რეკურსია: ფუნქცია, რომელიც საკუთარ თავს ეძახის უფრო მცირე შემავალ მონაცემებზე. ვიანგარიშებთ factorial(5)-ს. ყოველი გამოძახება საკუთარ ჩარჩოს იღებს გამოძახებათა სტეკზე.

ფსევდოკოდი

 1 fact(n): 2   if n <= 1: return 1     // base case 3   else: 4     return n * fact(n-1)  // recursive call

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

fact(5)-ის გამოთვლისას, ყველაზე ღრმა მომენტში fact-ის რამდენი ჩარჩოა სტეკზე?

№2

რა მოხდება n = 3-ით გამოძახებისას? f(n): if n == 0: return 0; return f(n − 2) + 1

№3

რატომაა მარტივი რეკურსიული fib(n) ასეთი ნელი?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeFibonacci Number დამწყები↗LeetCodePow(x, n) საშუალო↗CSESTower of Hanoi საშუალო↗CSESCreating Strings საშუალო↗CSESApple Division საშუალო↗