[Музички] 

Даг LLOYD: Веројатно сметате дека код е само користи за да се постигне задача. Ти го пишувам надвор. Тоа го прави нешто. Тоа е доста тоа многу. 

Можете да го компајлирате. Ќе ја стартувате програмата. Вие ќе бидете добро да отидевме. 

Но, верувале или не, ако можете код за долго време, вие всушност може да дојде за да ја видите код како на нешто што е убаво. Тоа го решава проблемот во многу интересен начин, или таму е само нешто што навистина уредни за начинот на кој таа изгледа. Може да се смее во мене, но тоа е вистина. И рекурзијата е еден начин за да се добие овој вид на идеја на убава, елегантна изглед код. Што решава проблемите на начин на кој се интересни, лесно да се визуелизира, и изненадувачки кратко. 

Работи на начинот на рекурзија е, рекурзивен функција се дефинира како функција која повикува себе како дел од неговото извршување. Тоа може да изгледа малку чудно, и ќе видиме малку за тоа како тоа функционира во еден миг. Но, повторно, овие рекурзивен процедури се ќе биде толку елегантна затоа што тие се случува да се реши овој проблем без имаат сите овие други функции или овие долги петелки. Ќе видите дека овие рекурзивни постапките се случува да изгледа толку кратко. И тие навистина се случува да се направи Вашиот код изгледа многу поубаво. 

Јас ќе ви дадам еден пример на ова се види како може да се дефинира рекурзивна постапка. Значи, ако сте запознаени со оваа од математика, пред многу години, Има нешто наречен факториел на, што е обично означува како извичник, која е дефинирана во текот на сите позитивни цели броеви. И начинот на кој што п факториел се пресметува е ќе се мултиплицираат сите броеви помалку од или еднаква на n together-- сите цели броеви помалку од или еднаква на n заедно. 

Па 5 факториел е 5 пати 4 пати 3 пати 2 пати 1. И 4 факториел е 4 пати 3 пати 2 пати 1 и така натаму. Ќе го добиете идеја. 

Како програмери, ние не користете n, извичник. Па ние ќе се дефинира факториел функција како факт на n. И ние ќе го користат за да се создаде факториел рекурзивен решение на проблемот. И мислам дека може да се најдат дека тоа е многу повеќе визуелно привлечен од повторната верзија на ова, што ние, исто така, ќе погледнеме во еден момент. 

Па еве неколку facts-- каламбур intended-- за factorial-- на факториел функција. Факториел од 1, како што реков, е 1. Факториел од 2 е 2 пати 1. Факториел од 3 е 3 Времето е 2 пати 1, и така натаму. Ние разговаравме за 4 и 5 веќе. 

Но, гледајќи во ова, не е тоа вистина? Не факториел од само 2 2 пати факториел од 1? Мислам, факториел од 1 е 1. Па зошто да не можеме да речеме дека, бидејќи факториел од 2 е 2 пати 1, тоа е навистина само 2 пати факториел од 1? 

А потоа продолжување на таа идеја, не е фактор од 3 само 3 пати факториел од 2? И факториел од 4 е 4 пати факториел од 3, и така натаму? Всушност, факториел на било кој број да се само биде искажана ако ние вид извршување на ова вечно. Ние може да се вид на генерализира факториел проблем како што тоа е n пати факториел од n 1 минус. Тоа е n пати производ на сите броеви помалку од мене. 

Оваа идеја, ова генерализација на проблемот, ни овозможува да рекурзивно дефинираат факториел функција. Кога ќе го дефинираме функција рекурзивно, има две работи кои треба да се биде дел од неа. Треба да имате нешто што се нарекува база на случајот, кој, кога ќе го активира, да запре на рекурзивен процес. 

Инаку, функција која што повикува itself-- како што може да imagine-- може да трае вечно. Функциски повици функцијата повици на функциски повици функцијата повикува функцијата. Ако не го имаат начин да го спречи тоа, вашата програма ќе биде ефикасно заглавени во бесконечна јамка. Тоа ќе несреќа на крајот, затоа што тоа ќе работи надвор од меморија. Но, тоа е до точка. 

Ние треба да имаат некој друг начин да се запре нешта, покрај нашата програма паѓа, бидејќи програмата што се урна е најверојатно не убава и елегантна. И така ние го нарекуваме овој основниот случај. Ова е едноставно решение за проблемот кој го запира рекурзивен процес од случуваат. Значи, тоа е еден дел од рекурзивен функција. 

Вториот дел е рекурзивен случај. И ова е местото каде што на рекурзија всушност, ќе се одржи. Ова е местото каде функција ќе се јавам. 

Тоа нема да се јавите во точно на ист начин како што беше наречена. Тоа ќе биде мала варијација што го прави тоа е проблем се обидува да реши еден teeny малку помали. Но тоа обично поминува префрлуваат за решавање на дел од решението на различни повик одредување на линија. 

