[Гуляе музыка] 

Даг Lloyd: Вы, напэўна, думаеце, што Код выкарыстоўваецца толькі для выканання задачы. Вы пішаце гэта. Гэта нешта робіць. Гэта даволі шмат яго. 

Вы скампіляваць яго. Вы запускаеце праграму. Вы добра ісці. 

Але верыць гэтаму ці не, калі вы код на працягу доўгага часу, вы на самой справе можа прыйсці, каб убачыць Код, як нешта, што прыгожа. Гэта вырашае праблему ў вельмі цікавы спосаб, ці ёсць нешта сапраўды акуратны пра тое, як ён выглядае. Вы можаце смяяцца на мяне, але гэта праўда. І Рэкурсія з'яўляецца адным са спосабаў да выгляду гэтая ідэя прыгожая, элегантная, гледзячы код. Гэта вырашае праблемы такім чынам, што цікавыя, лёгка візуалізаваць, і дзіўна кароткім. 

Шляху рэкурсіі працы ёсць, рэкурсіўная функцыя вызначаецца як функцыя, якая выклікае сябе як часткі яго выканання. Гэта можа здацца трохі дзіўным, і мы ўбачым трохі пра тое, як гэта працуе ў цяперашні час. Але зноў жа, гэта рэкурсіўныя працэдуры будзе так элегантны таму што яны збіраюцца каб вырашыць гэтую праблему без маючы ўсе гэтыя і іншыя функцыі або гэтыя доўгія завесы. Вы ўбачыце, што гэта рэкурсіўная працэдуры будзе выглядаць такое кароткае. І яны сапраўды маюць намер зрабіць код выглядаць нашмат прыгажэй. 

Я дам вам прыклад гэта паглядзець, як рэкурсіўная працэдура можа быць вызначана. Так што, калі вы знаёмыя з гэтым ад матэматычным класе шмат гадоў таму, там нешта называецца Функцыя фактарыяла, якія, як правіла, пазначаецца як клічнікам, які вызначана над ўсіх станоўчых цэлых лікаў. І тое, н фактарыяла вылічаецца гэта вы памножыць ўсе лік менш, чым або роўна п together-- усе цэлыя менш, чым або роўна п разам. 

Так 5 фактарыяла 5 разоў 4 разы 3 разы 2 разы 1. І 4 фактарыяла 4 разы 3 разы 2 разы 1 і гэтак далей. Вы атрымліваеце ідэю. 

Як праграмісты, мы не выкарыстоўваць п, клічнік. Так мы вызначым фактарыяла Функцыя як факт п. І мы будзем выкарыстоўваць для стварэння фактарыяла рэкурсіўны рашэнне праблемы. І я думаю, вы маглі б знайсці што гэта нашмат больш візуальна прывабным, чым итеративный версія гэтага якім мы таксама зірнем на ў адзін момант. 

Дык вось пару facts-- каламбур intended-- аб factorial-- фактарыяла. Фактарыяла 1, як я сказаў, гэта 1. Фактарыяла 2 у 2 разы 1. Фактарыяла 3 сакавіка разы 2 разы 1, і гэтак далей. Мы гаварылі пра 4 і 5 ўжо. 

Але, гледзячы на ​​гэта, ці не так гэта? Ня Фактарыял 2 разоў 2 разы Фактарыял 1? Я маю на ўвазе, фактарыяла 1 студзеня. Дык чаму мы не можам проста сказаць, што, так Фактарыял 2 у 2 разы 1, гэта сапраўды ўсяго 2 разы фактарыяла 1? 

А потым распаўсюдзіць гэтую ідэю, ня Фактарыял 3 усяго 3 разы Фактарыял 2? І Фактарыял 4 у 4 разы фактарыяла 3, і гэтак далей? На самай справе, факторный з любога ліку можна проста быць выказана, калі мы неяк з выканаць гэта назаўжды. Мы можам абагульніць выгляд факторный праблема як гэта п раз у Фактарыяла N мінус 1. Гэта п раз прадукт ўсе нумары менш, чым мне. 

Гэтая ідэя, гэта Абагульненне задачы, дазваляе рэкурсіўна вызначыць функцыю фактарыяла. Калі вы вызначаеце функцыю рэкурсіўна, ёсць дзве рэчы, якія павінны быць часткай гэтага. Вы павінны мець нешта, званае базавы выпадак, які, калі вы запускаеце яго, будзе спыніць працэс рэкурсіўнага. 

