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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Ak ste videli
video na rekurzia,

3
00:00:07,670 --> 00:00:10,170
Celý proces môže mať
Zdalo sa trochu čarovné.

4
00:00:10,170 --> 00:00:10,930
Ako to funguje?

5
00:00:10,930 --> 00:00:15,010
Ako sa funkcie, vedia, že
musieť čakať a čakať na inú hodnotu

6
00:00:15,010 --> 00:00:19,150
až sa vráti zo inú funkciu
zavolať, aby si výsledok chceme?

7
00:00:19,150 --> 00:00:22,550
>> No, dôvod, prečo to funguje, je to, že
niečoho známeho ako zásobníka volania.

8
00:00:22,550 --> 00:00:26,360
Pri volaní funkciu,
Systém vyčleňuje miesto v pamäti

9
00:00:26,360 --> 00:00:28,120
pre túto funkciu robiť svoju prácu.

10
00:00:28,120 --> 00:00:31,720
A my nazývame tieto kúsky pamäte, ktorá
sú vyčlenené pre každú funkciu

11
00:00:31,720 --> 00:00:35,670
volajte rám zásobníka alebo funkciu rámca.

12
00:00:35,670 --> 00:00:38,290
A ako sa dalo očakávať,
Tieto zásobník rámy

13
00:00:38,290 --> 00:00:41,000
žijú na zásobníku časť pamäti.

14
00:00:41,000 --> 00:00:43,960

15
00:00:43,960 --> 00:00:47,540
>> Viac ako jedna funkcia stack frame
môže existovať v pamäti v danom čase.

16
00:00:47,540 --> 00:00:51,240
Ak hlavný volá funkciu ťah,
a žiada, aby pohyb smerom,

17
00:00:51,240 --> 00:00:54,460
všetky tri funkcie majú otvorené rámy.

18
00:00:54,460 --> 00:00:57,350
Ale nie všetci majú aktívny rámy.

19
00:00:57,350 --> 00:00:59,410
Tieto rámy sú usporiadané v zásobníku.

20
00:00:59,410 --> 00:01:01,820
A rám z
naposledy volal

21
00:01:01,820 --> 00:01:04,390
funkcia je vždy v hornej časti zásobníka.

22
00:01:04,390 --> 00:01:07,150
A to je vždy aktívny rámček.

23
00:01:07,150 --> 00:01:10,420
Je tu len naozaj vždy raz
Funkcia, ktorá je aktívna vždy.

24
00:01:10,420 --> 00:01:12,420
Je to jeden na vrchole zásobníka.

25
00:01:12,420 --> 00:01:17,620
>> Keď sa funkcie volá ďalšia
funkcie, to nejako lisy pauzu.

26
00:01:17,620 --> 00:01:20,590
Tak nejako je v poradí, a čakal.

27
00:01:20,590 --> 00:01:24,050
A ďalšie stack frame je tlačená
do zásobníka na vrchole toho.

28
00:01:24,050 --> 00:01:26,150
A to sa stane aktívnou rámček.

29
00:01:26,150 --> 00:01:28,600
A snímka bezprostredne
Nižšie je potrebné čakať

30
00:01:28,600 --> 00:01:33,560
kým nie je opäť aktívny frame
pred tým, než môže pokračovať v jeho práci.

31
00:01:33,560 --> 00:01:35,870
Ak je funkcia
kompletný a je to hotovo,

32
00:01:35,870 --> 00:01:37,720
jeho rám je vyskočila z kôpky.

33
00:01:37,720 --> 00:01:38,950
To je terminológia.

34
00:01:38,950 --> 00:01:41,110
A snímka bezprostredne
pod ňou, ako som práve povedal,

35
00:01:41,110 --> 00:01:42,880
sa stane novým aktívnym rámu.

36
00:01:42,880 --> 00:01:45,960
>> A ak to volá inú funkciu,
že to bude zase pauzu.

37
00:01:45,960 --> 00:01:49,290
Tá nová funkcia stack frame bude
nasunúť na vrchole zásobníka.

38
00:01:49,290 --> 00:01:50,650
To bude robiť svoju prácu.

39
00:01:50,650 --> 00:01:52,100
Mohlo by to pop späť.

40
00:01:52,100 --> 00:01:55,630
A ďalšie funkcie
pod ňou môže pokračovať znovu.

41
00:01:55,630 --> 00:02:00,080
>> Takže poďme cez to ešte raz, hľadá
pri predstave, že funkcie faktoriálu

42
00:02:00,080 --> 00:02:03,070
že definované v
rekurzia video vidieť

43
00:02:03,070 --> 00:02:07,770
presne tak, ako kúzlo za tým
rekurzívne proces prebieha.

44
00:02:07,770 --> 00:02:09,870
Takže to je celý náš súbor, že jo?

45
00:02:09,870 --> 00:02:14,000
Definovali sme dva
functions-- hlavné a fakt.