Која од овие изглед како основен случај тука? Кој од овие изгледа како Наједноставниот решение на проблемот? Имаме еден куп на factorials, и ние би можеле да продолжат случува on-- 6, 7, 8, 9, 10, и така натаму. 

Но еден од овие личи на добар случај да биде база случај. Тоа е многу едноставно решение. Ние не треба да правите ништо посебно. 

Факториел од 1 е само 1. Ние не треба да направите било множење на сите. Ми се чини дека, ако ние се случува да се обиде да го реши овој проблем, и ние треба да се запре рекурзија некаде, ние најверојатно сакаат да престанат тоа кога ќе се добие на 1. Ние не сакаме да се запре пред тоа. 

Значи, ако ние сме дефинирање нашите факториел на, еве еден скелет за како да го направите тоа. Ние треба да го приклучиш во овие две things-- основното сценарио и рекурзивни случај. Што е основниот случај? Ако n е еднаков на 1, се врати 1-- тоа е навистина едноставен проблем да се реши. 

Факториел од 1 е 1. Тоа не е 1 пати ништо. Тоа е само 1. Тоа е многу лесно факт. И, така што може да биде наш основен случај. Ако можеме да се донесе во оваа 1 функција, ние само ќе се вратат 1. 

Што е рекурзивен случај веројатно изгледа? За секој друг број освен 1, што е шемата? Па, ако ние сме преземање факториел од n, тоа е n пати факториел од n 1 минус. 

Ако ние сме преземање факториел од 3, тоа е 3 пати факториел од 3 минус 1, или 2. И така, ако ние не сме гледа во 1, инаку враќање n пати факториел од n 1 минус. Тоа е прилично јасна. 

И за доброто на се има малку почиста и поелегантни код, знам дека ако имаме една линија јамки или еден ред условен гранки, ние може да се ослободи од сите на големи загради околу нив. За да можеме да ја консолидираме оваа на ова. Ова има иста функционалност што е оваа. 

Јас сум само одземање на кадрава протези, бидејќи има само една линија во внатрешноста на тие условен гранки. Значи овие се однесуваат идентично. Ако n е еднакво на 1, се врати 1. Инаку се вратат n пати факториел од n 1 минус. Па ние сме прави проблем помали. Ако n почнува како 5, ние ќе треба да врати 5 пати факториел од 4. И ќе видиме во една минута, кога зборуваме за stack-- повикот во друг видео кога зборуваме за јавете stack-- ние ќе научат за тоа зошто токму овој процес дела. 

Но, додека факториел од 5 вели врати 5 пати факториел од 4 и 4 се случува да се каже, Добро, добро, враќање 4 пати факториел од 3. И како што можете да видите, ние сме вид приближува 1. Ние сме добивање поблиску и поблиску до таа база случај. 

И кога ќе се удри на база случај, сите од претходната функции имаме одговорот што го барате. Факториел од 2 велеше враќање 2 пати факториел од 1. Па, факториел од 1 враќа 1. Затоа конкурсот факториел можат да се вратат од 2 1 2 пати, и му даде назад кон факториел 3, кој е на чекање за тој резултат. 

И потоа може да се пресмета нејзиниот резултат, 3 пати 2 е 6, и го даде назад кон факториел од 4. И повторно, имаме видео на магацинот на повикот каде што тоа е илустрирано малку повеќе од она што сакам да кажам дека во моментов. Но, тоа е тоа. Ова е само решение за пресметување на факториел на број. 

Тоа е само четири линии на код. Тоа е прилично кул, нели? Тоа е вид на секси. 

Па воопшто, но не секогаш, рекурзивен функција може да го замени еден циклус во не-рекурзивен функција. Па еве, рамо до рамо, е итеративен верзија на факториел на. И двете од овие се пресмета токму истото. 

Тие двете се пресмета факториел од n. Верзијата на левата користи рекурзија да го направи тоа. Верзијата на десната користи повторување да го направи тоа. 

И информации, ние мора да се декларираат променлива цел број производ. А потоа ние јамка. Толку долго како што n е поголема од 0, ние задржи множење дека производот од страна н и decrementing n до ние се пресмета производот. Па овие две функции, повторно, направите токму истото. Но, тие не го прават тоа во токму на ист начин. 

Сега, можно е да се имаат повеќе од една база случај или повеќе од еден рекурзивен случај, во зависност на она што вашите функција се обидуваат да го направат. Вие не мора да се само ограничени на една база случај или една рекурзивен случај. Така пример за нешто со повеќе база случаи би можело да биде на this-- Фибоначиевата низа број. 

Може да се сети од ОУ дена дека низата на Фибоначи е дефинирана како this-- првиот елемент е 0. На вториот елемент е 1. И на оние кои се само по дефиниција. 

Тогаш секој друг елемент е дефинирана како збир на n минус 1 и n минус 2. Па на третиот елемент ќе биде 0 плус 1 е 1. А потоа и на четвртиот елемент ќе биде вториот елемент, 1, плус на третиот елемент, 1. И дека ќе биде 2. И така натаму и така натаму. 

