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