[მუსიკის დაკვრა] 

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

თქვენ კომპილირება. თქვენ აწარმოებს პროგრამა. თქვენ კარგი წასვლა. 

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

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

მე მოგცემთ მაგალითს ამ ვხედავთ, თუ როგორ რეკურსიული პროცედურა შეიძლება განისაზღვროს. ასე რომ, თუ თქვენ იცნობს ამ მათემატიკის კლასის მრავალი წლის წინ, იქ რაღაც მოუწოდა factorial ფუნქცია, რომელიც, როგორც წესი, აღინიშნება როგორც ძახილის წერტილი, რომელიც განისაზღვრება მთელ დადებითი რიცხვებით. და ისე, რომ n ფაქტორიალი არის გათვლილი არის გამრავლების ყველა ნომრები ნაკლები ან ტოლია N together-- ყველა რიცხვებით ნაკლები ან ტოლია n ერთად. 

ასე რომ, 5-ის ფაქტორიალი არის 5 ჯერ 4 ჯერ 3 ჯერ 2 ჯერ 1. და 4-ის ფაქტორიალი არის 4 ჯერ 3 ჯერ 2 ჯერ 1 და ასე შემდეგ. თქვენ იდეა. 

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

ასე რომ, აქ არის რამდენიმე facts-- pun განკუთვნილი შესახებ factorial-- factorial ფუნქცია. ფაქტორიალი 1, როგორც ვთქვი, არის 1. ფაქტორიალი 2 2-ჯერ 1. Factorial 3 3 ჯერ 2 ჯერ 1, და ასე შემდეგ. ჩვენ ვისაუბრეთ 4 და 5 უკვე. 

მაგრამ თუ ჩვენ შევხედავთ ამ, არ არის ეს? არ არის factorial 2 მხოლოდ 2 ჯერ factorial 1? მე ვგულისხმობ, რომ ის ფაქტორიალი 1 1. ასე რომ, რატომ არ შეიძლება ჩვენ უბრალოდ ვთქვა, რომ, მას შემდეგ, რაც ის ფაქტორიალი 2 2-ჯერ 1, ეს მართლაც მხოლოდ 2-ჯერ ფაქტორიალი 1? 

და მაშინ გაგრძელების, რომ იდეა, არ არის factorial 3 მხოლოდ 3 ჯერ factorial 2? და ის ფაქტორიალი 4 4-ჯერ factorial 3, და ასე შემდეგ? ფაქტობრივად, ის ფაქტორიალი ნებისმიერი რაოდენობის შეუძლია მხოლოდ იყოს გამოხატული თუ ჩვენ სახის საქართველოს განახორციელოს ამ out სამუდამოდ. ჩვენ შეგვიძლია სახის განზოგადება ფაქტორიალი პრობლემა როგორც ეს n ჯერ factorial of n მინუს 1. ეს ო ჯერ პროდუქტი ყველა ნომრები ნაკლები, ვიდრე მე. 

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

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

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

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

ეს არ მოვუწოდებთ თავად ზუსტად ანალოგიურად, ეს ეწოდა. ეს იქნება მცირე ვარიაციით , რაც პრობლემა ის ცდილობს გადაწყვიტოს teeny ცოტა პატარა. მაგრამ ეს ზოგადად გადის მამალი გადაჭრის ნაყარი გადაწყვეტა სხვადასხვა დარეკეთ ქვემოთ ხაზი. 

ჩამოთვლილთაგან რომელი გამოიყურება როგორც ბაზის შემთხვევაში აქ? რომელი ერთი ამ ჰგავს მარტივი გამოსავალი პრობლემა? ჩვენ გვყავს bunch of factorials, და ჩვენ ვერ გაგრძელდება აპირებს on-- 6, 7, 8, 9, 10, და ასე შემდეგ. 

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

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

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

