>> Zamyla: იმისათვის, რომ გავიგოთ უკან, თქვენ უნდა
გვესმოდეს უკან.
რა უკან პროგრამების შემუშავების საშუალებით რომ თქვენ გაქვთ თვითმმართველობის რეფერენტული
განმარტებები.
რეკურსიული მონაცემთა სტრუქტურები, მაგალითად, მონაცემები სტრუქტურები,
მოიცავს თავი მათი განმარტებები.
მაგრამ დღეს, ჩვენ ვაპირებთ ფოკუსირება on რეკურსიული ფუნქციები.
>> შეგახსენებთ, რომ ფუნქციები მიიღოს საშუალებებით, არგუმენტები, და დაბრუნდება მნიშვნელობა, როგორც მათი
გამომავალი წარმოდგენილია ამ დიაგრამაზე აქ.
ჩვენ ვფიქრობთ, ყუთში, როგორც ორგანოს ფუნქცია, რომელიც შეიცავს კომპლექტი
ინსტრუქციას, რომ ინტერპრეტაცია შემავალი და უზრუნველყოს გამომუშავება.
იმის ახლოს შიგნით ორგანოს ფუნქცია შეიძლება გამოავლინოს ზარები
სხვა ფუნქციები ისევე.
მიიღეთ ეს მარტივი ფუნქცია, foo, რომ იღებს ერთი string როგორც შეყვანის და
ნამუშევარი რამდენი ასო რომ სიმებიანი აქვს.
ფუნქცია strlen, სიმებიანი სიგრძე, ეწოდება, რომლის გამომავალი არის
საჭირო ზარი printf.
>> ახლა, რაც რეკურსიული ფუნქცია განსაკუთრებული ის არის, რომ ის მოუწოდებს თავად.
ჩვენ შეგვიძლია წარმოადგენს ამ რეკურსიული დარეკეთ ამ ფორთოხლის arrow
looping უკან თავად.
მაგრამ შესრულებაში თავად ერთხელ მხოლოდ კიდევ ერთი რეკურსიული ზარი და
სხვა და სხვა.
მაგრამ რეკურსიული ფუნქციების არ შეიძლება იყოს უსასრულო.
ისინი უნდა დამთავრდეს რატომღაც, ან თქვენი პროგრამა აწარმოებს სამუდამოდ.
>> ამიტომ, ჩვენ უნდა მოვძებნოთ გზა შესვენება გარეთ რეკურსიული მოუწოდებს.
ჩვენ მოვუწოდებთ ამ ბაზის შემთხვევაში.
როდესაც ბაზის შემთხვევაში მდგომარეობა დაკმაყოფილებულია, ფუნქცია დააბრუნებს გარეშე
სხვა რეკურსიული ზარი.
ამ ფუნქციას, hi, ბათილად ფუნქცია რომ იღებს int n, როგორც შეყვანის.
ბაზის შემთხვევაში მოდის პირველი.
თუ n ნაკლებია, ვიდრე ნულოვანი, ბეჭდვითი bye და დაბრუნდეს ყველა სხვა შემთხვევაში,
ფუნქცია ბეჭდვა hi და შეასრულოს რეკურსიული ზარი.
სხვა ზარი ფუნქცია hi ერთად decremented შეყვანის ღირებულება.
>> ახლა, მიუხედავად იმისა, რომ ჩვენ ბეჭდვა hi, ფუნქცია არ შეწყვიტოს სანამ ჩვენ
დაიბრუნებს დაბრუნების ტიპის, ამ შემთხვევაში ბათილად.
ასე რომ, ყოველ n გარდა ბაზის შემთხვევაში, ამ ფუნქციის hi დაბრუნდება hi
of n მინუს 1.
მას შემდეგ, რაც ამ ფუნქციის ბათილად თუმცა, ჩვენ არ პირდაპირ აკრიფოთ დაბრუნების აქ.
ჩვენ უბრალოდ შეასრულოს ფუნქცია.
ასე მოუწოდებდა hi (3) ბეჭდვა hi და შეასრულოს hi (2), რომელიც ახორციელებს hi (1) ერთი
რომელიც ახორციელებს hi (0), სადაც ბაზის შემთხვევაში მდგომარეობა დაკმაყოფილებულია.
ასე რომ, hi (0) ბეჭდავს bye და ანაზღაურება.
>> OK.
ახლა რომ ჩვენ გვესმის საფუძვლებს რეკურსიული ფუნქცია, რომ მათ სჭირდებათ
მინიმუმ ერთი ბაზის შემთხვევაში, ისევე როგორც რეკურსიული ზარი, მოდით გადაადგილება
უფრო მნიშვნელოვანი მაგალითი.
ერთი, რომ არ დააბრუნებს ბათილად არ აქვს მნიშვნელობა რა.
>> მოდით შევხედოთ factorial ოპერაცია გამოიყენება ყველაზე ხშირად
ალბათობა გათვლები.
Factorial of n არის პროდუქტი ყველა დადებითი მთელი რიცხვი ნაკლები
და ტოლია n.
ასე რომ factorial ხუთ არის 5 ჯერ 4 ჯერ 3 ჯერ 2 ჯერ 1 მისცეს 120.
ოთხი factorial არის 4 ჯერ 3 ჯერ 2 ჯერ 1 რათა 24.
და იგივე წესი ვრცელდება ნებისმიერი დადებითი მთელი რიცხვი.
>> ასე როგორ შეიძლება ჩვენ წერენ რეკურსიული ფუნქცია, რომელიც ითვლის factorial
რიგი?
ასევე, ჩვენ უნდა გამოავლინოს ორივე ბაზის შემთხვევაში და რეკურსიული ზარი.
რეკურსიული ზარი იქნება იგივე ყველა შემთხვევაში, გარდა ბაზაზე
შემთხვევაში, რაც ნიშნავს, რომ ჩვენ გვექნება იპოვოს ნიმუში, რომელიც საშუალებას მოგვცემს ჩვენი
სასურველი შედეგი.
>> ამ მაგალითად, ვხედავ, როგორ 5 factorial მოიცავს გამრავლებით 4 3 2 1
და რომ იმავე გამრავლება გამოჩენას აქ,
განმარტება 4 factorial.
ასე რომ, ჩვენ ვხედავთ, რომ 5 factorial არის მხოლოდ 5 ჯერ 4 factorial.
ახლა ჯერ ეს ნიმუში ვრცელდება 4 factorial ისევე?
დიახ.
ჩვენ ვხედავთ, რომ 4 factorial შეიცავს გამრავლება 3 ჯერ 2 ჯერ 1,
იმავე განმარტება 3 factorial.
ასე რომ 4 factorial უდრის 4 ჯერ 3 factorial, და ა.შ. და ა.შ. ჩვენი
ნიმუში ჩხირები წლის 1 factorial, რომელიც ზოგადად უდრის 1.
>> არ არსებობს სხვა დადებითი რიცხვებით დატოვა.
ასე რომ ჩვენ გვაქვს ნიმუში ჩვენი რეკურსიული ზარი.
n factorial უდრის n times factorial of n მინუს 1.
და ჩვენი ბაზის შემთხვევაში?
ეს უბრალოდ ჩვენი განმარტება 1 factorial.
>> ასე რომ, ახლა ჩვენ შეგვიძლია გადაადგილება წერა კოდი ფუნქცია.
ბაზის შემთხვევაში, ჩვენ გვექნება მდგომარეობა n შეადგენს შეადგენს 1, სადაც
ჩვენ დაბრუნებას 1.
შემდეგ მოძრავი გადატანა რეკურსიული ზარი, ჩვენ დაბრუნდება n ჯერ
factorial of n მინუს 1.
>> ახლა მოდით შეამოწმოთ ეს ჩვენი.
მოდით ცდილობენ factorial 4.
პერ ჩვენი ფუნქცია ის ტოლია 4 ჯერ factorial (3).
Factorial (3) უდრის 3 ჯერ factorial (2).
Factorial (2) უდრის 2 ჯერ factorial (1), რომელიც დააბრუნებს 1.
Factorial (2) ახლა ბრუნდება 2 ჯერ 1, 2.
Factorial (3) ახლა დაბრუნდნენ 3 ჯერ 2, 6.
და ბოლოს, factorial (4) ბრუნდება 4 ჯერ, 6, 24.
>> თუ თქვენ encountering ნებისმიერი სირთულის ერთად რეკურსიული ზარი, ვიტყვი, რომ
ფუნქცია მუშაობს უკვე.
რას ნიშნავს ეს, რომ თქვენ უნდა ენდობა თქვენი რეკურსიული ზარი დაბრუნებას
მარჯვენა ღირებულებებს.
მაგალითად, თუ მე ვიცი, რომ factorial (5) შეადგენს 5 ჯერ
factorial (4), მე ვაპირებ, რომ მჯერა, რომ factorial (4) მომცემს 24.
ვფიქრობ, რომ ეს ცვლადი, თუ იქნება, რადგან თუ თქვენ უკვე განსაზღვრულია
factorial (4).
ასე რომ, ნებისმიერი factorial (n), ეს პროდუქტი n და
წინა factorial.
და ეს წინა factorial მიღებული მოუწოდებს
factorial of n მინუს 1.
>> ახლა, თუ შეგიძლიათ განახორციელოს რეკურსიული ფუნქცია თავს.
ჩატვირთვა თქვენი ტერმინალში, ან run.cs50.net, და ჩაწერის ფუნქცია თანხა
რომ იღებს რიცხვი n და დააბრუნებს თანხა ყველა ზედიზედ დადებითი
რიცხვებით ეხლა n 1.
მე გაწერილი თანხები ზოგიერთი ღირებულებები დაგეხმაროთ ჩვენი.
პირველი, გაერკვნენ ბაზის შემთხვევაში მდგომარეობაშია.
მაშინ, შევხედოთ თანხა (5).
შეგიძლიათ გამოხატოს ის ტერმინები სხვა თანხა?
ახლა, რაც შეეხება თანხა (4)?
როგორ შეგიძლიათ გამოხატოს თანხა (4) თვალსაზრისით კიდევ თანხა?
>> მას შემდეგ, რაც თქვენ გაქვთ თანხა (5) და თანხა (4) თავის მხრივ, სხვა თანხები, ვხედავ
თუ შეგიძლიათ იდენტიფიცირება ნიმუში თანხა (n).
თუ არა, ცდილობენ რამდენიმე სხვა ნომრები და გამოხატონ თავიანთი თანხები
თვალსაზრისით მეორე ნომრები.
განსაზღვრავს თარგების დისკრეტული ციფრები, თქვენ კარგად თქვენს გზა
საიდენტიფიკაციო ნიმუში ნებისმიერი n.
>> უკან მართლაც ძლიერი ინსტრუმენტი, ასე რომ, რა თქმა უნდა, ის არ შემოიფარგლება
მათემატიკური ფუნქციები.
უკან შეიძლება გამოყენებულ იქნას ეფექტურად როდესაც საქმე ხეები მაგალითად.
შეამოწმეთ მოკლე ხეები უფრო საფუძვლიანი მიმოხილვა, მაგრამ ახლა
გავიხსენოთ, რომ ორობითი ძებნა ხეები, კერძოდ, შედგება კვანძების, თითოეული
ერთად ღირებულება და ორი კვანძის პოინტერები.
როგორც წესი, ეს წარმოდგენილია მშობელი კვანძი, რომელსაც ერთი ხაზი მიუთითებს
მარცხენა კვანძზე და ერთი მარჯვნივ კვანძზე.
სტრუქტურა ორობითი ძებნა ხე lends თავად კარგად
to რეკურსიული ძებნა.
რეკურსიული ზარი ან გადის მარცხენა ან მარჯვენა კვანძის, მაგრამ უფრო
რომ ხე მოკლე.
>> ამბობენ, რომ გსურთ შეასრულოს ოპერაცია თითოეული კვანძის ორობითი ხე.
როგორ შეიძლება წავიდეთ შესახებ ეს?
ასევე, შეგიძლიათ დაწეროთ რეკურსიული ფუნქცია, რომელიც ასრულებს ოპერაცია
მშობლის კვანძის და რაც რეკურსიული მოვუწოდებთ იგივე ფუნქცია,
გადადის და მარცხენა უფლება ბავშვის კვანძების.
მაგალითად, ამ ფუნქციას, foo, რომ ცვლის ღირებულება მოცემული კვანძის და
ყველა მისი შვილები 1.
ბაზის შემთხვევაში null კვანძის მიზეზები ფუნქციის დაბრუნებას, რაც მიუთითებს,
რომ არ არსებობს კვანძების დარჩა, რომ sub-ხე.
>> მოდით გავლა იგი.
პირველი მშობელი არის 13.
შევცვლით ღირებულება 1, და შემდეგ მოვუწოდებთ ჩვენი ფუნქცია მარცხენა ისევე
როგორც უფლება.
ფუნქცია, foo, ეწოდება მარცხენა sub-tree პირველი, ისე მარცხენა კვანძის
იქნება გადაიყვანა 1 და foo იქნება ეწოდოს, რომ კვანძის ბავშვებს,
პირველი მარცხენა და მერე მარჯვენა, და ასე შემდეგ და ასე შემდეგ.
და ვუთხრა, რომ ტოტები არ აქვს რაიმე უფრო ბავშვებს, რათა იგივე პროცესი
გაგრძელდება უფლება ბავშვები სანამ მთელი ხე კვანძების
გადაიყვანა 1.
>> როგორც ხედავთ, თქვენ არ შემოიფარგლება მხოლოდ ერთი რეკურსიული ზარი.
ისევე, როგორც ბევრი როგორც იქნება მისაღებად გაწეული სამუშაო.
რა თუ ჰქონდა ხე, სადაც თითოეული კვანძის სამი შვილი,
მარცხენა, შუა და მარჯვენა?
რა შეცვალონ foo?
ისე, მარტივია.
უბრალოდ დაამატოთ კიდევ ერთი რეკურსიული ზარი და გაივლის შუა კვანძის მაჩვენებელი.
>> უკან არის ძალიან ძლიერი და არა ვთქვათ ელეგანტური, მაგრამ ეს შეიძლება იყოს
რთული კონცეფცია, პირველ რიგში, ასე რომ პაციენტის და მიიღოს თქვენი დრო.
დაწყება ბაზის შემთხვევაში.
ეს, როგორც წესი მარტივი იდენტიფიცირება, და მაშინ მუშაობა
უკან იქიდან.
თქვენ იცით, თქვენ უნდა მივაღწიოთ თქვენი ბაზის შემთხვევაში, ასე რომ, შესაძლოა,
მოგცემთ რამდენიმე მინიშნებები.
სცადეთ გამოხატოს ერთ კონკრეტულ შემთხვევაში, თვალსაზრისით სხვა შემთხვევებში, ან საქვეუწყებო კომპლექტი.
>> მადლობა თვალს ამ მოკლე.
სულ ცოტა, ახლა თქვენ შეგიძლიათ მესმის ხუმრობები მოსწონს ეს.
ჩემი სახელი არის Zamyla, და ეს არის CS50.
>> ამ ფუნქციას, hi, ბათილად ფუნქცია, რომელიც იღებს
int, N, როგორც შეყვანის.
ბაზის შემთხვევაში მოდის პირველი.
თუ n ნაკლებია, ვიდრე 0, ბეჭდვითი "Bye" და სანაცვლოდ.