[Играет музыка] 

ДАГ Lloyd: Вы, наверное, думаете, что Код используется только для выполнения задачи. Вы пишете это. Это что-то делает. Это довольно много его. 

Вы скомпилировать его. Вы запускаете программу. Вы хорошо идти. 

Но верить этому или нет, если вы код в течение длительного времени, вы на самом деле может прийти, чтобы увидеть Код, как что-то, что красиво. Это решает проблему в очень интересный способ, или есть что-то действительно аккуратный о том, как он выглядит. Вы можете смеяться на меня, но это правда. И рекурсия является одним из способов к виду эта идея красивая, элегантная, глядя код. Это решает проблемы таким образом, что интересны, легко визуализировать, и удивительно коротким. 

Пути рекурсии работы есть, рекурсивная функция определяется как функция, которая вызывает себя как части его исполнения. Это может показаться немного странным, и мы увидим немного о том, как это работает в настоящее время. Но опять же, это рекурсивные процедуры будет так элегантный потому что они собираются чтобы решить эту проблему без имея все эти и другие функции или эти длинные петли. Вы увидите, что это рекурсивная процедуры будет выглядеть так коротка. И они действительно намерены сделать код выглядеть намного красивее. 

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

Так 5 факториала 5 раз 4 раза 3 раза 2 раза 1. И 4 факториал 4 раза 3 раза 2 раза 1 и так далее. Вы получаете идею. 

Как программисты, мы не использовать п, восклицательный знак. Так мы определим факториал Функция как факт п. И мы будем использовать для создания факториала рекурсивный решение проблемы. И я думаю, вы могли бы найти что это намного более визуально привлекательным, чем итеративный версия этого котором мы также взглянем на в один момент. 

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

Но, глядя на это, не так ли это? Не Факториал 2 раз 2 раза Факториал 1? Я имею в виду, факториал 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. 

Что рекурсивный Дело, вероятно, выглядеть? Для каждого другой номер кроме 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. 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.