Значи во овој случај, имаме две база случаи. Ако n е еднаков на 1, се врати 0. Ако n е еднакво на 2, се врати 1. Во спротивно, се врати на Фибоначи на n 1 минус плус Фибоначи од n минус 2. 

Значи тоа е повеќе база случаи. Што е со повеќе рекурзивен случаи? Па, таму е нешто наречен претпоставка Collatz. Јас не одам да се каже, Знаете ли што е тоа што, затоа што тоа е всушност нашата конечна Проблемот за оваа видео. И тоа е нашата вежба да работат заедно. 

Значи тука е она што Collatz претпоставка is-- Тој важи за секој позитивен цел број. И тоа се шпекулира дека тоа е секогаш е можно да се врати назад 1, ако ги следите овие чекори. Ако n е 1, да престане. Имаме назад до 1 ако n е 1. 

Инаку, одат преку овој Процесот повторно на н поделено со 2. И да видиме дали може да се вратам на 1. Во спротивно, ако n е непарен, одат преку овој процес повторно на 3N плус 1, или 3 пати n плус 1. Значи тука имаме една база случај. Ако n е еднаков на 1, да престане. Да не правиш ништо повеќе рекурзија. 

Но, ние имаме две рекурзивен случаи. Ако n е дури, тоа го правиме еден рекурзивен случај, повикувајќи n поделено со 2. Ако n е непарен, тоа го правиме на поинаков рекурзивен случај на 3 пати n плус 1. 

И така цел за ова видео е да се земе втора, паузирање на видеото, и да се обиде и да го напишам ова рекурзивен функција Collatz каде што ќе помине во вредност n и го пресметува колку што чекори потребно да се добие на 1 ако почнете од n и да ги следат овие чекори до горе. Ако n е 1, тоа трае 0 чекори. Инаку, тоа се случува да земе еден чекор плус сепак многу чекори што е потребно на секоја n поделен со 2 ако n е дури, или 3N плус 1 ако n е непарен. 

Сега, јас сум се стави на екранот овде неколку тест работи за вас, неколку случаи тестови за вас, за да ја видите она што овие различни Collatz броеви се, а исто така и за илустрација од чекорите кои треба да се качил преку па можете да вид на видите овој процес во акција. Па, ако n е еднаков на 1, Collatz на n е 0. Вие не треба да се направи ништо да се вратам на 1. Ти си веќе таму. 

Ако n е 2, што е потребно еден чекор за да се добие на 1. Ќе почнете со 2. Па, 2 не е еднаков на 1. Па затоа се случува да биде еден чекор плус тоа сепак многу чекори презема n поделено со 2. 

2 поделено со 2 е 1. Па го зема еден чекор плус сепак многу чекори што е потребно за 1. 1 зема нула чекори. 

За 3, како што можете да видите, постои вклучени неколку чекори. Одите од 3. А потоа ќе оди во 10, 5, 16, 8, 4, 2, 1. Тоа трае седум чекори за да се вратам на 1. И како што можете да видите, постои неколку други случаи тест тука да пробате вашата програма. Значи, повторно, го паузирате видео. И јас ќе одам сега да скокнете назад на она што вистински процес е тука, она што ова е претпоставка. 

Види дали може да дознаам како да се дефинира Collatz на n така што тоа пресметува колку чекорите што е потребно за да се добие на 1. Па се надевам, ќе го паузира видеото и не само се чека за мене да ви даде одговор тука. Но, ако сте, добро, тука е одговорот во секој случај. 

Значи тука е можна дефиниција на функцијата Collatz. Нашата база case-- ако n е еднаков на 1, се враќаме 0. Тоа не презема чекори за да се вратам на 1. 

Инаку, имаме две рекурзивен cases-- еден за парни броеви и една за чудно. Начинот на кој јас се тестира за парни броеви е да се провери ако n МО 2 изнесува 0. Ова е во основа, повторно, го поставува прашањето, ако се потсетиме што МО is-- ако јас јаз n за 2 не постои остатокот? Тоа би било парен број. 

И така, ако n МО 2 е еднакво на 0 ова тестирање е парен број. Ако е така, би сакал да се врати 1, бидејќи ова е дефинитивно презема еден чекор плус Collatz на број што е половина од мене. Инаку, сакам да се вратат 1 плус Collatz од 3 пати n плус 1. Тоа беше од друга рекурзивен чекор што ние може да се земе да се пресмета Collatz-- на бројот на чекори што е потребно за да се вратат 1 даден број. Па се надевам, овој пример ти дал малку на вкусот на рекурзивен процедури. Се надеваме дека, мислите дека кодот е малку поубаво доколку се спроведат во домот, рекурзивни начин. Но, дури и ако не, рекурзија е навистина моќна алатка сепак. И така тоа е дефинитивно нешто за да ја добиете вашата глава околу себе, затоа што ќе бидете во можност да се создаде прилично кул програми со користење на рекурзија кои инаку би можеле да бидат комплексни да се напише ако сте со користење јамки и повторување. Јас сум Даг Лојд. Ова е CS50.