46
00:02:14,000 --> 00:02:15,980
A ako by sme mohli očakávať,
akýkoľvek program v jazyku C sa deje

47
00:02:15,980 --> 00:02:18,470
začať na prvom riadku hlavnej.

48
00:02:18,470 --> 00:02:21,660
>> Tak sme vytvoriť nový rámec pre hlavné zásobníka.

49
00:02:21,660 --> 00:02:23,320
A bude to začať zobrazovať.

50
00:02:23,320 --> 00:02:25,270
Hlavné volanie printf.

51
00:02:25,270 --> 00:02:29,390
A printf bude
vytlačiť faktoriál 5.

52
00:02:29,390 --> 00:02:31,440
No, to nevie
čo faktoriál 5 je,

53
00:02:31,440 --> 00:02:35,620
a tak tento hovor sa už
v závislosti na inom volanie funkcie.

54
00:02:35,620 --> 00:02:37,270
Takže hlavný bude pozastaviť práve tam.

55
00:02:37,270 --> 00:02:39,103
Nechám svoje
šípka vpravo tam, farba

56
00:02:39,103 --> 00:02:41,360
to rovnakej farby ako
stack frame na pravej strane,

57
00:02:41,360 --> 00:02:47,720
čo znamená, že hlavná bude zmraziť
tu, zatiaľ čo faktoriál 5 sa nazýva.

58
00:02:47,720 --> 00:02:49,300
>> Takže faktoriál 5 sa nazýva.

59
00:02:49,300 --> 00:02:53,160
A bude to začať u veľmi
začiatok faktoriálnym funkcie.

60
00:02:53,160 --> 00:02:55,440
To kladie otázku mám činiť až 1?

61
00:02:55,440 --> 00:02:56,810
Je 5 presne 1?

62
00:02:56,810 --> 00:02:57,410
No, no.

63
00:02:57,410 --> 00:03:01,110
Tak to bude, aby šiel do
else časť, návrat n krát

64
00:03:01,110 --> 00:03:02,990
faktoriál n mínus 1.

65
00:03:02,990 --> 00:03:03,490
No, OK.

66
00:03:03,490 --> 00:03:07,070
>> Takže teraz, faktoriál 5 je
V závislosti na ďalšom hovoru

67
00:03:07,070 --> 00:03:09,740
na faktoriál, odovzdávanie
v 4 ako parameter.

68
00:03:09,740 --> 00:03:14,210
A tak sa faktoriál
5 rám, ktorý červeným rámikom,

69
00:03:14,210 --> 00:03:17,160
sa chystá zmraziť práve tam
v tomto riadku som uvedený

70
00:03:17,160 --> 00:03:21,914
a čakať na faktoriálu 4 až do konca
čo je potrebné to urobiť tak, že potom ju

71
00:03:21,914 --> 00:03:23,330
sa môže stať opäť aktívny rámček.

72
00:03:23,330 --> 00:03:26,890
>> Takže faktoriál 4 začína na
začiatok faktoriál.

73
00:03:26,890 --> 00:03:28,556
4 je rovné 1?

74
00:03:28,556 --> 00:03:30,180
Nie, tak to bude robiť to isté.

75
00:03:30,180 --> 00:03:31,590
Bude to ísť dole iného vetva.

76
00:03:31,590 --> 00:03:33,240
Bude sa dostať na tento riadok kódu.

77
00:03:33,240 --> 00:03:35,710
OK, budem sa vrátiť štyrikrát.

78
00:03:35,710 --> 00:03:41,270
Oh, faktoriál 3-- tak faktoriálu
4 závisí na faktoriál 3 úprav.

79
00:03:41,270 --> 00:03:43,055
>> A tak je potreba volať faktoriál 3.

80
00:03:43,055 --> 00:03:45,180
A to bude prejsť
opäť rovnaký proces.

81
00:03:45,180 --> 00:03:48,200
Začína to cez, sa sem dostane.

82
00:03:48,200 --> 00:03:50,980
Faktoriál z 3. závisí
o faktoriál 1.

83
00:03:50,980 --> 00:03:53,750
Takže faktoriál 2 štartov, sa sem dostane.

84
00:03:53,750 --> 00:03:56,310
Záleží na tom, faktoriál 1.

85
00:03:56,310 --> 00:03:57,430
Faktoriál z 1 štartov.

86
00:03:57,430 --> 00:03:57,650
>> OK.

87
00:03:57,650 --> 00:03:59,775
Takže teraz, sa dostávame
nejakom zaujímavom mieste, že jo?

88
00:03:59,775 --> 00:04:02,190
Teraz teda, 1 je rovný 1.

89
00:04:02,190 --> 00:04:05,130
A tak sa vraciame 1.

90
00:04:05,130 --> 00:04:06,770
V tomto bode, sa vraciame.

91
00:04:06,770 --> 00:04:07,880
Funkcia sa stalo.

92
00:04:07,880 --> 00:04:11,140
Je to správanie je-- je tu
nič iné pre to robiť,

