>> ZAMYLA: Для таго, каб зразумець, рэкурсіі, вы павінны
спачатку зразумець рэкурсіі.
Маючы рэкурсіі ў праграмных дызайну сродкаў што ў вас ёсць самосправочные
вызначэння.
Рэкурсіўныя структуры дадзеных, напрыклад, гэта структуры дадзеных, якія
ўключаюць сябе ў іх вызначэння.
Але сёння мы збіраемся засяродзіцца на рэкурсіўных функцый.
>> Нагадаем, што функцыі прымаюць ўваходы, аргументы, і вяртае значэнне, як і іх
Выхад у асобе гэтая схема тут.
Мы будзем думаць аб поле як цела функцыя, які змяшчае набор
інструкцыі, якія інтэрпрэтуюць ўваход і забяспечваюць выхад.
Пры больш дбайным вывучэнні ўнутры цела функцыя можа выявіць выклікі
іншыя функцыі, а таксама.
Вазьміце гэтую простую функцыю, Фу, што займае адну радок у якасці ўваходных дадзеных і
друкуе колькі лістоў што радок мае.
Функцыя STRLEN, для даўжыні радка, называецца, выхад якога
патрабуецца для выкліку Printf.
>> Цяпер, тое, што робіць рэкурсіўнага функцыю асаблівага ў тым, што ён называе сябе.
Мы можам прадставіць гэты рэкурсіўны патэлефанаваць з гэтым аранжавай стрэлкай
цыкл назад да сябе.
Але выкананне сябе зноў будзе толькі зрабіць яшчэ адзін рэкурсіўны выклік, і
яшчэ і яшчэ.
Але рэкурсіўныя функцыі не можа быць бясконцым.
Яны павінны пакласці канец так ці інакш, ці ваш Праграма будзе працаваць вечна.
>> Так што мы павінны знайсці спосаб разарваць з рэкурсіўных выклікаў.
Базавы варыянт Мы называем гэта.
Калі базавы варыянт ўмова выконваецца, функцыя вяртае без
іншы рэкурсіўны выклік.
Вазьміце гэтую функцыю, прывітанне, пусты функцыі , Якая прымае Int N ў якасці ўваходных дадзеных.
Базавы варыянт стаіць на першым месцы.
Калі п менш за нуль, друку спатканні і вярнуцца Ва ўсіх астатніх выпадках,
Функцыя будзе друкаваць прывітанне і выканаць рэкурсіўны выклік.
Яшчэ адзін званок да функцыі прывітанне з памяншаецца уваходнае значэнне.
>> Цяпер, нават пры тым, што мы друкуем прывітанне, функцыя не будзе спыніць пакуль мы не
вярнуць яго які вяртаецца тып, у гэтым выпадку пустаты.
Такім чынам, для кожнага п, акрамя базавага варыянту, гэтая функцыя прывітанне вернецца прывітанне
н мінус 1.
Так як гэтая функцыя з'яўляецца нікчэмным, хоць, мы не будзе відавочна тып якое вяртаецца тут.
Мы проста выканаць функцыю.
Так называючы прывітанне (3) будзе друкаваць прывітанне і выканаць прывітанне (2), які выконвае прывітанне (1) адзін
які выконвае Hi (0), дзе базавы варыянт ўмова.
Так прывітанне (0) друкуе спатканні і вяртаецца.
>> ОК.
Так што цяпер мы разумеем асновы рэкурсіўныя функцыі, якія яны павінны
па меншай меры адзін базавы варыянт, а таксама рэкурсіўны выклік, давайце пяройдзем да
больш значным прыкладам.
Той, які не проста вярнуць ня анулюе ні на што.
>> Давайце зірнем на фактарыяла Аперацыя выкарыстоўваецца часцей за ўсё ў
імавернасны разлікі.
Фактарыяла п з'яўляецца творам кожны станоўчае цэлае лік менш
і роўная п.
Так фактарны пяць у 5 разоў 4 разоў 3 раз 2 раз 1, каб даць 120.
Чатыры фактарны ў 4 разы 3 разы 2 раз 1 з атрыманнем 24.
І тое ж самае правіла ўжываецца любое станоўчае цэлае.
>> Такім чынам, як мы маглі б напісаць рэкурсіўны функцыя, якая вылічае фактарыяла
шэрагу?
Ну, мы павінны вызначыць, як базавы варыянт і рэкурсіўны выклік.
Рэкурсіўны выклік будзе такім жа, для ўсіх выпадкаў за аснову, акрамя
выпадак, які азначае, што мы павінны будзем знайсці мадэль, якая дасць нам нашу
Жаданы вынік.
>> Для гэтага прыкладу, паглядзім, як 5 фактарыяла ўключае множання 4 па 3 на 2 на 1
І ў той жа множанне знаходзіцца тут,
Вызначэнне 4 фактарыяла.
Такім чынам, мы бачым, што 5 фактарыяла ўсяго 5 раз 4 фактарны.
Цяпер жа гэтая мадэль прымяняецца да 4 фактарыяла, а?
Так.
Мы бачым, што 4 фактарны ўтрымлівае множанне 3 разы 2 раз 1,
Сам жа вызначэнне, як 3 фактарыяла.
Так 4 фактарны роўная 4 разы 3 фактарны, і гэтак далей і таму падобнае нашай
шаблон не прыліпае да 1 фактарыяла, якая па вызначэнні роўная 1.
>> Там няма іншай станоўчы цэлыя пакінулі.
Таму ў нас ёсць узор для наш рэкурсіўны выклік.
н фактарны роўная п раз фактарыяла п мінус 1.
І наш базавы сцэнар?
Гэта будзе проста наша вызначэнне 1 фактарыяла.
>> Так што цяпер мы можам перайсці да напісання код функцыі.
Для базавага варыянту, мы будзем мець стан п роўная роўная 1, дзе
мы вернемся 1.
Тады перайсці на рэкурсіўнага выкліку, мы вернемся п раз
Фактарыяла п мінус 1.
>> Зараз давайце праверым гэта наша.
Давайце паспрабуем фактарыяла 4.
За нашай функцыі ён роўны у 4 разы фактарыяла (3).
Фактарыяла (3) роўная 3 разы фактарных (2).
Фактарыяла (2) роўная 2 разы фактарны (1), якая вяртае 1.
Фактарыяла (2) зараз вяртае 2 разы 1, 2.
Фактарыяла (3) зараз можна вярнуцца 3 разы 2, 6.
І, нарэшце, фактарны (4) вяртае 4 разы 6, 24.
>> Калі ўзнікаюць якія-небудзь цяжкасці з рэкурсіўнага выкліку, рабіць выгляд, што
функцыя працуе ўжо.
Тое, што я маю на ўвазе, што вы павінны давяраць сваім рэкурсіўныя выклікі, каб вярнуцца
правільныя значэння.
Напрыклад, калі я ведаю, што фактарны (5) роўная 5 разоў
фактарны (4), я збіраюся верыць, што фактарны (4) дасць мне 24.
Думайце пра гэта як зменнай, калі вы будзе, як калі б вы ўжо вызначаны
фактарыяла (4).
Такім чынам, для любога фактарыяла (п), гэта твор п і
папярэдні фактарны.
І гэта папярэдняя фактарны атрымліваецца шляхам выкліку
Фактарыяла п мінус 1.
>> Дык вось, бачыце, калі вы можаце рэалізаваць рэкурсіўная функцыя сябе.
Загрузіце ваш тэрмінал, або run.cs50.net, і напісаць функцыю суму
, Якая прымае лік п і вяртае Сума ўсіх запар станоўчы
цэлыя лікі ад п да 1.
Я выпісаў сумы некаторых значэнні, якія дапамогуць вам наш.
Па-першае, высветліць, базавы варыянт стан.
Затым паглядзіце на сумы (5).
Ці можаце вы выказаць яе праз іншы сумы?
Цяпер, што тычыцца сумы (4)?
Як вы можаце выказаць суму (4) з пункту гледжання іншы сумы?
>> Калі ў вас ёсць сума (5) і сума (4) выяўляецца праз іншых сум, см.
калі вы можаце вызначыць шаблон для сумы (п).
Калі няма, паспрабуйце некалькі іншых нумароў і выказваць свае сумы ў
ўмовы яшчэ нумары.
Выяўляючы заканамернасці для дыскрэтных нумары, вы добра на вашым шляху да
выяўлення ўзор для любога п.
>> Рэкурсія гэта сапраўды магутны інструмент, таму, вядома, гэта не абмяжоўваецца
матэматычныя функцыі.
Рэкурсія можа быць выкарыстаны вельмі эфектыўна пры працы з дрэвамі, напрыклад.
Праверце хапае дрэў для больш глыбокі аналіз, але цяпер
нагадаць, што бінарныя дрэвы пошуку, у прыватнасці, складаюцца з вузлоў, кожны
са значэннем і двух паказальнікаў вузлоў.
Як правіла, яна прадстаўлена бацькоўскі вузел, які мае адзін радок, якая паказвае
на левы вузел дзецьмі і адзін ў патрэбны даччынага вузла.
Структура бінарнага пошуку дрэва добра паддаецца
да рэкурсіўнага пошуку.
Рэкурсіўны выклік альбо пераходзіць у налева або права вузел, але больш
таго, што ў дрэве кароткага замыкання.
>> Дапусцім, вы хочаце выканаць аперацыю кожны вузел у двайковым дрэве.
Як вы маглі б пайсці з гэтай нагоды?
Ну, вы маглі б напісаць рэкурсіўнага функцыя, якая выконвае аперацыю
на бацькоўскім вузле і робіць рэкурсіўны патэлефанаваць у той жа функцыі,
праходзячы ў левай і правы даччыныя вузлы.
Напрыклад, гэта функцыя, Foo, што змяняе значэнне дадзенага вузла і
ўсе яго дзяцей да 1.
База выпадку нулявога прычын вузлоў функцыя для вяртання, паказваючы
што няма ніякіх вузлоў пакінулі ў гэтым поддерево.
>> Давайце ісці праз яго.
Першы бацька 13.
Мы мяняем яго значэнне на 1, а затым выклікаць наша функцыя злева, а
як права.
Функцыя, Фу, называецца злева суб-дрэва спачатку, так што левая вузел
будзе пераведзены на 1 і Foo будзе назваць на дзяцей гэтага вузла,
Першы левы, а затым правы, і гэтак далей і таму падобнае.
І сказаць ім, што філіялы не маюць больш дзяцей, так жа працэс
будзе працягвацца на працягу правільных дзяцей да вузлы усё дрэва ў ня
пераведзены ў 1.
>> Як вы можаце бачыць, вы не абмежаваныя проста адзін рэкурсіўны выклік.
Гэтак жа, як многія, як будзе атрымаць працу.
Што калі ў вас на дрэва, дзе кожны вузел было трое дзяцей,
Злева, сярэдні, і правільна?
Як бы вы змяніць Foo?
Ну, проста.
Проста дадаць яшчэ адзін рэкурсіўны выклік і прайсці ў паказальніку сярэдняга вузла.
>> Рэкурсія з'яўляецца вельмі магутным і ня кажучы элегантна, але гэта можа быць
складаная канцэпцыя на першы, так таму і быць пацыенту і не спяшайцеся.
Пачніце з базавага варыянту.
Гэта, як правіла, самы просты для выяўлення, а затым вы можаце працаваць
назад адтуль.
Вы ведаеце, што вам трэба для дасягнення вашых базавы варыянт, так што можа
даць вам некалькі саветаў.
Паспрабуйце выказаць адзін канкрэтны выпадак у ўмовы іншых выпадках, або ў падмноства.
>> Дзякуй за прагляд гэтай кароткай.
Па крайняй меры, цяпер вы можаце зразумець жарты, як гэта.
Мяне клічуць Zamyla, і гэта CS50.
>> Вазьміце гэтую функцыю, прывітанне, несапраўднымі функцыя, якая прымае
унутр, п, у якасці ўваходных дадзеных.
Базавы варыянт стаіць на першым месцы.
Калі п менш 0, друку "Да пабачэння" і вяртанне.