[За възпроизвеждане на музика] 

Дъг LLOYD: Вие вероятно мислят, че код е просто използва за да постигне дадена задача. Можете да го напиша. Той прави нещо. Това е доста го много. 

Можете да го компилирате. Можете да стартирате програмата. Вие сте добре да тръгвам. 

Но вярвате или не, ако можете да кодира за дълго време, всъщност може да дойде да види код като нещо, което е красиво. Това решава проблема в един много интересен начин, или има нещо наистина Прецизният за начина, по който изглежда. Може да се смее към мен, но е вярно. И рекурсия е един от начините някак да получите тази идея на красива, елегантна изглеждащ код. Това решава проблеми по начин, който са интересни, лесно да се визуализира, и изненадващо кратък. 

Работи по начина, рекурсия е, рекурсивно функция се определя като функция, която призовава себе си като част от неговото изпълнение. Това може да изглежда малко странно, и ще видим малко по- за това, как това работи в един миг. Но пак, те рекурсивни процедури са щеше да бъде толкова елегантна защото те ще да се реши този проблем, без да като всички тези други функции или тези дълги вериги. Ще видите, че тези рекурсивни процедури ще изглежда толкова кратко. И те наистина ще направим кода си изглежда много по-красива. 

Аз ще ви дам един пример на това, за да се види как може да се дефинира рекурсивно процедура. Така че, ако сте запознати с тази от клас по математика преди много години, Има нещо, наречено факторен функция, която обикновено е обозначена като удивителен знак, който се определя над всички положителни числа. И начинът, N факторен се изчислява се умножите всички цифрите по-малко от или равна на N together-- всички числа по-малко от или равно на п заедно. 

Така 5 факторен е 5 пъти 4 пъти 3 пъти 2 пъти 1. И 4 факторен е 4 пъти 3 пъти 2 пъти 1 и така нататък. Можете да получите представа. 

Като програмисти, ние не правим използвате п, удивителен знак. Така че ние ще определите факториел функция като факт от п. И ние ще използваме факторен да създадете рекурсивно решение на даден проблем. И мисля, че може да откриете че това е много по-визуално привлекателни, отколкото Итеративният версия на това, което ние също така ще да погледнем в един миг. 

Така че тук са няколко facts-- каламбур intended-- около factorial-- на факторен функция. The факториела 1, както казах, е един. The факториела 2 е 2 пъти по 1. The факториела 3 е 3 пъти 2 пъти 1, и така нататък. Ние говорихме за 4 и 5 вече. 

Но погледнете в това, не е вярно това? Ако не факториела 2 само 2 пъти факториела на 1? Искам да кажа, факториела на 1 е 1. Така че защо да не можем просто да кажем, че, тъй факторен на 2 е 2 пъти по 1, това е наистина само 2 пъти факториела на 1? 

И тогава, простираща тази идея, Не е факториел от 3 само 3 пъти факториела на 2? И факториела на 4 е 4 пъти факториела на 3, и така нататък? В действителност, факториел на всяко число може просто да се изрази, ако ние натура на превоз на този завинаги. Можем да обобщим вид факторен проблема като това е п времената на факторен на N минус 1. Това е N пъти продукта от всички числа по-малки от мен. 

Тази идея, това обобщение на проблема, ни позволява да рекурсивно определи факторен функция. Когато дефинирате функция рекурсивно, има две неща, които трябва да бъдат част от него. Трябва да има нещо, наречено базов модел, който, когато го задейства, ще спре рекурсивни процес. 

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

Ние трябва да имаме някакъв друг начин да се спре неща, освен нашата програма трясък, защото една програма, която е катастрофи Вероятно не е красиво или елегантна. И така, ние наричаме това базовия модел. Това е просто решение да е проблем, който спира рекурсивни процеса от настъпване. Така че това е една част от рекурсивно функция. 

Втората част е рекурсивно случая. И това е мястото, където рекурсията всъщност ще се проведе. Това е мястото, където функция ще се обадя. 

Тя няма да се нарече точно По същия начин се е наричал. Тя ще бъде леко изменение което прави проблема, че е опитвайки се да реши един мъничък малко по-малък. Но това обикновено преминава отмятат решаване на по-голямата част от разтвора в различна покана за установяване на ред. 

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