У адваротным выпадку, функцыя, якая выклікае у тым: як вы маглі imagine-- можа працягвацца вечна. Функцыя выклікае функцыю называе выклікі функцый функцыя выклікае функцыю. Калі вы не ёсць спосаб , Каб спыніць яго, вашу праграму будзе эфектыўна затрымаўся ў бясконцым цыкле. Гэта прывядзе да краху ў рэшце рэшт, таму што ён будзе працаваць з памяці. Але гэта да справы не адносіцца. 

Мы павінны мець іншы спосаб, каб спыніць рэчы, акрамя нашай праграмы разбіваючы, таму што праграма, якая разбівае гэта верагодна, не прыгожа або элегантна. І так мы называем гэта базавы варыянт. Гэта простае рашэнне да праблемы, які спыняецца рэкурсіўны працэс узнікнення. Дык вось адна частка рэкурсіўная функцыя. 

Другая частка рэкурсіўны выпадак. І гэта, дзе Рэкурсія на самай справе адбываецца. Гэта тое, дзе функцыя называць сябе. 

Гэта не будзе называць сябе сапраўды гэтак жа, як яго называлі. Гэта будзе невялікая змена што робіць праблему гэта спрабуе вырашыць маленькі трохі менш. Але гэта, як правіла праходзіць даляр рашэння большую частку раствора на іншы выклік па лініі. 

Які з гэтых поглядаў як базавай выпадку тут? Які з гэтых выглядае як простае рашэнне праблемы? У нас ёсць куча факториалов, і мы маглі б працягваць адбываецца on-- 6, 7, 8, 9, 10 і гэтак далей. 

Але адзін з гэтых выглядае як добры выпадак, каб быць базавым сцэнаром. Гэта вельмі простае рашэнне. Мы не павінны рабіць нічога асаблівага. 

Фактарыяла 1 знаходзіцца ўсяго ў 1. Мы не павінны рабіць нічога множанне на ўсіх. Падобна на тое, калі мы збіраемся каб паспрабаваць вырашыць гэтую праблему, і мы павінны спыніць Рэкурсія дзе-небудзь, мы, верагодна, хочаце, каб спыніць гэта калі мы атрымліваем да 1. Мы не хочам, каб спыніць раней. 

Так што, калі мы вызначаем наш фактарыяла, вось каркас для як мы маглі б гэта зрабіць. Мы павінны падключыць ў гэтых двух things-- базавы варыянт і рэкурсіўны выпадак. Што базавы варыянт? Калі п роўна 1, вярнуцца 1-- гэта сапраўды простая задача вырашыць. 

Фактарыяла 1 студзеня. Гэта не 1 раз нічога. Гэта проста 1. Гэта вельмі проста факт. І так, што можа быць нашым базавым сцэнаром. Калі нас прайшло 1 у гэтым Функцыя, мы проста вяртае 1. 

Што рэкурсіўны Справа, верагодна, выглядаць? Для кожнага іншы нумар акрамя 1, што карціна? Ну, калі мы бярэм фактарыяла N, Гэта п раз фактарыяла N мінус 1. 

Калі мы бярэм фактарыяла з 3, гэта ў 3 разы Фактарыял 3 мінус 1, або 2. І таму, калі мы не гледзячы на ​​1, інакш Вяртанне ў п раз Фактарыяла N мінус 1. Гэта даволі проста. 

І дзеля наяўнасці трохі чысцей і больш элегантны код, ведаю, што калі ў нас ёсць завесы аднарадковы або аднарадковы ўмоўныя галіны, мы можам пазбавіцца ад усіх з Фігурныя дужкі вакол іх. Такім чынам, мы можам аб'яднаць гэта з гэтым. Гэта сапраўды гэтак жа, Функцыянальнасць, як гэты. 

Я проста забіраючы кучаравыя дужкі, таму што ёсць толькі адна лінія ўнутры гэтых умоўных галін. Такім чынам, гэтыя паводзяць сябе аднолькава. Калі п роўна 1, вяртае 1. У адваротным выпадку вярнуць п раз фактарыяла N мінус 1. Такім чынам, мы робім праблему менш. Калі п пачынаецца як 5, мы збіраемся вярнуцца 5 разоў фактарыяла 4. І мы ўбачым у хвіліну, калі мы гаворым аб stack-- выкліку ў іншым відэа дзе мы гаворым пра патэлефанаваць stack-- мы даведаемся аб тым, чаму менавіта гэты працэс працуе. 

