[Грає музика] 

ДАГ Lloyd: Ви, напевно, думаєте, що Код використовується тільки для виконання завдання. Ви пишете це. Це щось робить. Це досить багато його. 

Ви скомпілювати його. Ви запускаєте програму. Ви добре йти. 

Але вірити цьому чи ні, якщо ви код протягом тривалого часу, ви насправді може прийти, щоб побачити Код, як щось, що красиво. Це вирішує проблему в дуже цікавий спосіб, або є щось дійсно акуратний про те, як він виглядає. Ви можете сміятися на мене, але це правда. І рекурсія є одним із способів до виду ця ідея красива, елегантна, дивлячись код. Це вирішує проблеми таким чином, що цікаві, легко візуалізувати, і дивно коротким. 

Шляхи рекурсії роботи Тобто, рекурсивна функція визначається як функція, яка викликає себе як частини його виконання. Це може здатися трохи дивним, і ми побачимо трохи про те, як це працює в даний час. Але знову ж, це рекурсивні процедури буде так елегантний тому що вони збираються щоб вирішити цю проблему без маючи всі ці та інші функції або ці довгі петлі. Ви побачите, що це рекурсивна процедури буде виглядати так коротке. І вони дійсно мають намір зробити код виглядати набагато красивіше. 

Я дам вам приклад це подивитися, як рекурсивна процедура може бути визначена. Так що, якщо ви знайомі з цим від математичному класі багато років тому, там щось називається Функція факторіала, які, як правило, позначається як знаком оклику, який визначена над всіх позитивних цілих чисел. І те, н факторіал обчислюється це ви помножити все число менше, ніж або дорівнює п together-- всі цілі менше, ніж або дорівнює п разом. 

Так 5 факторіала 5 раз 4 рази 3 рази 2 рази 1. І 4 факторіал 4 рази 3 рази 2 рази 1 і так далі. Ви отримуєте ідею. 

Як програмісти, ми не використовувати п, знак оклику. Так ми визначимо факторіал Функція як факт п. І ми будемо використовувати для створення факторіала рекурсивний рішення проблеми. І я думаю, ви могли б знайти що це набагато більш візуально привабливим, ніж ітеративний версія цього якому ми також поглянемо на в один момент. 

Так от пару facts-- каламбур intended-- про factorial-- факторіала. Факторіал 1, як я сказав, це 1. Факторіал 2 в 2 рази 1. Факторіал 3 березня рази 2 рази 1, і так далі. Ми говорили про 4 і 5 вже. 

Але, дивлячись на це, чи не так це? Чи не Факторіал 2 раз 2 рази Факторіал 1? Я маю на увазі, факторіал 1 січня. Так чому ми не можемо просто сказати, що, так Факторіал 2 в 2 рази 1, це дійсно всього 2 рази факторіал 1? 

А потім поширити цю ідею, НЕ Факторіал 3 всього 3 рази Факторіал 2? І Факторіал 4 в 4 рази факторіал 3, і так далі? Насправді, факторний з будь-якого числа можна просто бути виражено, якщо ми якось з виконати це назавжди. Ми можемо узагальнити вид факторний проблема як це п раз в Факторіал N мінус 1. Це п раз продукт всі номери менше, ніж мені. 

Ця ідея, це Узагальнення завдання, дозволяє рекурсивно визначити функцію факторіала. Коли ви визначаєте функцію рекурсивно, є дві речі, які повинні бути частиною цього. Ви повинні мати щось, зване базовий випадок, який, коли ви запускаєте його, буде зупинити процес рекурсивного. 

В іншому випадку, функція, яка викликає в тому: як ви могли imagine-- може тривати вічно. Функція викликає функцію називає виклики функцій функція викликає функцію. Якщо ви не є спосіб , Щоб зупинити його, вашу програму буде ефективно застряг у нескінченному циклі. Це призведе до краху в кінці кінців, тому що він буде працювати з пам'яті. Але це до справи не відноситься. 

Ми повинні мати інший спосіб, щоб зупинити речі, крім нашої програми розбиваючи, тому що програма, яка розбиває це ймовірно, не красиво чи елегантно. І так ми називаємо це базовий варіант. Це просте рішення до проблеми, який зупиняється рекурсивний процес виникнення. Так от одна частина рекурсивна функція. 

Друга частина рекурсивний випадок. І це, де рекурсія насправді відбувається. Це те, де функція називати себе. 

Це не буде називати себе точно так само, як його називали. Це буде невелика зміна що робить проблему це намагається вирішити маленький трохи менше. Але це, як правило проходить долар рішення більшу частину розчину на інший виклик по лінії. 

Який з цих поглядів як базового випадку тут? Який з цих виглядає як просте рішення проблеми? У нас є купа факториалов, і ми могли б продовжувати відбувається on-- 6, 7, 8, 9, 10 і так далі. 

