1 00:00:00,000 --> 00:00:05,587 2 00:00:05,587 --> 00:00:07,670 ДАГ Lloyd: Если вы видели видео на рекурсии, 3 00:00:07,670 --> 00:00:10,170 весь процесс может иметь Казалось немного волшебным. 4 00:00:10,170 --> 00:00:10,930 Как это работает? 5 00:00:10,930 --> 00:00:15,010 Как функционирует знают, что они нужно ждать и ждать другого значения 6 00:00:15,010 --> 00:00:19,150 вернуться из другой функции звоните, чтобы получить результат, который мы хотим? 7 00:00:19,150 --> 00:00:22,550 >> Ну, причина этого в том, что работает что-то известный как стек вызовов. 8 00:00:22,550 --> 00:00:26,360 Когда вы вызываете функцию, то Система выделяет пространство в памяти 9 00:00:26,360 --> 00:00:28,120 для этой функции, чтобы сделать свою работу. 10 00:00:28,120 --> 00:00:31,720 И мы называем эти куски памяти, создаются в сторону для каждой функции 11 00:00:31,720 --> 00:00:35,670 вызвать стека или функцию кадра. 12 00:00:35,670 --> 00:00:38,290 И, как вы могли бы ожидать, эти кадры стека 13 00:00:38,290 --> 00:00:41,000 жить на стеке части памяти. 14 00:00:41,000 --> 00:00:43,960 15 00:00:43,960 --> 00:00:47,540 >> Более чем одну функцию фрейм стека может существовать в памяти в данный момент времени. 16 00:00:47,540 --> 00:00:51,240 Если основной вызывает функцию шаг, и шаг вызывает направление, 17 00:00:51,240 --> 00:00:54,460 все три функции имеют открытые рамки. 18 00:00:54,460 --> 00:00:57,350 Но не все они имеют активные кадры. 19 00:00:57,350 --> 00:00:59,410 Эти кадры расположены в стеке. 20 00:00:59,410 --> 00:01:01,820 И кадр из недавно назвал 21 00:01:01,820 --> 00:01:04,390 Функция всегда на вершине стека. 22 00:01:04,390 --> 00:01:07,150 И это всегда активный кадр. 23 00:01:07,150 --> 00:01:10,420 Там только действительно когда-либо одним функция, активен одновременно. 24 00:01:10,420 --> 00:01:12,420 Это один на вершине стека. 25 00:01:12,420 --> 00:01:17,620 >> Когда функция вызывает другую Функция, он вроде нажимает паузу. 26 00:01:17,620 --> 00:01:20,590 Это своего рода находится на удержании, ожидая. 27 00:01:20,590 --> 00:01:24,050 И еще фрейм стека выталкивается стек поверх него. 28 00:01:24,050 --> 00:01:26,150 И, что становится активным кадра. 29 00:01:26,150 --> 00:01:28,600 И кадр сразу Ниже он должен ждать 30 00:01:28,600 --> 00:01:33,560 до тех пор, пока снова активный кадр прежде чем он может возобновить свою работу. 31 00:01:33,560 --> 00:01:35,870 Когда функция полное и это будет сделано, 32 00:01:35,870 --> 00:01:37,720 его кадр из стека. 33 00:01:37,720 --> 00:01:38,950 Это терминология. 34 00:01:38,950 --> 00:01:41,110 И кадр сразу под ним, как я только что сказал 35 00:01:41,110 --> 00:01:42,880 становится новым активный кадр. 36 00:01:42,880 --> 00:01:45,960 >> А если она вызывает другую функцию, он собирается приостановить снова. 37 00:01:45,960 --> 00:01:49,290 Фрейм стека, что новые функции будет быть помещается в вершине стека. 38 00:01:49,290 --> 00:01:50,650 Это будет делать свою работу. 39 00:01:50,650 --> 00:01:52,100 Это может поп отступить. 40 00:01:52,100 --> 00:01:55,630 И другие функции Ниже можно возобновить снова. 41 00:01:55,630 --> 00:02:00,080 >> Итак, давайте пройти через это снова, глядя на идее функции факториала 42 00:02:00,080 --> 00:02:03,070 что мы определены в рекурсия видео, чтобы увидеть 43 00:02:03,070 --> 00:02:07,770 точно, как магия за этим рекурсивный процесс происходит. 44 00:02:07,770 --> 00:02:09,870 Так что это все наш файл, верно? 45 00:02:09,870 --> 00:02:14,000 Мы определили два functions-- основной и факт. 46 00:02:14,000 --> 00:02:15,980 И, как мы могли бы ожидать, любая программа С происходит 47 00:02:15,980 --> 00:02:18,470 чтобы начать на первой линии главной. 48 00:02:18,470 --> 00:02:21,660 >> Так мы создаем новый кадр стека для основной. 49 00:02:21,660 --> 00:02:23,320 И это происходит, чтобы начать бег. 50 00:02:23,320 --> 00:02:25,270 Основные вызовы PRINTF. 51 00:02:25,270 --> 00:02:29,390 И Printf собирается распечатать факториала 5. 52 00:02:29,390 --> 00:02:31,440 Ну, он не знает, то, что факториал 5 является, 53 00:02:31,440 --> 00:02:35,620 и так этот вызов уже в зависимости от другого вызова функции. 54 00:02:35,620 --> 00:02:37,270 Так главный собирается приостановить прямо там. 55 00:02:37,270 --> 00:02:39,103 Я собираюсь оставить его стрелка вправо там, цвет 56 00:02:39,103 --> 00:02:41,360 это тот же цвет, как стек рамки справа, 57 00:02:41,360 --> 00:02:47,720 чтобы указать, что главная собирается заморозить здесь, а Факториал 5 называется. 58 00:02:47,720 --> 00:02:49,300 >> Так Факториал 5 называется. 59 00:02:49,300 --> 00:02:53,160 И это происходит, чтобы начать по крайней начиная от функции факториала. 60 00:02:53,160 --> 00:02:55,440 Это задает вопрос я равна 1? 61 00:02:55,440 --> 00:02:56,810 Есть 5 равно 1? 62 00:02:56,810 --> 00:02:57,410 Ну нет. 63 00:02:57,410 --> 00:03:01,110 Таким образом, это будет идти вниз, чтобы части иначе, возвращение в п раз 64 00:03:01,110 --> 00:03:02,990 Факториал N минус 1. 65 00:03:02,990 --> 00:03:03,490 Ладно. 66 00:03:03,490 --> 00:03:07,070 >> Так что теперь, Факториал 5 является в зависимости от другой вызов 67 00:03:07,070 --> 00:03:09,740 чтобы факториал, проходя в 4 в качестве параметра. 68 00:03:09,740 --> 00:03:14,210 И так факториал 5 кадров, что красной рамкой, 69 00:03:14,210 --> 00:03:17,160 собирается заморозить тут на этой линии я указал 70 00:03:17,160 --> 00:03:21,914 и ждать факториала от 4 до завершения то, что нужно сделать так, чтобы потом его 71 00:03:21,914 --> 00:03:23,330 может стать активную рамку снова. 72 00:03:23,330 --> 00:03:26,890 >> Так Факториал 4 начинается в начало факториала. 73 00:03:26,890 --> 00:03:28,556 Есть 4 равен 1? 74 00:03:28,556 --> 00:03:30,180 Нет, так он собирается сделать то же самое. 75 00:03:30,180 --> 00:03:31,590 Это собирается спуститься еще ветвь. 76 00:03:31,590 --> 00:03:33,240 Это происходит, чтобы добраться до этой строки кода. 77 00:03:33,240 --> 00:03:35,710 ОК, я собираюсь вернуться в четыре раза. 78 00:03:35,710 --> 00:03:41,270 О, Факториал 3-- так Факториал 4 зависит от факториала 3 отделки. 79 00:03:41,270 --> 00:03:43,055 >> И поэтому он должен позвонить факториал 3. 80 00:03:43,055 --> 00:03:45,180 И, что собирается пройти тот же самый процесс снова. 81 00:03:45,180 --> 00:03:48,200 Она начинается через, получает здесь. 82 00:03:48,200 --> 00:03:50,980 Факториал 3 зависит на факториала 1. 83 00:03:50,980 --> 00:03:53,750 Так Факториал 2 стартов, получает здесь. 84 00:03:53,750 --> 00:03:56,310 Это зависит от факториала 1. 85 00:03:56,310 --> 00:03:57,430 Факториал 1 стартов. 86 00:03:57,430 --> 00:03:57,650 >> ХОРОШО. 87 00:03:57,650 --> 00:03:59,775 Так что теперь, мы получаем где интересно, правда? 88 00:03:59,775 --> 00:04:02,190 Итак, 1 равен 1. 89 00:04:02,190 --> 00:04:05,130 И так мы возвращаемся 1. 90 00:04:05,130 --> 00:04:06,770 На данный момент, мы возвращаемся. 91 00:04:06,770 --> 00:04:07,880 Функция сделано. 92 00:04:07,880 --> 00:04:11,140 Это поведение is-- есть ничего еще для этого делать, 93 00:04:11,140 --> 00:04:17,006 и поэтому кадр стека для Факториал 1 появляется от. 94 00:04:17,006 --> 00:04:17,589 Закончено. 95 00:04:17,589 --> 00:04:19,480 1 возвращается. 96 00:04:19,480 --> 00:04:23,370 А теперь, Факториал 2, что был кадра непосредственно под ним 97 00:04:23,370 --> 00:04:26,160 в стеке, становится активным кадра. 98 00:04:26,160 --> 00:04:29,030 >> И это может подобрать где именно остановились. 99 00:04:29,030 --> 00:04:32,240 Это ждали факториала 1, чтобы закончить свою работу. 100 00:04:32,240 --> 00:04:33,610 В настоящее время закончена. 101 00:04:33,610 --> 00:04:35,510 И вот мы здесь. 102 00:04:35,510 --> 00:04:38,080 >> Факториал 1 возвращается значение 1. 103 00:04:38,080 --> 00:04:42,430 Так Факториал 2 может скажем вернуть 2 раза 1. 104 00:04:42,430 --> 00:04:43,680 Его работа делается сейчас. 105 00:04:43,680 --> 00:04:49,110 Это вернулся от 2 до факториал 3, который был для него ждут. 106 00:04:49,110 --> 00:04:53,370 Факториал 3 теперь верхняя рама, активный кадр в стеке. 107 00:04:53,370 --> 00:04:58,617 И так он говорит, хорошо, хорошо, я собираюсь вернуться 3 раза 2, который 6. 108 00:04:58,617 --> 00:05:00,700 И я собираюсь дать, что значение обратно факториала 109 00:05:00,700 --> 00:05:03,430 4, который ждал меня. 110 00:05:03,430 --> 00:05:04,500 Я задолбался. 111 00:05:04,500 --> 00:05:09,410 Факториал 3 появляется из стека, и Факториал 4 теперь активный кадр. 112 00:05:09,410 --> 00:05:13,510 >> 4 говорит, хорошо, я собираюсь вернуться в 4 раза факториал 3, что было шесть лет. 113 00:05:13,510 --> 00:05:15,980 Это было ценное, что Факториал 3 возвращается. 114 00:05:15,980 --> 00:05:19,010 И так 4 раза 6 24. 115 00:05:19,010 --> 00:05:20,990 И я собираюсь пройти что вернуться к факториал 116 00:05:20,990 --> 00:05:23,160 5, которая ждала меня. 117 00:05:23,160 --> 00:05:25,270 Факториал 5 в настоящее время активный кадр. 118 00:05:25,270 --> 00:05:30,700 Это собирается вернуться в 5 раз Факториал 4-- 5 раз 24 или 120-- 119 00:05:30,700 --> 00:05:32,722 и дать, что значение на главную, которая имеет 120 00:05:32,722 --> 00:05:35,680 ждали очень терпеливо для долгое время в нижней части стопки. 121 00:05:35,680 --> 00:05:36,640 >> Это место, где она началась. 122 00:05:36,640 --> 00:05:37,670 Он сделал этот вызов. 123 00:05:37,670 --> 00:05:39,400 Несколько кадров взял на себя сверху. 124 00:05:39,400 --> 00:05:41,890 Теперь обратно на вершине стека. 125 00:05:41,890 --> 00:05:43,450 Это активный кадр. 126 00:05:43,450 --> 00:05:47,810 Так главный получили значение 120 назад от факториала 5. 127 00:05:47,810 --> 00:05:50,750 Это было ждать, чтобы распечатать эту величину. 128 00:05:50,750 --> 00:05:51,657 А потом это делается. 129 00:05:51,657 --> 00:05:53,240 Там нет больше строк кода в основной. 130 00:05:53,240 --> 00:05:56,800 Так каркас Главное выскакивает от стек, и мы сделали. 131 00:05:56,800 --> 00:05:58,992 >> И вот как работает рекурсия. 132 00:05:58,992 --> 00:06:00,200 Вот как кадры стека работать. 133 00:06:00,200 --> 00:06:03,120 Эти вызовы функций что произошло ранее 134 00:06:03,120 --> 00:06:06,620 просто на паузу, ожидая для последующих вызовов 135 00:06:06,620 --> 00:06:12,050 до конца, чтобы они могли стать активным кадр и закончить то, что они должны делать. 136 00:06:12,050 --> 00:06:13,060 >> Я Дуг Ллойд. 137 00:06:13,060 --> 00:06:14,880 Это CS50. 138 00:06:14,880 --> 00:06:16,580