Але ў той час, Фактарыял 5 кажа вярнуцца ў 5 разоў фактарыяла 4, і 4 будзе казаць, добра, добра, вяртанне 4 разы Фактарыял 3. І, як вы бачыце, мы роду набліжаецца да 1. Мы ўсё бліжэй і бліжэй да гэтай базавай выпадку. 

І як толькі мы трапілі ў базавы варыянт, ўсе папярэднія функцыі ёсць адказ, які яны шукалі. Фактарыяла 2 казаў вяртанне 2 разы Фактарыял 1. Ну, факторный 1 вяртаецца 1. Такім чынам, заклік да фактарыяла 2 можа вярнуцца ў 2 разы 1, і даць, што спіной да фактарыяла 3, які чакаў гэтага выніку. 

І тады ён можа разлічваць яго вынік, 3 разы лютым 6, і аддаць яго фактарыяла 4. І зноў, у нас ёсць відэа ў стэку выклікаў дзе гэта паказана трохі больш, чым тое, што я кажу цяпер. Але гэта ён. Гэта само па сабе рашэнне разліку фактарыяла колькасці. 

Гэта толькі чатыры радкі кода. Гэта вельмі выдатна, ці не так? Гэта свайго роду сэксуальны. 

Такім чынам, у агульным, але не заўсёды, рэкурсіўная функцыя можа замяніць цыклу ў нерекурсивный функцыя. Дык вось, побач, гэта ітэрацыйныя версія функцыі фактарыяла. Абодва гэтыя Статыстыка роўна тое ж самае. 

Яны абодва разліку фактарыяла п. Версія злева выкарыстоўвае рэкурсіі, каб зрабіць гэта. Версія аб праве выкарыстоўвае ітэрацыю, каб зрабіць гэта. 

І заўважце, мы павінны абвясьціць пераменная цэлы твор. І тады мы пятля. Пакуль п больш, чым 0, то размнажацца, што прадукт па п і не змяншаючы п да мы вылічыць твор. Такім чынам, гэтыя дзве функцыі, зноў жа, зрабіць тое ж самае. Але яны не робяць гэта ў сапраўды такім жа чынам. 

Зараз можна больш чым адну базу так, ці больш чым адзін Рэкурсіўны выпадак, у залежнасці на што ваша функцыя спрабуе зрабіць. Вы не абавязкова абмяжоўваецца толькі адзін базавы выпадак або адзін рэкурсіўны выпадак. Так што прыклад чагосьці з мноствам базавых выпадках можа быць this-- Фібаначы парадкавы нумар. 

Вы можаце ўспомніць з элементарныя школьныя дні што паслядоўнасць Фібаначы вызначаецца як this-- першы элемент 0. Другім элементам з'яўляецца 1. Абодва з іх з'яўляюцца проста па азначэнні. 

Тады кожны элемент вызначаецца у выглядзе сумы п мінус 1 і мінус 2 н. Так трэцяга элемента будзе 0 + 1 = 1. А потым чацвёрты элемент будзе другі элемент, 1, плюс трэці элемент, 1. І, што б 2. І гэтак далей, і гэтак далей. 

Такім чынам, у гэтым выпадку, у нас ёсць два базавых выпадкаў. Калі п роўна 1, вярнуць 0. Калі п роўна 2, вяртае 1. У адваротным выпадку, вяртанне Фібаначы п мінус 1 плюс Фібаначы п мінус 2. 

Дык вось некалькі базавых выпадкаў. Што аб некалькіх выпадках рэкурсіўных? Ну, ёсць сёе-тое называецца гіпотэза Коллатц. Я не збіраюся казаць, Вы ведаеце, што гэта такое, таму што гэта на самай справе наш апошні Праблема для дадзенага відэа. І гэта наша практыкаванні працаваць разам. 

Дык вось тое, што Коллатц гіпотэза is-- гэта ставіцца да любога натуральнага. І гэта прадугледжвае, што гэта заўсёды можна вярнуцца 1, калі вы выканаеце наступныя дзеянні. Калі п = 1, спыніцца. Мы вярнуліся да 1, калі п = 1. 

У адваротным выпадку, прайсці праз гэта Працэс зноў на п дзеліцца на 2. І паглядзець, калі вы можаце атрымаць назад да 1. У адваротным выпадку, калі п няцотна, прайсці гэты працэс зноў на 3n плюс 1, ці 3 разы N плюс 1. Дык вось у нас ёсць адзін базавы варыянт. Калі п роўна 1, спыніцца. Мы не робім больш Рэкурсія. 

