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

2
00:00:05,587 --> 00:00:07,670
Doug LLOYD: Jei mačiau
dėl rekursijos vaizdo,

3
00:00:07,670 --> 00:00:10,170
visas procesas gali turėti
atrodė šiek tiek magiška.

4
00:00:10,170 --> 00:00:10,930
Kaip tai veikia?

5
00:00:10,930 --> 00:00:15,010
Kaip funkcijas žino, kad jie
reikia laukti ir laukti kito vertę

6
00:00:15,010 --> 00:00:19,150
grįžti iš skirtingos funkcijos
skambinti norint gauti rezultatą mes norime?

7
00:00:19,150 --> 00:00:22,550
>> Na, priežastis tai veikia, nes
kažką, žinomą kaip skambučių kamino.

8
00:00:22,550 --> 00:00:26,360
Kai skambinate funkciją,
sistema panaikina vietos atmintyje

9
00:00:26,360 --> 00:00:28,120
šiai funkcijai atlikti savo darbą.

10
00:00:28,120 --> 00:00:31,720
Ir mes vadiname šiuos atminties gabaliukus, kad
yra atidėta kiekvienos funkcijos

11
00:00:31,720 --> 00:00:35,670
skambinti "stack frame" ar funkcija rėmo.

12
00:00:35,670 --> 00:00:38,290
Ir kaip galima tikėtis,
Šie kamino rėmeliai

13
00:00:38,290 --> 00:00:41,000
gyvena ant kamino dalį atminties.

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

15
00:00:43,960 --> 00:00:47,540
>> Daugiau nei viena funkcija "stack frame"
gali egzistuoti atmintyje tam tikru laiku.

16
00:00:47,540 --> 00:00:51,240
Jei pagrindinis vadina funkcija perkelti,
ir judėti ragina kryptį,

17
00:00:51,240 --> 00:00:54,460
visi trys funkcijos turi atvirus rėmai.

18
00:00:54,460 --> 00:00:57,350
Bet jie ne visi turi aktyvių kadrų.

19
00:00:57,350 --> 00:00:59,410
Šie rėmai yra išdėstyti kamino.

20
00:00:59,410 --> 00:01:01,820
Ir nuo rėmo
neseniai pavadino

21
00:01:01,820 --> 00:01:04,390
funkcija yra visada ant kamino.

22
00:01:04,390 --> 00:01:07,150
Ir kad yra visada aktyvus rėmas.

23
00:01:07,150 --> 00:01:10,420
Yra tik tikrai kada nors viena
funkcija tai aktyvus metu.

24
00:01:10,420 --> 00:01:12,420
Tai vienas ant kamino.

25
00:01:12,420 --> 00:01:17,620
>> Kai funkcija ragina kitas
funkcija, tai tarsi spaudžia pauzę.

26
00:01:17,620 --> 00:01:20,590
Tai tarsi yra sulaikytas, laukti.

27
00:01:20,590 --> 00:01:24,050
Ir dar krūvą rėmas stumiamos
ant ant jo kamino.

28
00:01:24,050 --> 00:01:26,150
Ir tai tampa aktyvus rėmas.

29
00:01:26,150 --> 00:01:28,600
Ir rėmas iš karto
Toliau reikia laukti

30
00:01:28,600 --> 00:01:33,560
tol, kol jis vėl yra aktyvi rėmas
prieš tai gali tęsti savo darbą.

31
00:01:33,560 --> 00:01:35,870
Kai funkcija yra
išsami ir tai daroma,

32
00:01:35,870 --> 00:01:37,720
jo rėmas yra popped nuo kamino.

33
00:01:37,720 --> 00:01:38,950
Štai terminologija.

34
00:01:38,950 --> 00:01:41,110
Ir rėmas iš karto
po juo, kaip aš ką tik pasakė,

35
00:01:41,110 --> 00:01:42,880
tampa nauja veiklioji rėmas.

36
00:01:42,880 --> 00:01:45,960
>> Ir jei ji vadina kitą funkciją,
jis ketina pristabdyti dar kartą.

37
00:01:45,960 --> 00:01:49,290
Kad naujos funkcijos kamino kadras
būti stumiama ant iš kamino viršuje.

38
00:01:49,290 --> 00:01:50,650
Tai bus padaryti savo darbą.

39
00:01:50,650 --> 00:01:52,100
Tai gali grįžti išjungtas.

40
00:01:52,100 --> 00:01:55,630
Ir kitas funkcijas,
toliau jis gali vėl ir vėl.

41
00:01:55,630 --> 00:02:00,080
>> Taigi eikime per tai vėl ieško
ties Faktorialaus funkcijos idėja

42
00:02:00,080 --> 00:02:03,070
kad mes nustatoma pagal
rekursija vaizdo pamatyti

43
00:02:03,070 --> 00:02:07,770
tiksliai, kaip už tai magija
rekursywny procesas vyksta.

44
00:02:07,770 --> 00:02:09,870
Taigi tai yra visa mūsų failas, tiesa?

45
00:02:09,870 --> 00:02:14,000
Mes nustatėme du
functions-- pagrindinis ir faktas.

