[Мусиц плаиинг] 

Даг Ллоид: Вероватно мислите да је Код је само користи за постизање задатак. Ти си то написати. То ради нешто. То је прилично је много. 

Ви га саставити. Ви покрените програм. Добар си да идеш. 

Али веровали или не, ако ви код за дуго времена, заправо могу доћи да видим Код као нешто што је прелепо. То решава проблем у веома занимљив начин, или само нешто стварно уредно о начину то изгледа. Можда се смијати на мене, али то је истина. И рецурсион је један од начина на неки начин добити ову идеју од лепа, елегантна изгледа код. То решава проблеме на начине који су занимљиви, лако замислити, и изненађујуће кратко. 

Тхе Ваи рецурсион радови је, рекурзивни функција се дефинише као функција која позива Сама као део његовог извршења. То можда делује помало чудно, па да видимо мало како то функционише у једном тренутку. Али опет, то рецурсиве процедуре су ће бити тако елегантно јер они иду да реше овај проблем без да све ове друге функције или ове дуге петље. Видећете да су рекурзиван процедуре ће изгледати тако кратак. И они заиста ће направити Ваш код изгледају много лепше. 

Даћу вам један пример ово да видим како рекурзивни процедура може бити дефинисани. Дакле, ако сте упознати са овим из математике пре много година, дошло је нешто што се зове факторијел функција, која је обично означен као знаком узвика који је дефинисан над свим позитивних целих бројева. И начин на који н факторијел се обрачунава је помножите све бројеве мање од или једнако н заједно-- све целе бројеве мање од или једнак н заједно. 

Дакле, 5 факторијални је 5 пута 4 пута 3 пута 2 пута 1. И 4 факторијални је 4 пута 3 пута 2 пута 1 и тако даље. Можете добити идеју. 

Као програмери, ми не знамо Користите Н, узвичник. Тако ћемо дефинисати факторијални функција као чињенице н. И ми ћемо користити факторијел за креирање рекурзивни решење проблема. И мислим да би пронашли да је то много више визуелно апелујући од итеративни верзија овога, којих такође ћемо да погледамо у тренутку. 

Дакле, ево пар фацтс-- пун интендед-- о фацториал-- факторијел функција. Подаци су обрађени од 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, и тако даље? У ствари, фацториал од било ког броја могу само може изразити ако смо некако од носе ово заувек. Можемо врста генерализовати Подаци су обрађени Проблем Пошто је н пута на факторијел од н минус 1. То је н пута производ сви бројеви мање од мене. 

Ова идеја, ово генерализација проблема, нам омогућава да рекурсивно дефинисати Факториал функцију. Када дефинишете функцију рекурсивно, ту је две ствари које треба да буду део тога. Потребно је да имате нешто што се зове основни случај, који, када га покренути, ће зауставити Рекурзив процес. 

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

Морамо да имамо неки други начин да се заустави ствари поред нашег програма разбијаш, јер програм који се срушио је Вероватно није лепа или елегантно. И тако зовемо то основни случај. Ово је једноставно решење на проблем који се зауставља Рекурзив процес од дешавају. Дакле, то је један део рекурзивна функција. 

Други део је Рекурзив случај. И ово је место где рекурзије ће заправо се одржати. Ово је место где функција ће се звати. 

То се неће звати тацно Исто тако се звала. То ће бити мала варијација који чини проблем је то покушавамо да решимо малени мало мањи. Али генерално пролази долар решавања већи део решења на другом позиву низ линију. 

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

Али један од тих личи на Добар пример да је основни случај. То је веома једноставно решење. Не морамо да радимо ништа посебно. 

Подаци су обрађени 1 је само 1. Ми не треба да урадите било множење уопште. Чини се као да идемо да покушамо да решимо овај проблем, и морамо да заустави рецурсион негде, вероватно желите да престанете то кад стигнемо до 1. Ми не желимо да зауставимо пре тога. 

Дакле, ако смо дефинисања наш факторијел функција, Овде је костур за како бисмо могли да урадимо то. Морамо да укључите у ове две ствари-- база случај и рекурзивност случај. Шта је основни случај? Ако је н је једнако 1, врате 1-- то је стварно једноставан проблем да реши. 

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

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

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

И због имају незнатно чистији и елегантан број, знамо да ако имамо једно линије петље или једнолинијски условне гране, можемо се ослободити свих од цурли протеза око њих. Дакле, можемо консолидовати то то. То је потпуно иста функционалност као ово. 

Само одузимање таласасту брацес, јер постоји само једна линија унутар тих условних грана. Дакле, то се понашају идентично. Ако је н је једнако 1, врате 1. У супротном се врати н пута Подаци су обрађени од н минус 1. Дакле, ми правимо проблем мањи. Ако је н почиње као 5, идемо у врати 5 пута факторијел 4. И ми ћемо видети у минут када говоримо о позиву стацк-- у другом видеу где причамо о позовите стацк-- ћемо научити о томе зашто баш овај процес функционише. 

