>> ZAMYLA: За да се разбере рекурсия, трябва
първо да разберем рекурсия.
Като рекурсия в програмни средства за проектиране че имате самостоятелно референтна
определения.
Рекурсивни структури от данни, например, са структури от данни, че
се включва в техните определения.
Но днес, ние ще се съсредоточи на рекурсивни функции.
>> Спомнете си, че функциите вземат входа, аргументи, и връща стойност като своя
изход представени от тази диаграма тук.
Ще мисля за кутията, тъй като тялото на функцията, съдържащ набор от
инструкции, които интерпретират вход и осигури изход.
Като погледнем по-отблизо в тялото на функцията може да разкрие повиквания към
други функции, както добре.
Вземете тази проста функция, Foo, че приема единствен низ като вход и
отпечатъци колко писма че има низ.
Strlen функцията за дължина низ, се нарича, чиято продукция е
необходима за поканата да ФОРМАТ.
>> Сега, това, което прави рекурсивно функция специален е, че той нарича себе си.
Ние може да представлява това рекурсивно наричаме с тази оранжева стрелка
примка обратно към себе си.
Но самото изпълнение отново само ще нов рекурсивно повикване и
друг и друг.
Но рекурсивни функции не може да бъде безкраен.
Те трябва да се свърши по някакъв начин, или си Програмата ще работи вечно.
>> Така че ние трябва да се намери начин да се прекъсне от рекурсивните повиквания.
Ние наричаме това базовия модел.
След като състоянието на база случай е изпълнено, функцията връща, без да прави
друг рекурсивно повикване.
Вземете тази функция, здравей, функция нищожен че отнема Int н като вход.
Базовата случай е на първо място.
Ако н е по-малко от нула, печат и чао за връщане за всички други случаи,
функция ще отпечата здрасти и изпълнение рекурсивни повикването.
Друг призив към функция хай с а декрементирани входна стойност.
>> Сега, макар и да отпечатате Здравейте, на функция няма да се прекрати, докато не
върне неговия вид завръщане, в този случай за невалидни.
Така за всеки п различни от базовата случай тази функция ще се върне здрасти здрасти
п минус 1.
Тъй като тази функция е невалидна обаче, ние няма да е изрично връщане тип тук.
Ние просто ще се изпълни функцията.
Така вика здрасти (3) ще отпечата здрасти и изпълни здрасти (2), който изпълнява здрасти (1) един
който изпълнява Hi (0), където състояние база случай е изпълнено.
Така здрасти (0) отпечатва сбогом и се връща.
>> OK.
Така че сега ние разбираме основите на рекурсивни функции, от които се нуждаят
най-малко една база случай, както и рекурсивно повикване, нека преминем към
по-смислен пример.
Едно, че не може просто да се върне анулира без значение какво.
>> Нека да разгледаме най-факториел операция се използва най-често в
вероятностни изчисления.
Повдигане на п е продукта на всеки положително число по-малко от
и равен на п.
Така факториел пет е 5 пъти 4 пъти 3 пъти два пъти 1 до получаване на 120.
Четири факториел е 4 пъти по 3 пъти 2 пъти 1 за да се получи 24.
И важи същото правило за всяко положително число.
>> Така че как може да се пише рекурсивно функция, която изчислява факториела
на номер?
Е, ние ще трябва да се идентифицират както в базов модел и рекурсивно повикване.
The рекурсивно повикване няма да бъде същият за всички случаи, с изключение на основата
случай, което означава, че ние ще трябва да намери модел, който ще ни даде нашата
желания резултат.
>> За този пример, вижте как 5 факториел включва умножаване 4 от 3 с 2 от 1
И същата тази умножение се намери тук, на
определение от 4 факториел.
Така ние виждаме, че 5 факториел е само 5 пъти 4 факториел.
Сега се прилага този модел до 4 факториел, както и?
Да.
Ние виждаме, че четири факториел съдържа умножение 3 пъти 2 пъти 1, на
същото определение като 3 факториел.
Така 4 факторен е равно на четири пъти 3 факториел, и така нататък и така нататък ни
модел се придържа до един факториел, което по дефиниция е равно на 1.
>> Няма друг положителен числа оставяли.
Така че ние имаме модел за нашата рекурсивно повикване.
п факторен е равна на N пъти факториела на п минус 1.
И нашата база случай?
Това просто ще бъде нашата дефиниция на един факториел.
>> Така че сега можем да преминем към писането код за функцията.
За основния случай, ние ще имаме състояние н равнява равни 1, където
ние ще се върне един.
Тогава се движи върху рекурсивно повикване, ние ще се върне н пъти
факторен п минус 1.
>> Сега нека да тествате това ни.
Нека се опитаме факториел 4.
Per нашата функция е равен 4 пъти факторен (3).
Повдигане (3) е равна на 3 пъти факторен (2).
Повдигане (2) е равна на два пъти факториел (1), която връща 1.
Повдигане (2) вече връща два пъти едно, две.
Повдигане (3), сега може да се върне 3 пъти 2, 6.
И накрая, факторен (4) връща 4 пъти 6, 24.
>> Ако сте се натъкват на всяка трудност с рекурсивно повикване, се преструвам, че
Функцията работи вече.
Какво искам да кажа от това е, че трябва да доверят вашите рекурсивни повиквания да се върне
правилните стойности.
Например, ако знам, че факторен (5) е равен на 5 пъти
факториел (4), аз отивам да се доверите, че факториел (4) ще ми даде 24.
Мислете за това като променлива, ако ще, като че ли вече е определен
факториел (4).
Така за всеки факторен (п), е продукта от п и
предходната факториел.
И това предишния факториел се получава чрез извикване
факторен п минус 1.
>> Сега, вижте, ако можете да се приложи рекурсивно функционира себе си.
Заредете вашия терминал, или run.cs50.net, и да напише функция сума
че се цяло число п и връща сума от всички последователни положителни
числа от N до 1.
Аз съм писал от сумите на някои стойности, за да ви помогне ни.
Първо, да разбера на състояние базов модел.
Виж тогава сума (5).
Можеш ли да го изразят по отношение от друга сума?
Сега, какво да кажем за сума (4)?
Как може да ви изразя сума (4) от гледна точка на друга сума?
>> След като имате сума (5) и сума (4) изразени по отношение на други суми, вижте
ако може да се идентифицира модел за сума (п).
Ако не, опитайте няколко други номера и да изразяват своите суми в
отношение на други номера.
Чрез идентифициране модели за дискретна номера, вие сте добре на вашия начин да се
определяне на модел за всяко п.
>> Рекурсия е много мощен инструмент, така че разбира се, че не е ограничен до
математически функции.
Рекурсия може да се използва много ефективно , когато се занимават с дървета например.
Напускане на краткосрочен по дърветата за по-обстоен преглед, но за сега
припомни, че двоични дървета за търсене, в специално се състои от възли, всеки
със стойност и две възел указатели.
Обикновено това се представлява от родител възел има една линия, сочеща
към лявата дете възел и един към дясната дете възел.
Структурата на двоично търсене дърво се поддава добре
да рекурсивно търсене.
The рекурсивно повикване или обходни пътища в лявата или дясната възел, но по-
на, че в краткосрочен дървото.
>> Да речем, че искате да се извърши дадена операция по всеки един възел в двоичен дърво.
Как може да отида за това?
Е, можете да напишете рекурсивно функция, която изпълнява операцията
на основния възел и прави рекурсивно зове към една и съща функция,
преминаване в ляво и правилните деца възли.
Например, тази функция, Фу, че променя стойността на даден възел и
всичко на децата си до едно.
Базовата случай на нулев причини възел функцията за връщане, което показва
че не са всички възли оставен в този под-дърво.
>> Да минеш през нея.
Първият родител е 13.
Ние променете стойността на един, и след това се обадете нашата функция в ляво, както и
както отдясно.
Функцията, Foo, се нарича в ляво под-дърво, на първо място, така че лявата възел
ще бъде преразпределено на една и Foo ще да се нарече на деца от тази възлова точка,
първо ляво и след това право, и така нататък и така нататък.
И да им кажа, че клонове, не разполагат с повече деца, така че един и същ процес
ще продължи за правото на децата възли, докато цялото дърво са
преназначен към 1.
>> Както можете да видите, че не са ограничени просто едно рекурсивно повикване.
Точно толкова, колкото ще се свърши работата.
Какво става, ако имаше едно дърво, където всеки възел имаше три деца,
Ляв, среден и десен?
Как бихте редактирате Foo?
Ами, просто.
Просто добавете друг рекурсивно повикване и премине в показалеца на средната възел.
>> Рекурсия е много мощен и не спомена елегантен, но тя може да бъде
трудно концепция в началото, така че да бъде търпеливи и да ви отнеме малко време.
Започнете с базовия модел.
Тя обикновено е най-лесно да се идентифицират, и след това можете да работите
назад от там.
Знаеш, че трябва да достигне своя базов модел, така че мощта
ви дам няколко съвета.
Опитайте се да изразя един конкретен случай в отношение на други случаи, или в подгрупи.
>> Благодаря за гледане на този кратък.
Най-малкото, сега можете да разбират вицове като този.
Моето име е Zamyla, и това е CS50.
>> Вземете тази функция, здрасти, а нищожен функция, която взима
едно цяло число, п, като вход.
Базовата случай е на първо място.
Ако н е по-малко от 0, печат "Чао" и връщане.