Factorial of 1 1. ეს არ არის 1 ჯერ არაფერი. ეს არის მხოლოდ 1. ეს არის ძალიან მარტივი ფაქტი. და ისე, რომ შეიძლება ჩვენი ბაზის შემთხვევაში. თუ ჩვენ გავიდა 1 ამ ფუნქცია, ჩვენ უბრალოდ დააბრუნოს 1. 

რა არის რეკურსიული იმ შემთხვევაში, ალბათ გამოიყურებოდეს? ყოველი მეორე ნომერი გარდა ამისა, 1, რა არის ნიმუში? ისე, თუ ჩვენ ვიღებთ factorial of n, ეს n ჯერ factorial of n მინუს 1. 

თუ ჩვენ აღების factorial 3, ეს 3-ჯერ factorial 3 მინუს 1, ან 2. ასე რომ, თუ ჩვენ არ ვართ ეძებს 1, წინააღმდეგ შემთხვევაში, დაბრუნების n ჯერ factorial of n მინუს 1. ეს საკმაოდ მარტივია. 

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

მე უბრალოდ წაიღეს curly braces, იმიტომ, რომ იქ მხოლოდ ერთი ხაზი შიგნით იმ პირობით ფილიალში. ასე რომ, ეს მოიქცეს იდენტურად. თუ n უდრის 1, დაბრუნდნენ 1. წინააღმდეგ შემთხვევაში დაბრუნდება n ჯერ factorial of n მინუს 1. ასე რომ, ჩვენ მიღების პრობლემა პატარა. თუ n იწყება, როგორც 5, ჩვენ ვაპირებთ დაბრუნდეს 5 ჯერ factorial 4. და ვნახავთ, ერთი წუთით, როდესაც ვსაუბრობთ ზარის შესახებ დასტის სხვა ვიდეო სადაც ჩვენ ვსაუბრობთ მოვუწოდებთ დასტის ჩვენ ვისწავლოთ შესახებ, თუ რატომ სწორედ ეს პროცესი მუშაობს. 

მაგრამ მაშინ, როცა ის ფაქტორიალი 5 ამბობს დაბრუნდეს 5 ჯერ factorial 4, 4 თქმას, OK, ისევე, დაბრუნების 4-ჯერ factorial 3. და როგორც ხედავთ, ჩვენ ერთგვარი ახლოვდება 1. ჩვენ უფრო და უფრო ახლოს რომ ბაზის შემთხვევაში. 

და კიდევ ჩვენ მოხვდა ბაზის შემთხვევაში, ყველა წინა ფუნქციები აქვს პასუხი ეძებდნენ. Factorial 2 ამბობდა დაბრუნების 2 ჯერ factorial 1. ისე, ის ფაქტორიალი 1 ბრუნდება 1. ასე რომ, მოწოდება ფაქტორიალი 2 შეიძლება დაბრუნდეს 2 ჯერ 1, და მისცეს, რომ უკან factorial of 3, რომელიც ელოდება, რომ შედეგი. 

და მაშინ შეიძლება გამოვთვალოთ მისი შედეგი, 3-ჯერ 2: 6, და მისცეს მას უკან ფაქტორიალი 4. ისევ და ისევ, ჩვენ გვაქვს ვიდეო სტეკი სადაც ეს ილუსტრირებულია პატარა მეტი, ვიდრე მე ვამბობ ახლავე. მაგრამ ეს არის ის. მარტო ეს არის გამოსავალი გაანგარიშების factorial რიგი. 

ეს არის მხოლოდ ოთხი ხაზი კოდი. ეს არის საკმაოდ მაგარი, არა? ეს არის სახის სექსუალური. 

ზოგადად, მაგრამ არა ყოველთვის, რეკურსიული ფუნქცია შეიძლება შეცვალოს loop in a არასამთავრობო რეკურსიული ფუნქცია. ასე რომ, აქ, გვერდით, არის ტიპიური მობილური factorial ფუნქცია. ორივე ეს გამოთვლა ზუსტად იგივე. 