Али док факторијални 5 каже врати 5 пута у факторијел 4, и 4 ће рећи, ОК, повратак 4 пута факторијалног од 3. И као што видите, ми смо врста приближава 1. Ми смо све ближе и ближе том основном случају. 

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

И онда може израчунати Његов резултат, 3 пута 2 је 6, и да га врати у факторијелском 4. И опет, имамо видео на Цалл Стацк где је то илустрована помало више него што ја говорим сада. Али, то је то. То је једино решење за израчунавање факторијел броја. 

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

Дакле генерално, али не Увек, рекурзивни функција може да замени петље у не-рекурзивно функција. Па ево, раме уз раме, је итеративни верзија факторијел функција. Оба ова Ð¿Н потпуно иста ствар. 

Обојица су израчунати факторијел н. Верзија са леве стране користи рекурзију да то уради. Верзија са десне стране користи итерацију да то уради. 

И обавештење, морамо да се изјасни променљиве цео број производа. И онда петља. Све док н је већи од 0, ми смо држати множењем тај производ са Н и децрементинг н до смо укупну производ. Дакле, ове две функције, поново, раде потпуно исту ствар. Али они не раде у управо на исти начин. 

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

Можда се сећате из основних школа дана да је Фибоначијев низ дефинисан као ово-- први елемент је 0. Други елемент је 1. Оба су то само по дефиницији. 

Затим сваки други елемент је дефинисан као збир Н минус 1 и н минус 2. Дакле, трећи елемент ће бити 0, плус 1 је 1. И онда је четврти елемент би био други елемент, 1, плус трећи елемент, 1. И то би било 2. И тако даље и тако даље. 

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

Дакле, то је више базне случајеве. Шта више рекурзивних случајевима? Па, има нешто назива Цоллатз Цоњецтуре. Нећу да кажем, знате шта је то, јер то је заправо наш финални проблем за овом видеу. И то је наша вежба да раде заједно. 

Дакле, овде је оно што је Цоллатз Цоњецтуре је-- се односи на сваки позитиван цео број. И спекулише да је увек могуће да се врати на 1 ако пратите ове кораке. Ако је н 1, стани. Ми смо се вратили на 1 ако је н 1. 

У супротном, пролазе кроз ово Процес поново Н подељен 2. А видите да ли можете да се вратим на 1. У супротном, ако је н непаран, проћи кроз Овај процес поново 3Н плус 1, или 3 пута Н плус 1. Дакле, овде имамо једну базу случај. Ако је н једнак 1, заустави. Не радимо виље рекурзију. 

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

И тако је циљ за овај видео је да мало, паузирање видео, и покушати ово написао рекурзиван функција Цоллатз где пролазе у вредности н, и обрачунава Колико их корака потребно да стигнете до 1. ако почнете од н а ви пратите те кораке изнад. Ако је н 1, потребно 0 кораке. У супротном, то ће један корак плус међутим много корака да преузима или Н подељено са 2 ако је н чак, или 3н, плус 1 ако је н непаран. 

Сада сам ставио на екрану овде неколико тестова ствари за вас, пар тестова предмета за вас, да видимо шта ови различити Цоллатз бројеви, као и илустрација од корака који треба прошли тако можете некако види овај процес у акцији. Дакле, ако њеједнако 1, Цоллатз од н је 0. Не морате да урадите шта да се вратим на 1. Ти си већ тамо. 

Ако је н 2, потребно један корак да до 1. Можете почети са 2. Па, 2 није једнако 1. Дакле, то ће бити још један корак плус, међутим многе то кораци преузима Н подељен 2. 

2 подељено са 2 је 1. Дакле, потребно је један корак плус међутим много корака је потребно за 1. 1 узима нула кораке. 

За 3, као што видите, ту је доста корака укључени. Ти иди од 3. И онда да 10, 5, 16, 8, 4, 2, 1. Потребно је седам корака да се вратим на 1. И као што видите, ту је пар других тест случајева овде да тестирате свој програм. Дакле, опет, паузирање видео. И ја ћу отићи скочити се сада на шта је стварни процес је овде, шта је ово претпоставка је. 

Видите да ли могу да схватим како дефинисати Цоллатз од н тако да обрачунава колико кораке је потребно да стигнете до 1. Дакле, надамо се, ви сте застао видео и не чекају ме да вам дам одговор овде. Али, ако сте, добро, Овде је ионако одговор. 

Дакле, овде је могућа дефиниција функције Цоллатз. Наша база цасе-- ако је н једнак 1, враћамо 0. Није потребно било кораци да се вратим на 1. 

Иначе, имамо два рекурзивни торбе-- један за парним бројевима и један за чудно. Како сам тестирати парним бројевима јесте да проверите да ли Н мод 2 износи 0. То је у основи, опет, постављам питање, ако се сећате шта мод је-- ако подела Н од 2 је нема остатак? То ће бити паран број. 

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