46
00:02:14,000 --> 00:02:15,980
Ir kaip mes galima tikėtis,
bet C programa vyksta

47
00:02:15,980 --> 00:02:18,470
pradėti nuo pirmosios linijos pagrindinis.

48
00:02:18,470 --> 00:02:21,660
>> Taigi, mes sukurti naują "stack frame" už pagrindinis.

49
00:02:21,660 --> 00:02:23,320
Ir jis ketina pradėti veikti.

50
00:02:23,320 --> 00:02:25,270
Pagrindinės skambučiai printf.

51
00:02:25,270 --> 00:02:29,390
Ir printf ketina
spausdinti faktorialas 5.

52
00:02:29,390 --> 00:02:31,440
Na, jis nežino,
kas faktorialas 5 yra,

53
00:02:31,440 --> 00:02:35,620
todėl šis skambutis yra jau
priklausomai nuo kito skambinimo funkcijos.

54
00:02:35,620 --> 00:02:37,270
Taigi pagrindinis ketina pristabdyti teisę ten.

55
00:02:37,270 --> 00:02:39,103
Aš gonna palikti savo
rodyklė į dešinę ten, spalvą

56
00:02:39,103 --> 00:02:41,360
ji tokios pat spalvos kaip
kamino rėmo dešinėje,

57
00:02:41,360 --> 00:02:47,720
nurodo, kad pagrindinis ketina įšaldyti
čia, o faktorinė 5 vadinama.

58
00:02:47,720 --> 00:02:49,300
>> Taigi faktorinė 5 vadinama.

59
00:02:49,300 --> 00:02:53,160
Ir jis ketina pradėti labai
pradžioje Faktorialaus funkcija.

60
00:02:53,160 --> 00:02:55,440
Jis klausia aš lygus 1?

61
00:02:55,440 --> 00:02:56,810
Yra 5, lygus 1?

62
00:02:56,810 --> 00:02:57,410
Na, ne.

63
00:02:57,410 --> 00:03:01,110
Taigi jis ketina eiti į
else dalis, grąža n kartų

64
00:03:01,110 --> 00:03:02,990
faktorialas n minus 1.

65
00:03:02,990 --> 00:03:03,490
Na, gerai.

66
00:03:03,490 --> 00:03:07,070
>> Taigi dabar, faktorinė 5 yra
priklausomai kitą skambutį

67
00:03:07,070 --> 00:03:09,740
į faktorialas, einančios
in 4, kaip parametrą.

68
00:03:09,740 --> 00:03:14,210
Ir taip faktorinės
5 rėmas, kad raudonu rėmeliu,

69
00:03:14,210 --> 00:03:17,160
ketina įšaldyti teisę ten
ne tos linijos aš nurodė,

70
00:03:17,160 --> 00:03:21,914
ir laukti faktorialas 4 iki pabaigos
ką jis turi daryti, kad tada ją

71
00:03:21,914 --> 00:03:23,330
gali vėl tapo Aktyviojo rėmo.

72
00:03:23,330 --> 00:03:26,890
>> Taigi faktorialas 4 prasideda
faktorinės pradžia.

73
00:03:26,890 --> 00:03:28,556
Yra 4, lygus 1?

74
00:03:28,556 --> 00:03:30,180
Ne, todėl jis ketina padaryti tą patį.

75
00:03:30,180 --> 00:03:31,590
Ji ketina eiti į kita filialas.

76
00:03:31,590 --> 00:03:33,240
Ji ketina gauti iki to kodo eilutę.

77
00:03:33,240 --> 00:03:35,710
Gerai, aš ruošiuosi grįžti keturis kartus.

78
00:03:35,710 --> 00:03:41,270
Oi, faktorinė ir 3-- taip Faktorialas
4 priklauso nuo faktorialas 3 apdailai.

79
00:03:41,270 --> 00:03:43,055
>> Ir todėl reikia skambinti faktorialas 3.

80
00:03:43,055 --> 00:03:45,180
Ir tai viskas eiti per
tas pats procesas dar kartą.

81
00:03:45,180 --> 00:03:48,200
Jis prasideda per, gauna čia.

82
00:03:48,200 --> 00:03:50,980
Faktorinė 3 priklauso
nuo faktorialas 1.

83
00:03:50,980 --> 00:03:53,750
Taigi faktorinė 2 paleidimų, gauna čia.

84
00:03:53,750 --> 00:03:56,310
Tai priklauso nuo faktorialas 1.

85
00:03:56,310 --> 00:03:57,430
Faktorinė iš 1 paleidimų.

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

87
00:03:57,650 --> 00:03:59,775
Taigi dabar mes vis
kokioje nors įdomioje vietoje, tiesa?

88
00:03:59,775 --> 00:04:02,190
Taigi, dabar, 1 yra lygus 1,.

89
00:04:02,190 --> 00:04:05,130
Ir taip mes grįžtame 1 d.

90
00:04:05,130 --> 00:04:06,770
Šiuo metu, mes grįžtame.

91
00:04:06,770 --> 00:04:07,880
Ši funkcija daroma.

92
00:04:07,880 --> 00:04:11,140
Tai elgesys is-- ten
nieko ji padaryti,