Але ў нас ёсць два рэкурсіўных спраў. Калі п цотна, мы робім адну рэкурсіўнай Справа, называючы п дзеліцца на 2. Калі п няцотна, мы робім розныя рэкурсіўная справа па 3 разы п плюс 1. 

І таму мэта гэтага відэа прыняць секунды, паўза відэа, і паспрабаваць напісаць гэта рэкурсіўная функцыя Коллатц дзе вы праходзіце ў значэнні п, і ён разлічвае, колькі крокаў патрабуецца, каб атрымаць 1, калі вы пачынаеце з п і вы будзеце прытрымлівацца гэтыя крокі наверсе. Калі п = 1, ён прымае меры 0. У адваротным выпадку, гэта будзе адзін крок плюс аднак шмат крокаў ён бярэ на любым п дзеліцца на 2, калі п цотна, або 3n + 1 калі п няцотна. 

Зараз, я паклаў на экране тут пару тэставых рэчаў для вас, пару тэставых варыянтаў для вас, каб убачыць тое, што гэтыя розныя нумары Collatz з'яўляюцца, а таксама ілюстрацыя пра крокі, якія трэба перажыць, каб вы маглі накшталт разглядаюць гэты працэс у дзеянні. Такім чынам, калі п роўна 1, Коллатц п 0. Вы не павінны рабіць нічога, каб вярнуцца да 1. Вы ўжо там. 

Калі п 2, ён займае адзін крок, каб дабрацца да 1. Вы пачынаеце з 2. Добра, 2 не роўная 1. Такім чынам, гэта будзе адзін крок плюс, аднак многія крокі, якія ён бярэ на п дзеліцца на 2. 

2 дзеліцца на 2 студзеня. Так ён прымае адзін крок плюс аднак шмат крокаў патрабуецца для 1. 1 займае нулявыя крокі. 

Для 3, як вы можаце бачыць, ёсць ўдзел нямала крокаў. Вы ідзяце ад 3. І тады вы ідзяце ў 10, 5, 16, 8, 4, 2, 1. Гэта зойме сем крокаў, каб вярнуцца да 1. І, як вы бачыце, ёсць некалькі іншых выпадкаў тут выпрабаванняў каб праверыць вашу праграму. Такім чынам, яшчэ раз, паўза відэа. І я пайду скакаць назад цяпер тое, што сам працэс тут, тое, што гэтая гіпотэза. 

Глядзіце, калі вы можаце высветліць, як вызначыць Collatz п такім чынам, што ён падлічвае, колькі крокі трэба, каб атрымаць 1. Так, мы спадзяемся, вы паўзу відэа і вы не проста чакае мяне каб даць вам адказ тут. Але калі вы, ну, вось адказ у любым выпадку. 

Дык вось магчымае вызначэнне функцыі Collatz. Наша база case--, калі п роўны 1, мы вяртаемся 0. Гэта не прымаць якія-небудзь крокі, каб вярнуцца да 1. 

У адваротным выпадку, у нас ёсць два рэкурсіўны cases-- адным для цотных лікаў і адзін для няцотных. Як я праверыць цотных лікаў каб праверыць, калі п па модулю 2 роўны 0. Гэта, у асноўным, зноў жа, задаючы пытанне, калі ўспомніць, што мод is-- калі я падзяляй п на 2 не існуе ніякага астатку? Гэта было б цотная колькасць. 

І так, калі п па модулю 2 роўны 0 Тэставанне гэта цотная колькасць. Калі гэта так, я хачу, каб вярнуць 1, таму што гэта, безумоўна, адзін крок плюс Collatz з усе лік палова мяне. У адваротным выпадку, я хачу, каб вярнуць 1 плюс Коллатц 3 разы N плюс 1. Гэта быў іншы рэкурсіўны крок, які мы маглі б распачаць для разліку Collatz-- колькасць крокаў ён прымае, каб вярнуцца 1 прысвоены нумар. Так, мы спадзяемся, гэты прыклад даў вам крыху з густу рэкурсіўных працэдур. Спадзяюся, вы думаеце, код трохі больш прыгожым, калі рэалізаваны у элегантным рэкурсіўнай чынам. Але нават калі няма, Рэкурсія з'яўляецца сапраўды магутны інструмент, тым не менш. І так што гэта вызначана нешта каб атрымаць сваю галаву вакол, таму што вы будзеце ў стане стварыць Даволі халаднавата, якія выкарыстоўваюць Рэкурсія праграмы якія маглі б быць складаным, каб напісаць калі вы выкарыстоўваеце завес і ітэрацыі. Я Дуг Лойд. Гэта CS50.