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