ორივე გამოთვლა factorial n. ვერსია მარცხენა იყენებს უკან, რომ ამის გაკეთება. ვერსია მარჯვენა იყენებს iteration ამის გაკეთება. 

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

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

თქვენ შეიძლება გავიხსენოთ დაწყებითი სკოლის დღის რომ Fibonacci თანმიმდევრობა განისაზღვრება მოსწონს ეს პირველი ელემენტი 0. მეორე ელემენტი არის 1. ორივე ეს არის მხოლოდ განმარტება. 

მაშინ ყველა სხვა ელემენტს განისაზღვრება როგორც თანხა n მინუს 1 და N -2. ასე რომ, მესამე ელემენტს იქნება 0 + 1 1. და მაშინ მეოთხე ელემენტს იქნება მეორე ელემენტს, 1, პლუს მესამე ელემენტს, 1. და ეს იქნება 2. და ასე შემდეგ და ასე შემდეგ. 

ასე რომ, ამ შემთხვევაში, ჩვენ გვაქვს ორი ბაზა შემთხვევაში. თუ n უდრის 1, დაბრუნდნენ 0. თუ n უდრის 2, დაბრუნდნენ 1. წინააღმდეგ შემთხვევაში, დაბრუნების Fibonacci ო მინუს 1 plus Fibonacci of n მინუს 2. 

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

ასე რომ, აქ არის ის, რაც Collatz ვარაუდი is-- ეს ეხება ყველა დადებითი მთელი რიცხვი. და ეს ვარაუდობს, რომ ეს ყოველთვის შესაძლებელია დავუბრუნდეთ 1 თუ მიჰყვეთ ამ ნაბიჯებს. თუ n 1, შეწყვიტოს. ჩვენ მივიღეთ უკან 1, თუ n 1. 

წინააღმდეგ შემთხვევაში, გაიაროს ეს პროცესი კვლავ ო იყოფა 2. და თუ შეგიძლიათ მიიღოთ უკან 1. წინააღმდეგ შემთხვევაში, თუ n არის უცნაური, გავლა ეს პროცესი კვლავ 3N პლუს 1, ან 3 ჯერ n + 1. ასე რომ აქ გვაქვს ერთი ბაზის შემთხვევაში. თუ n უდრის 1, შეწყვიტოს. ჩვენ არ აკეთებს რაიმე უფრო უკან. 

მაგრამ ჩვენ გვაქვს ორი რეკურსიული შემთხვევაში. თუ n კი, ჩვენ ერთი რეკურსიული იმ შემთხვევაში, მოუწოდებს ო იყოფა 2. თუ n უცნაური, ჩვენ სხვადასხვა რეკურსიული შემთხვევაში 3-ჯერ n + 1. 

ასე რომ, მიზანი ეს ვიდეო მიიღოს მეორე, პაუზის ვიდეო, და ცდილობენ და დაწეროთ ამ რეკურსიული ფუნქცია Collatz სადაც თქვენ გაივლის მნიშვნელობა ო, ითვლის რამდენი ნაბიჯი, იღებს, რათა 1 თუ დაიწყება n და თქვენ დაიცვას იმ ნაბიჯებს, ზემოთ. თუ n 1, სჭირდება 0 ნაბიჯები. წინააღმდეგ შემთხვევაში, ის აპირებს ერთი ნაბიჯით პლუს თუმცა ბევრი ნაბიჯები სჭირდება არც n გაყოფილი 2 თუ n კი, ან 3N პლუს 1 თუ n უცნაური. 

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

თუ N 2, სჭირდება ერთი ნაბიჯი, რათა 1. თქვენ იწყება 2. ისე, 2 არ უდრის 1. ასე რომ, ეს იქნება ერთ-ერთი ნაბიჯი პლუს, თუმცა ბევრი ის ნაბიჯი, იღებს ო იყოფა 2. 