93
00:04:11,140 --> 00:04:17,006
a tak rámec frontu pre
faktoriál 1 objavia off.

94
00:04:17,006 --> 00:04:17,589
Je koniec.

95
00:04:17,589 --> 00:04:19,480
To sa vrátil 1.

96
00:04:19,480 --> 00:04:23,370
A teraz, faktoriál 2, ktorý
bol rám bezprostredne pod ním

97
00:04:23,370 --> 00:04:26,160
v stohu, sa stane aktívnou rámček.

98
00:04:26,160 --> 00:04:29,030
>> A to môže vyzdvihnúť
presne tam, kde prestali.

99
00:04:29,030 --> 00:04:32,240
Bolo to čakanie na faktoriál
1. dokončiť svoju prácu.

100
00:04:32,240 --> 00:04:33,610
Teraz bolo dokončené.

101
00:04:33,610 --> 00:04:35,510
A tak sme tu.

102
00:04:35,510 --> 00:04:38,080
>> Faktoriál z 1. vrátila hodnotu 1.

103
00:04:38,080 --> 00:04:42,430
Takže faktoriál 2 môže
povedzme vrátiť 2 krát 1.

104
00:04:42,430 --> 00:04:43,680
Jeho práca je teraz hotovo.

105
00:04:43,680 --> 00:04:49,110
Je to vrátil do 2 faktoriál
z 3., ktorý čakal na neho.

106
00:04:49,110 --> 00:04:53,370
Faktoriál z 3 je teraz horný rám,
aktívny rám v stohu.

107
00:04:53,370 --> 00:04:58,617
A tak hovorí, OK, dobre, idem
Pre návrat 3x 2, čo je 6.

108
00:04:58,617 --> 00:05:00,700
A ja dám, že
hodnotu späť faktoriál

109
00:05:00,700 --> 00:05:03,430
4, ktorý bol na mňa čaká.

110
00:05:03,430 --> 00:05:04,500
Skončil som.

111
00:05:04,500 --> 00:05:09,410
Faktoriál z 3. objaví mimo zásobníka, a
faktoriál 4 je teraz aktívny rámček.

112
00:05:09,410 --> 00:05:13,510
>> 4 hovorí, OK, budem sa vrátiť 4 krát
faktoriál 3, čo bolo šesť.

113
00:05:13,510 --> 00:05:15,980
To bola hodnota, ktorá
faktoriál 3 vrátil.

114
00:05:15,980 --> 00:05:19,010
A tak 4 krát 6 je 24.

115
00:05:19,010 --> 00:05:20,990
A ja idem prejsť
že späť do faktoriál

116
00:05:20,990 --> 00:05:23,160
5, ktorý bol na mňa čaká.

117
00:05:23,160 --> 00:05:25,270
Faktoriál 5 je teraz aktívny rámček.

118
00:05:25,270 --> 00:05:30,700
Bude to návrat 5x
faktoriál 4-- 5 krát 24, alebo 120--

119
00:05:30,700 --> 00:05:32,722
a dať túto hodnotu
späť na hlavnú, ktorá má

120
00:05:32,722 --> 00:05:35,680
Čakal veľmi trpezlivo
dlho v spodnej časti zásobníka.

121
00:05:35,680 --> 00:05:36,640
>> To je miesto, kde to začalo.

122
00:05:36,640 --> 00:05:37,670
To robilo toto volanie.

123
00:05:37,670 --> 00:05:39,400
Niekoľko snímok prevzal na vrchole.

124
00:05:39,400 --> 00:05:41,890
To je teraz späť v hornej časti zásobníka.

125
00:05:41,890 --> 00:05:43,450
Je to aktívny rámček.

126
00:05:43,450 --> 00:05:47,810
Takže hlavný dostal hodnotu 120
späť z faktoriál 5.

127
00:05:47,810 --> 00:05:50,750
Je to už čaká na
vytlačiť túto hodnotu.

128
00:05:50,750 --> 00:05:51,657
A potom sa to robí.

129
00:05:51,657 --> 00:05:53,240
Neexistuje žiadne ďalšie riadky kódu v hlavnej.

130
00:05:53,240 --> 00:05:56,800
Takže hlavné je rám objavia off
zásobníka, a my sme urobili.

131
00:05:56,800 --> 00:05:58,992
>> A to je to, ako funguje rekurzia.

132
00:05:58,992 --> 00:06:00,200
To je, ako stack snímok pracovať.

133
00:06:00,200 --> 00:06:03,120
Tieto volania funkcií
že sa stalo predtým

134
00:06:03,120 --> 00:06:06,620
sú len na pauze, čakanie
pre nasledujúcich výziev

135
00:06:06,620 --> 00:06:12,050
až do konca, takže sa môže stať aktívnym
rám a dokončiť to, čo je potrebné urobiť.

136
00:06:12,050 --> 00:06:13,060
>> Som Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
To je CS50.

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