Але один з цих виглядає як хороший випадок, щоб бути базовим сценарієм. Це дуже просте рішення. Ми не повинні робити нічого особливого. 

Факторіал 1 знаходиться всього в 1. Ми не повинні робити нічого множення на всіх. Схоже, якщо ми збираємося щоб спробувати вирішити цю проблему, і ми повинні зупинити Рекурсія де-небудь, ми, ймовірно, хочете, щоб зупинити це коли ми отримуємо до 1. Ми не хочемо, щоб зупинити раніше. 

Так що, якщо ми визначаємо наш факторіала, от каркас для як ми могли б це зробити. Ми повинні підключити в цих двох things-- базовий варіант і рекурсивний випадок. Що базовий варіант? Якщо п одно 1, повернутися 1-- це дійсно проста задача вирішити. 

Факторіал 1 січня. Це не 1 раз нічого. Це просто 1. Це дуже просто факт. І так, що може бути нашим базовим сценарієм. Якщо нас пройшло 1 в цьому Функція, ми просто повертає 1. 

Що рекурсивний Справа, ймовірно, виглядати? Для кожного інший номер крім 1, що картина? Ну, якщо ми беремо факторіал N, Це п раз факторіал N мінус 1. 

Якщо ми беремо факторіала з 3, це в 3 рази Факторіал 3 мінус 1, або 2. І тому, якщо ми не дивлячись на 1, інакше Повернення в п раз Факторіал N мінус 1. Це досить просто. 

І заради наявності трохи чистіше і більш елегантний код, знаю, що якщо у нас є петлі однорядкових або однорядковий умовні гілки, ми можемо позбутися всіх з Фігурні дужки навколо них. Таким чином, ми можемо об'єднати це з цим. Це точно так само, Функціональність, як цей. 

Я просто забираючи кучеряве дужки, тому що є тільки одна лінія всередині цих умовних гілок. Таким чином, ці поводяться однаково. Якщо п одно 1, повертає 1. В іншому випадку повернути п раз факторіал N мінус 1. Таким чином, ми робимо проблему менше. Якщо п починається як 5, ми збираємося повернутися 5 раз факторіал 4. І ми побачимо в хвилину, коли ми говоримо про stack-- виклику в іншому відео де ми говоримо про зателефонувати stack-- ми дізнаємося про те, чому саме цей процес працює. 

Але в той час Факторіал 5 говорить повернутися в 5 разів факторіал 4, і 4 буде казати, добре, добре, повернення 4 рази Факторіал 3. І, як ви бачите, ми роду наближається до 1. Ми все ближче і ближче до цієї базової випадку. 

І як тільки ми потрапили в базовий варіант, всі попередні функції є відповідь, яку вони шукали. Факторіал 2 говорив повернення 2 рази Факторіал 1. Ну, факторний 1 повертається 1. Таким чином, заклик до факторіала 2 може повернутися в 2 рази 1, і дати, що спиною до факторіала 3, який чекав цього результату. 

І тоді він може розраховувати його результат, 3 разу 2 6, і віддати його факторіала 4. І знову, у нас є відео в стеку викликів де це показано трохи більше, ніж те, що я говорю зараз. Але це він. Це саме по собі рішення розрахунку факторіала числа. 

Це тільки чотири рядки коду. Це дуже здорово, чи не так? Це свого роду сексуальний. 

Таким чином, загалом, але не завжди, рекурсивна функція може замінити циклу в нерекурсивний функція. Так от, поруч, це ітераційний версія функції факторіалу. Обидва ці Статистика рівно те ж саме. 

Вони обидва розрахунки факторіала п. Версія зліва використовує рекурсію, щоб зробити це. Версія про право використовує ітерацію, щоб зробити це. 

І зауважте, ми повинні оголосити змінна цілий твір. І тоді ми петля. Поки п більше, ніж 0, то розмножуватися, що продукт за п і не зменшуючи п до ми обчислити добуток. Таким чином, ці дві функції, знову ж, зробити те ж саме. Але вони не роблять це в точно таким же чином. 

Тепер можна більш ніж одну базу так, або більш ніж один Рекурсивний випадок, залежно на що ваша функція намагається зробити. Ви не обов'язково обмежується тільки один базовий випадок або один рекурсивний випадок. Так що приклад чогось з безліччю базових випадках може бути this-- Фібоначчі порядковий номер. 

Ви можете згадати з елементарні шкільні дні що послідовність Фібоначчі визначається як this-- перший елемент 0. Другим елементом є 1. Обидва з них є просто за визначенням. 

Тоді кожен елемент визначається у вигляді суми п мінус 1 і мінус 2 н. Так третього елемента буде 0 + 1 = 1. А потім четвертий елемент буде другий елемент, 1, плюс третій елемент, 1. І, що б 2. І так далі, і так далі. 

Таким чином, в цьому випадку, у нас є два базових випадків. Якщо п одно 1, повернути 0. Якщо п одно 2, повертає 1. В іншому випадку, повернення Фібоначчі п мінус 1 плюс Фібоначчі п мінус 2. 