93
00:04:11,140 --> 00:04:17,006
ir taip kamino rėmo
faktorialas 1 pasirodo išjungtas.

94
00:04:17,006 --> 00:04:17,589
Jis baigtas.

95
00:04:17,589 --> 00:04:19,480
Jis grįžo 1 d.

96
00:04:19,480 --> 00:04:23,370
Ir dabar, faktorinė 2, kuris
buvo rėmas iš karto po juo

97
00:04:23,370 --> 00:04:26,160
pluošte, tampa aktyvus rėmas.

98
00:04:26,160 --> 00:04:29,030
>> Ir tai gali pasiimti
tiksliai ten, kur jis nerašomas.

99
00:04:29,030 --> 00:04:32,240
Tai buvo laukia faktorialas
1 baigti savo darbą.

100
00:04:32,240 --> 00:04:33,610
Tai jau baigtas.

101
00:04:33,610 --> 00:04:35,510
Ir todėl čia esame.

102
00:04:35,510 --> 00:04:38,080
>> Faktorialinis iš 1 grąžintas 1 vertę.

103
00:04:38,080 --> 00:04:42,430
Taigi faktorinė 2 skardinės
tarkim grįžti 2 kartus 1 d.

104
00:04:42,430 --> 00:04:43,680
Jo darbas yra dabar padaryta.

105
00:04:43,680 --> 00:04:49,110
Jis grįžo nuo 2 iki faktorialas
3, kuris laukė jo.

106
00:04:49,110 --> 00:04:53,370
Faktorinė 3 dabar viršutinio rėmo,
aktyvus rėmas pluošte.

107
00:04:53,370 --> 00:04:58,617
Ir taip ji sako, gerai, gerai, aš ruošiuosi
grįžti 3 kartus 2, tai 6.

108
00:04:58,617 --> 00:05:00,700
Ir aš norėčiau duoti, kad
Vertiname atgal į faktorialas

109
00:05:00,700 --> 00:05:03,430
4, kuris buvo manęs laukia.

110
00:05:03,430 --> 00:05:04,500
Aš baigiau.

111
00:05:04,500 --> 00:05:09,410
Faktorinė 3 pasirodo nuo kamino, o
faktorialas 4 dabar aktyvus rėmas.

112
00:05:09,410 --> 00:05:13,510
>> 4 sako, gerai, aš ruošiuosi grįžti 4 kartus
3 faktorialas, kuris buvo šeši.

113
00:05:13,510 --> 00:05:15,980
Tai buvo verte,
faktorialas 3 grąžinami.

114
00:05:15,980 --> 00:05:19,010
Ir taip 4 kartus 6 yra 24.

115
00:05:19,010 --> 00:05:20,990
Ir aš ruošiuosi perduoti
kad atgal į faktorialas

116
00:05:20,990 --> 00:05:23,160
iš 5, kuri buvo manęs laukia.

117
00:05:23,160 --> 00:05:25,270
Faktorinė 5 dabar aktyvus rėmas.

118
00:05:25,270 --> 00:05:30,700
Jis ketina sugrįžti 5 kartus
faktorialas iš 4-- 5 kartus 24, ar 120--

119
00:05:30,700 --> 00:05:32,722
ir duoti tą vertę
atgal į pagrindinė, kuri turi

120
00:05:32,722 --> 00:05:35,680
laukėme labai kantriai dėl
ilgą laiką tuo kamino apačioje.

121
00:05:35,680 --> 00:05:36,640
>> Tai kur jis pradėjo.

122
00:05:36,640 --> 00:05:37,670
Jis padarė šį kvietimą.

123
00:05:37,670 --> 00:05:39,400
Keletas kadrų perėmė viršuje.

124
00:05:39,400 --> 00:05:41,890
Tai dabar atgal ant kamino.

125
00:05:41,890 --> 00:05:43,450
Tai aktyvus rėmas.

126
00:05:43,450 --> 00:05:47,810
Taigi pagrindinis gavo vertės 120
atgal nuo faktorialas 5.

127
00:05:47,810 --> 00:05:50,750
Tai buvo laukia
atsispausdinti šią vertę.

128
00:05:50,750 --> 00:05:51,657
Ir tada tai daroma.

129
00:05:51,657 --> 00:05:53,240
Nėra daugiau eilučių kodo Pagrindinėje.

130
00:05:53,240 --> 00:05:56,800
Taigi pagrindinis rėmas pasirodo ne
kamino, ir mes baigsite.

131
00:05:56,800 --> 00:05:58,992
>> Ir tai, kaip rekursija veikia.

132
00:05:58,992 --> 00:06:00,200
Štai kaip kamino rėmai dirbti.

133
00:06:00,200 --> 00:06:03,120
Tos funkcija skambučiai
tai atsitiko anksčiau

134
00:06:03,120 --> 00:06:06,620
yra tik ant pauzės, laukia
už paskesnių kvietimų

135
00:06:06,620 --> 00:06:12,050
baigti, todėl jie gali tapti aktyvus
apibrėžti ir baigti tai, ką jie turi daryti.

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

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

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