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 рази 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