ZAMYLA: Со цел да се разбере рекурзија, мора прво да се разбере рекурзија. Има рекурзија во програмата дизајн значи дека имате авто-референтен дефиниции. Рекурзивен структури на податоци, на пример, се структури на податоци кои вклучуваат себеси во нивните дефиниции. Но, денес, ние ќе треба да се фокусираат на рекурзивен функции. 

Потсетиме дека функциите се влезови, аргументи, и се врати на вредност како и нивните излез претставен со овој дијаграм тука. Ќе размислиме од кутијата како орган на функцијата, содржи множество на инструкциите кои ги толкуваат влез и да се обезбеди излез. Земајќи го одблизу во внатрешноста на телото на функцијата може да се открие повици кон други функции, како и. Искористам оваа едноставна функција, foo, дека зема една низа како влез и отпечатоци како многу писма стрингот има. Функцијата strlen, за стринг должина, се нарекува, чиј излез е потребни за повик за printf. 

Сега, она што го прави рекурзивен функција посебен е тоа што се нарекува себеси. Ние можеме да ја претставува оваа рекурзивен повик со оваа портокалова стрелка looping назад кон себе. Но извршување себе повторно само ќе направи уште еден рекурзивен повик, и друг и друг. Но рекурзивен функции не може да биде бесконечна. Тие треба да се стави крај некако, или вашиот програма ќе се кандидира засекогаш. 

Значи ние треба да се најде начин да се скрши надвор од рекурзивните повици. Ние го нарекуваме овој основното сценарио. Кога состојбата база случај е исполнет, функцијата враќа без да се прави друг рекурзивен повик. Искористам оваа функција, здраво, празнина функција дека зема int n како влез. Основното сценарио се случи прво. Ако n е помала од нула, печатење поздрават и пријава за сите други случаи, функција ќе печати Здраво и изврши рекурзивен повик. Уште еден повик до функцијата hi со на decremented влезна вредност. 

Сега, иако ние печати Здраво, на функција нема да прекине додека не се врати нејзиното враќање тип, во овој случај неважечки. Значи за секој n освен база случај, оваа функција hi ќе се врати hi- на n минус 1. Од оваа функција не е правосилен, иако, ние нема експлицитно тип враќање тука. Ние само ќе се изврши функцијата. Па повикувајќи hi (3) ќе се печати Здраво и изврши hi (2), кој извршува hi (1) еден , кој извршува hi (0), каде што база случај услов е исполнет. Па hi (0) отпечатоци поздрават и се враќа. 

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

Ајде да ги разгледаме во факториел операција се користи најчесто во веројатност пресметки. Фактор од n е производ на сите позитивен цел број помалку од и еднаков на n. Па факториел пет е 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. 

Нема други позитивни броеви лево. Па ние имаме моделот за нашите рекурзивен повик. n факторен е еднаква на n пати факториел од n минус 1. И нашата база случај? Дека само ќе биде нашата дефиниција од 1 факториел. 

Па сега можеме да се движи кон пишување код за функција. За база случај, ќе имаме состојба n еднаква еднакво на 1, каде што ние ќе се врати 1. Потоа се движи кон рекурзивен повик, ние ќе се вратат n пати факториел од n минус 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). Значи за секој факториел (n), тоа е производ на n и претходната факториел. И ова претходната факториел се добива со повик факториел од n минус 1. 

Сега, види дали може да се спроведе рекурзивен себе функционираат. Вчита до вашиот терминал, или run.cs50.net, и напишете функција Збирот кој ги зема цел број n и се враќа на Збирот на сите последователни позитивни броеви од n 1. Јас го напишав надвор суми на некои вредности да ви помогне на нашите. Прво, дознаам база случај состојба. Потоа, погледнете сума (5). Може да ви го изразиме во однос на друга сума? Сега, она што за сума (4)? Како може да се изразат сума (4) во однос на друга сума? 

Откако ќе имаат сума (5) и збирот (4) изразена во смисла на други суми, видете ако може да се идентификуваат модел за сума (n). Ако не, се обиде на неколку други броеви и да ги изразат нивните суми во однос на друг број. Со идентификување на шеми за дискретни броеви, вие многу добро на вашиот начин на идентификување на моделот за било n. 

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

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

Ајде да одиме низ него. Првиот родител е 13. Ние промена на вредноста на 1, и потоа побарајте нашата функција на левата, како и како право. Функцијата, foo, се нарекува на левата под-дрво прво, па на лево јазол ќе бидат прераспоредени на 1 и foo ќе бидат повикани деца кои јазол, Првиот левата, а потоа десната, и така натаму и така натаму. И да им каже дека гранки немаат повеќе деца, па истиот процес ќе продолжи за правата на децата до јазли целото дрво се прераспоредени на 1. 

Како што можете да видите, не сте ограничени на само еден рекурзивен повик. Само толку, колку што ќе одам на работа. Што ако сте имале дрво каде секој јазол имаше три деца, Лево, средината, и нели? Како ќе се променат foo? Добро, едноставна. Едноставно додадете друг рекурзивен повик и помине во средината јазол покажувачот на. 

Рекурзијата е многу моќен и да не се спомене домот, но тоа може да биде тешко концепт на прв, па да биде пациентот и не брзајте. Започнете со основното сценарио. Тоа е обично најлесно да се идентификуваат, а потоа можете да работите наназад од таму. Знаеш дека треба да стигнат до својата база случај, така што би можеле да ви даде неколку совети. Се обиде да го изразат на еден специфичен случај во однос на други случаи, или во под-групи. 

Ви благодариме за гледање овој краток. Во најмала рака, сега може да се се разбере шеги вака. Моето име е Zamyla, а тоа е cs50. 

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