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