Но един от тези изглежда като добър случай да бъде базовия модел. Това е много просто решение. Ние не трябва да правите нищо специално. 

The факториела 1 е само на 1. Ние не трябва да направите всеки размножаване на всички. Тя изглежда като, ако отиваме да се опита да реши този проблем, и ние трябва да се спре рекурсия някъде, ние вероятно искате да спрете то когато стигнем до един. Ние не искаме да се спре преди това. 

Така че, ако ние сме дефиниране нашата факторен функция, ето един скелет за как бихме могли да направим това. Ние трябва да се включите в тези две things-- базовия модел и рекурсивни случая. Какво е най-благоприятният сценарий? Ако п е равно на 1, върнете 1-- това е един наистина прост проблем за решаване. 

The факториела 1 е 1. Това не е нещо, 1 пъти. Това е просто един. Това е много лесно факт. И така, това може да бъде нашата база случай. Ако можем да премина в този 1 функция, ние просто ще се върне 1. 

Какво е рекурсивни случай вероятно изглежда? За всеки друг номер освен една, каква е схемата? Е, ако си говорим факториела на п, това е п пъти факториела на п минус 1. 

Ако ние сме като факториела на 3, това е 3 пъти факториела на 3 минус 1, или 2. И така, ако ние не сме погледнете в 1, в противен случай възвръщаемост н времената на факторен на N минус 1. Това е доста ясен. 

И с цел да има леко по-чисти и по-елегантен код, Знам, че ако имаме единен ред бримки или единен онлайн условни клонове, ние можем да се отървете от всички на фигурни скоби около тях. Така че можем да затвърдят тази за това. Това е точно същото, функционалност, тъй като това. 

Аз съм просто отнемане на Кърли тиранти, защото има само един ред вътрешността на тези условни клонове. Така че те се държат по същия начин. Ако п е равно на 1, 1 върне. В противен случай се върне н пъти факториела на п минус 1. Така че ние правим проблема по-малък. Ако п започва като 5, ние ще върнете 5 пъти факториела на четири. И ние ще видим след малко, когато говорим около stack-- за повикване в друг видео когато говорим за обадете stack-- ще научим за това, защо точно този процес работи. 

Но докато факториел от 5 казва върнете 5 пъти факторен от 4 и 4 ще кажа, OK, добре, възвръщаемост 4 пъти факториела на 3. И както можете да видите, че сме нещо като наближава 1. Ние сме все по-близо и близък до този базов модел. 

И след като ние се удари в базовия модел, Всички предишни функции имате отговор те търсят. Факториел на 2 казваше връщане 2 пъти факториела на 1. Е, факторен от 1 възвръщаемост 1. Така че поканата за факторен 2 може да се върне 2 пъти 1, и да даде, че обратно на факториел 3, която е в очакване на този резултат. 

И тогава той може да се изчисли неговите резултати, 3 пъти 2 е 6, и да го върне на факториел от 4. И пак, ние имаме видео на стека за повикване когато това е илюстрирано малко повече от това, което аз казвам, че точно сега. Но това е то. Това само по себе е решениято на изчисляване на факториел на число. 

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

Така най-общо, но не Винаги, рекурсивно функция може да замени една линия в не-рекурсивни функции. Така че тук, рамо до рамо, е итеративен версия на факториален функция. И двете неща се изчисли точно същото нещо. 

И двамата се изчислява факториела на п. Версията отляво използва рекурсия да го направя. Версията на правото използва итерация да го направя. 

И предизвестие, ние трябва да се декларират променлива цяло число продукт. И тогава ние линия. Докато п е по-голямо от 0, ние запази умножаване съответния продукт, като п и намаляващи п докато изчисляваме продукта. Така тези две функции, отново, направя точно същото нещо. Но те не го правят в точно по същия начин. 

Сега е възможно да се да има повече от една база случай или повече от един рекурсивни случай, в зависимост от това, което си функция се опитваме да направим. Не е задължително да ограничава само до една базова случай или единична рекурсивни случай. Така един пример за нещо с множество базови случаи може да бъде this-- на Фибоначи пореден номер. 

Може би си спомняте от елементарни учебни дни че последователността се определя Фибоначи this-- като първият елемент е 0. Вторият елемент е 1. И двете от тези, които са само по дефиниция. 