Так ось кілька базових випадків. Що про декілька випадків рекурсивних? Ну, є дещо називається гіпотеза Коллатц. Я не збираюся говорити, Ви знаєте, що це таке, бо це насправді наш останній Проблема для даного відео. І це наша вправи працювати разом. 

Так ось те, що Коллатц гіпотеза is-- це відноситься до будь-якого натурального. І це передбачає, що це завжди можна повернутися 1, якщо ви виконаєте наступні дії. Якщо п = 1, зупинитися. Ми повернулися до 1, якщо п = 1. 

В іншому випадку, пройти через це Процес знову на п ділиться на 2. І подивитися, якщо ви можете отримати назад до 1. В іншому випадку, якщо п нечетно, пройти цей процес знову на 3n плюс 1, або 3 рази N плюс 1. Так от у нас є один базовий варіант. Якщо п одно 1, зупинитися. Ми не робимо більше рекурсію. 

Але у нас є два рекурсивних справ. Якщо п парне, ми робимо одну рекурсивної Справа, називаючи п ділиться на 2. Якщо п нечетно, ми робимо різні рекурсивна справу за 3 рази п плюс 1. 

І тому мета цього відео прийняти секунди, пауза відео, і спробувати написати це рекурсивна функція Коллатц де ви проходите в значенні п, і він розраховує, скільки кроків потрібно, щоб отримати 1, якщо ви починаєте з п і ви будете слідувати ці кроки нагорі. Якщо п = 1, він вживає заходів 0. В іншому випадку, це буде один крок плюс проте багато кроків він бере на будь-якому п ділиться на 2, якщо п парне, або 3n + 1 якщо п непарній. 

Тепер, я поклав на екрані тут пару тестових речей для вас, пару тестових варіантів для вас, щоб побачити те, що ці різні номери Collatz є, а також ілюстрація про кроки, які потрібно пережити, щоб ви могли начебто розглядають цей процес в дії. Таким чином, якщо п одно 1, Коллатц п 0. Ви не повинні робити нічого, щоб повернутися до 1. Ви вже там. 

Якщо п 2, він займає один крок, щоб дістатися до 1. Ви починаєте з 2. Добре, 2 не дорівнює 1. Таким чином, це буде один крок плюс, проте багато кроки, які він бере на п ділиться на 2. 

2 ділиться на 2 січня. Так він приймає один крок плюс проте багато кроків потрібно для 1. 1 займає нульові кроки. 

Для 3, як ви можете бачити, є участь чимало кроків. Ви йдете від 3. І тоді ви йдете в 10, 5, 16, 8, 4, 2, 1. Це займе сім кроків, щоб повернутися до 1. І, як ви бачите, є кілька інших випадків тут випробувань щоб перевірити вашу програму. Отже, ще раз, пауза відео. І я піду стрибати назад тепер те, що сам процес тут, те, що ця гіпотеза. 

Дивіться, якщо ви можете з'ясувати, як визначити Collatz п таким чином, що він підраховує, скільки кроки потрібно, щоб отримати 1. Так, ми сподіваємося, ви паузу відео і ви не просто чекає мене щоб дати вам відповідь тут. Але якщо ви, ну, ось відповідь в будь-якому випадку. 

Так от можливий визначення функції Collatz. Наша база case--, якщо п дорівнює 1, ми повертаємося 0. Це не приймати будь-які кроки, щоб повернутися до 1. 

В іншому випадку, у нас є два рекурсивний cases-- одним для парних чисел і один для непарних. Як я перевірити парних чисел щоб перевірити, якщо п по модулю 2 дорівнює 0. Це, в основному, знову ж, задаючи питання, якщо згадати, що мод is-- якщо я розділяй п на 2 не існує ніякого залишку? Це було б парне число. 

І так, якщо п по модулю 2 дорівнює 0 Тестування це парне число. Якщо це так, я хочу, щоб повернути 1, тому що це, безумовно, один крок плюс Collatz з всі число половина мене. В іншому випадку, я хочу, щоб повернути 1 плюс Коллатц 3 рази N плюс 1. Це був інший рекурсивний крок, який ми могли б зробити для розрахунку Collatz-- кількість кроків він приймає, щоб повернутися 1 присвоєно номер. Так, ми сподіваємося, цей приклад дав вам трохи з смаку рекурсивних процедур. Сподіваюся, ви думаєте, код трохи більш гарним, якщо реалізовані в елегантному рекурсивним чином. Але навіть якщо ні, рекурсія є справді потужний інструмент, тим не менш. І так що це безумовно щось щоб отримати свою голову навколо, тому що ви будете в змозі створити Досить прохолодно, що використовують рекурсію програми які могли б бути складним, щоб написати якщо ви використовуєте петель і ітерації. Я Дуг Ллойд. Це CS50.