2 იყოფა 2 1. ასე რომ, იგი იღებს ერთი ნაბიჯი პლუს თუმცა ბევრი ნაბიჯები სჭირდება 1. 1 იღებს ნულოვანი ნაბიჯები. 

3, როგორც ხედავთ, არსებობს საკმაოდ ნაბიჯები ჩართული. მიდიხარ 3. და მაშინ წასვლა 10, 5, 16, 8, 4, 2, 1. იგი იღებს შვიდი ნაბიჯები დავუბრუნდეთ 1. და როგორც ხედავთ, არსებობს რამდენიმე სხვა ტესტის აქ შეამოწმოთ თქვენი პროგრამა. ასე რომ კიდევ ერთხელ, პაუზის ვიდეო. მე კი წასვლა ხტომა უკან ახლა რა ფაქტობრივი პროცესი აქ, ის, რაც ამ ვარაუდი არის. 

აგრეთვე, თუ შეგიძლიათ გაერკვნენ როგორ უნდა განისაზღვროს Collatz ო ისე, რომ იგი ითვლის რამდენი ნაბიჯები სჭირდება მიიღოთ 1. ასე რომ, იმედია, თქვენ არ ათვისება ვიდეო და თქვენ არა მხოლოდ მელოდება გადმოგცეთ პასუხი აქ. მაგრამ თუ თქვენ, ისევე, აქ არის პასუხი მაინც. 

ასე რომ აქ შესაძლებელია განმარტება საქართველოს Collatz ფუნქცია. ჩვენი ბაზის case-- თუ n 1-ის ტოლი, დაბრუნდნენ 0. ეს არ მიიღოს ნებისმიერი ნაბიჯები, რათა დავუბრუნდეთ 1. 

წინააღმდეგ შემთხვევაში, ჩვენ გვაქვს ორი რეკურსიული cases-- ერთი კი ნომრები და ერთი უცნაური. გზა მე შესამოწმებლად კი ნომრები შეამოწმეთ n mod 2 უდრის 0. ეს არის ძირითადად, კიდევ ერთხელ, სვამს კითხვას, თუ გავიხსენებთ, რა mod is-- თუ მე გათიშე n 2 აღარც დარჩენილი? ეს იქნება კიდევ ნომერი. 

ასე რომ, თუ n mod 2 უდრის 0 არის ტესტირება ამ კი რაოდენობის. თუ ეს ასეა, მინდა დაბრუნდეს 1, იმიტომ, რომ ეს არის ნამდვილად ერთი ნაბიჯის გადადგმით, პლუს Collatz of რასაც ნახევარს ჩემთვის. წინააღმდეგ შემთხვევაში, მე მინდა დაბრუნდეს 1 პლუს Collatz 3 ჯერ n + 1. ეს იყო სხვა რეკურსიული ნაბიჯი, რომელიც ჩვენ შეიძლება მიიღოს გამოთვლა Collatz-- რაოდენობის ნაბიჯები იგი იღებს, რათა დავუბრუნდეთ 1 გეძლევათ ნომერი. ასე რომ, იმედია, ეს მაგალითი მისცა თქვენ ცოტა საქართველოს გემოვნების რეკურსიული პროცედურები. იმედია, თქვენ ფიქრობთ, კოდი არის უფრო ლამაზი თუ ხორციელდება ელეგანტური, რეკურსიული გზა. მაგრამ მაშინაც კი, თუ არა, უკან არის მართლაც ძლიერი ინსტრუმენტი მაინც. ასე რომ, ეს ნამდვილად რაღაც მისაღებად თქვენი უფროსი გარშემო, იმიტომ, რომ თქვენ შეძლებთ შექმნათ საკმაოდ გრილი პროგრამების გამოყენებით უკან რომელიც შეიძლება სხვაგვარად იყოს რთული დაწერა თუ თქვენ იყენებთ მარყუჟების და მცდელობაა. მე Doug Lloyd. ეს არის CS50.