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, друку "Да пабачэння" і вяртанне.