ДАГ Lloyd: Если вы видели видео на рекурсии, весь процесс может иметь Казалось немного волшебным. Как это работает? Как функционирует знают, что они нужно ждать и ждать другого значения вернуться из другой функции звоните, чтобы получить результат, который мы хотим? Ну, причина этого в том, что работает что-то известный как стек вызовов. Когда вы вызываете функцию, то Система выделяет пространство в памяти для этой функции, чтобы сделать свою работу. И мы называем эти куски памяти, создаются в сторону для каждой функции вызвать стека или функцию кадра. И, как вы могли бы ожидать, эти кадры стека жить на стеке части памяти. 

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

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

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

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

Так мы создаем новый кадр стека для основной. И это происходит, чтобы начать бег. Основные вызовы PRINTF. И Printf собирается распечатать факториала 5. Ну, он не знает, то, что факториал 5 является, и так этот вызов уже в зависимости от другого вызова функции. Так главный собирается приостановить прямо там. Я собираюсь оставить его стрелка вправо там, цвет это тот же цвет, как стек рамки справа, чтобы указать, что главная собирается заморозить здесь, а Факториал 5 называется. 

Так Факториал 5 называется. И это происходит, чтобы начать по крайней начиная от функции факториала. Это задает вопрос я равна 1? Есть 5 равно 1? Ну нет. Таким образом, это будет идти вниз, чтобы части иначе, возвращение в п раз Факториал N минус 1. Ладно. 

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

Так Факториал 4 начинается в начало факториала. Есть 4 равен 1? Нет, так он собирается сделать то же самое. Это собирается спуститься еще ветвь. Это происходит, чтобы добраться до этой строки кода. ОК, я собираюсь вернуться в четыре раза. О, Факториал 3-- так Факториал 4 зависит от факториала 3 отделки. 

И поэтому он должен позвонить факториал 3. И, что собирается пройти тот же самый процесс снова. Она начинается через, получает здесь. Факториал 3 зависит на факториала 1. Так Факториал 2 стартов, получает здесь. Это зависит от факториала 1. Факториал 1 стартов. 

ХОРОШО. Так что теперь, мы получаем где интересно, правда? Итак, 1 равен 1. И так мы возвращаемся 1. На данный момент, мы возвращаемся. Функция сделано. Это поведение is-- есть ничего еще для этого делать, и поэтому кадр стека для Факториал 1 появляется от. Закончено. 1 возвращается. А теперь, Факториал 2, что был кадра непосредственно под ним в стеке, становится активным кадра. 

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

Факториал 1 возвращается значение 1. Так Факториал 2 может скажем вернуть 2 раза 1. Его работа делается сейчас. Это вернулся от 2 до факториал 3, который был для него ждут. Факториал 3 теперь верхняя рама, активный кадр в стеке. И так он говорит, хорошо, хорошо, я собираюсь вернуться 3 раза 2, который 6. И я собираюсь дать, что значение обратно факториала 4, который ждал меня. Я задолбался. Факториал 3 появляется из стека, и Факториал 4 теперь активный кадр. 

4 говорит, хорошо, я собираюсь вернуться в 4 раза факториал 3, что было шесть лет. Это было ценное, что Факториал 3 возвращается. И так 4 раза 6 24. И я собираюсь пройти что вернуться к факториал 5, которая ждала меня. Факториал 5 в настоящее время активный кадр. Это собирается вернуться в 5 раз Факториал 4-- 5 раз 24 или 120-- и дать, что значение на главную, которая имеет ждали очень терпеливо для долгое время в нижней части стопки. 

Это место, где она началась. Он сделал этот вызов. Несколько кадров взял на себя сверху. Теперь обратно на вершине стека. Это активный кадр. Так главный получили значение 120 назад от факториала 5. Это было ждать, чтобы распечатать эту величину. А потом это делается. Там нет больше строк кода в основной. Так каркас Главное выскакивает от стек, и мы сделали. 

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

Я Дуг Ллойд. Это CS50.