Тогава всеки друг елемент се определя като сумата от п и п минус 1 минус 2. Така третия елемент ще бъде 0 плюс 1 е 1. И след това на четвъртия елемент ще бъде втория елемент, 1, плюс третия елемент, 1. И това ще бъде 2. И така нататък и така нататък. 

Така че в този случай, ние имаме две базови случаи. Ако п е равно на 1, върнете 0. Ако п е равно на 2, 1 върне. В противен случай, върнете Фибоначи на п минус 1 плюс Фибоначи на N минус 2. 

Така че това е множество базови случаи. Какво ще кажете за няколко рекурсивни случаи? Е, има нещо наречено хипотезата Collatz. Аз няма да кажа, Знаете ли какво е това, защото това е всъщност нашата окончателното проблем за този конкретен видеоклип. И това е нашият спорт да работят заедно. 

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

В противен случай, проверете това процес отново на п разделена на две. И да видим дали можете да получите обратно към 1. В противен случай, ако п е странно, проверете този процес отново на 3n плюс 1, или 3 пъти N плюс 1. Така че тук имаме един единствен базов модел. Ако п е равно на 1, спрете. Ние не правим повече рекурсия. 

Но ние имаме две рекурсивни случаи. Ако п е дори това, ние правим една рекурсивни случай, наричайки п разделена на две. Ако п е странно, ние правим различен рекурсивни случай на 3 пъти п плюс 1. 

И така в гол за това видео е да вземе втори, пауза във видеото, и да се опитаме и да напиша тази рекурсивни функции Collatz където можете да премине в стойност п и той изчислява колко го стъпки необходимо, за да стигнем до един, ако започнете от п и да следвате тези стъпки до горе. Ако п е 1, е необходимо 0 стъпки. В противен случай, тя ще вземе една стъпка плюс обаче много стъпки, които предприема от двете п разделена на две, ако п е дори, или 3n плюс 1 ако п е странно. 

Сега, аз я сложили на екрана тук Няколко тестови неща за вас, Няколко тестове случаи за вас, за да видите какви са тези различни Collatz номера са, и също илюстрация от стъпките, които Трябва да се отиде през толкова можеш нещо като видите този процес в действие. Така че, ако п е равно на 1, Collatz на п е 0. Не е нужно да се направи всичко, за да се върнем към 1. Вие сте вече там. 

Ако п е 2, е необходимо една стъпка за да стигнем до един. Започвате с 2. Е, 2 не е равно на 1. Така че това ще бъде една стъпка плюс обаче много го стъпки се разделя на п от 2. 

2 е разделена на две 1. Така че това отнема една стъпка плюс обаче много стъпки, необходими за 1. 1 отнема нулеви стъпки. 

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

Виж, ако можете да разберете как да се определят Collatz на п така, че да изчислява колко стъпки е необходимо да стигнем до един. Така че да се надяваме, ти спря видеото и не са само чакат за мен да ви дам отговора тук. Но ако сте, добре, тук е отговорът, така или иначе. 

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

В противен случай, ние имаме две рекурсивни cases-- един за четни числа и една за странно. Начинът, по който тествам за четни числа е да се провери, ако п мод 2 е равно на 0. Това е основно, отново, задава въпроса, Ако си спомняте какво мод is-- ако I разделение п от 2 не е налице остатък? Това ще бъде четен брой. 

И така, ако п мод 2 е равно на 0 е тестване е този четен брой. Ако е така, искам да се върна 1, защото това е определено като една стъпка плюс Collatz на независимо от броя е половината от мен. В противен случай, аз искам да се върне 1 плюс Collatz 3 пъти N плюс 1. Това беше другият рекурсивни стъпка, която ние може да предприеме, за да се изчислява Collatz-- броя на стъпките е необходимо да се върнем 1 даден номер. Така че да се надяваме, този пример ти даде малко на вкус на рекурсивни процедури. Надяваме се, че смятате код е Малко по-красива, ако се прилагат в елегантен, рекурсивни начин. Но дори и ако не е, рекурсия е наистина мощен инструмент все пак. И така, това е определено нещо за да получите главата си наоколо, защото вие ще бъдете в състояние да се създаде много готино програми, използващи рекурсия които иначе биха могли да е сложно да се напише ако използвате вериги и итерация. Аз съм Дъг Лойд. Това е CS50.