1
00:00:00,000 --> 00:00:05,587

2
00:00:05,587 --> 00:00:07,670
Даг Ллоид: Ако сте видели
видео на рекурзије,

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
Дефинисан смо два
фунцтионс-- главни и чињеница.

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
Главни позиви принтф.

51
00:02:25,270 --> 00:02:29,390
И иф ће
одштампате факторијел 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
Pa ne.

63
00:02:57,410 --> 00:03:01,110
Тако да ће отићи до
елсе део, повратак н пута

64
00:03:01,110 --> 00:03:02,990
факторијел од н минус 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
То је понашање је- ту је
ништа друго јер да уради,

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
Ово је ЦС50.

138
00:06:14,880 --> 00:06:16,580