ЗАМИЛА: Да бисмо разумели рекурзије, морате прво разумети рекурзија. Имајући рекурзија у програмским дизајн средствима да имате самореферентан дефиниције. Рекурзивне структуре података, на пример, су структуре података које укључују се у њихове дефиниције. Али данас, идемо да се фокусирамо на рекурсивних функцијама. 

Подсетимо се да функција узети инпуте, аргументи, и враћају вредност као свој излаз заступа ово дијаграм овде. Ми ћемо мислити о оквира као тело функција, која садржи скуп инструкције да интерпретирају улаз и обезбедити излаз. Узимајући изблиза унутар тела функција може да открије позиве на друге функције. Узми ову једноставну функцију, фоо, који узима један стринг као улаз и отисци колико слова да има жица. Функција стрлен, за дужине, се зове, чији је излаз потребна за позив на принтф. 

Сада, оно што чини рекурзивни функцију Посебан је да себе назива. Можемо представљају ову рекурзивно позвати са овом наранџастом стрелицом лоопинг назад на себе. Али се опет изврши само ће направи још један рекурзивни позив, а још и други. Али Рекурзивне функције не може бити бесконачан. Они морају да некако оконча, или ваш Програм ће покренути заувек. 

Дакле, морамо да нађемо начин да се пробије од Рекурзив позива. Ми то називамо база случај. Када се састао база случај услов, Функција враћа без још један рекурзивни позив. Узми ову функцију, здраво, празнина функција који заузима инт н као улаз. Основни случај долази прво. Ако је н мање од нуле, штампање и здраво вратите За све остале случајеве, Функција ће одштампати здраво и извршава рекурзивни позив. Још један позив на функцију хи са умањен улазна вредност. 

Сада, иако смо одштампали здраво, Функција неће прекинути док не врати своју повратни тип, у овом случају празнину. Дакле, за свако н осим основног случаја, ова функција хи хи ће се вратити н минус 1. Пошто је ова функција празнина ипак, ми неће експлицитно куцате повратак овде. Само ћемо извршити функцију. Дакле, позивајући хи (3) ће штампати и здраво извршава хи (2) који извршава хи (1) један који се извршава хи (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. 

Сада, видите да ли можете да спроведе рекурзивни функционишу сами. Убаците свој терминал, или рун.цс50.нет, и написати функцију Сум да узима целобројну н и враћа Збир свих узастопна позитивна цели бројеви од н до 1. Ја сам написао из суме неких вредности да вам помогну наш. Прво, схватите база случај стање. Затим, погледајте суме (5). Можете ли то да изрази у смислу другог суме? Сада, шта је са сумом (4)? Како можете изразити збир (4) у смислу другог збир? 

Када имате суму (5) и збир (4) изражене у односу на друге сумм, види ако можете да идентификујете образац за суму (н). Ако не, покушајте још неколико бројева и изражавају своје суме у Услови другим бројевима. Идентификацијом обрасце за дискретне бројеве, ви добро сте на путу ка идентификовање образац за било н. 

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

Рецимо да желите да извршите операцију на сваки чвор у бинарном стаблу. Како могу да идете о томе? Па, можете да напишете рекурзивна функција које обавља операцију на матичном чвору и чини рекурзивна позвати на исту функцију, пролази у лево и десно дете чворови. На пример, ова функција, фоо, то мења вредност датог чвора и све њене деце до 1. База случај нулл узрока чвора функција да се врати, што указује да не постоје чворови оставио у том под-стабло. 

Прошетајмо кроз њега. Први родитељ је 13. Ми промените вредност на 1, а затим позовите наша функција на лево, као и као право. Функција, трла, зове на левој суб-трее прво, па лево чвор ће бити премештен на 1. и ФОО ће бити позван на децу тог чвора, прво лево, а затим десно, и тако даље и тако даље. И реци им да немају гране било више деце тако исти процес ће се наставити за правим децу док чворови цело дрво су прекомандован у 1.. 

Као што можете да видите, ви се не ограничавају на само један рекурзивни позив. Баш колико ће добити посао. Шта ако сте имали дрво где сваки чвор је имао троје деце, Лево, средњи, и зар не? Како бисте уредили фоо? Па, једноставно. Само додајте још један рекурзивни позив и прође у показивач средини чвора. 

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

Хвала за гледање овај кратак. У најмању руку, сада можете разумем овакве вицеве. Моје име је Замила, а то је ЦС50. 

Узми ову функцију, здраво, воид функција која узима инт, н, као улаз. Основни случај долази прво. Ако је н мање од 0, штампа "Здраво" и повратак.