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

2
00:00:05,587 --> 00:00:07,670
Doug LLOYD: Če ste videli
video na rekurzije,

3
00:00:07,670 --> 00:00:10,170
celoten proces morda
zdelo malo čaroben.

4
00:00:10,170 --> 00:00:10,930
Kako deluje?

5
00:00:10,930 --> 00:00:15,010
Kako funkcije vedo, da
treba čakati in čakati na drugo vrednostjo

6
00:00:15,010 --> 00:00:19,150
vrniti iz druge funkcije
klic, da bi dobili rezultat, ki jo želimo?

7
00:00:19,150 --> 00:00:22,550
>> No, razlog to deluje, ker
nečesa znanega kot klicni dimnika.

8
00:00:22,550 --> 00:00:26,360
Ko pokličete funkcijo,
Sistem razveljavi prostora v pomnilniku

9
00:00:26,360 --> 00:00:28,120
za to funkcijo, da opravi svoje delo.

10
00:00:28,120 --> 00:00:31,720
In pravimo te kose pomnilnika,
so se v prahi za vsako funkcijo

11
00:00:31,720 --> 00:00:35,670
pokličite kup okvir ali funkcijo okvirja.

12
00:00:35,670 --> 00:00:38,290
In kot bi lahko pričakovali,
ti konzoli okvirji

13
00:00:38,290 --> 00:00:41,000
živi na dimnik del pomnilnika.

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

15
00:00:43,960 --> 00:00:47,540
>> Več kot eno funkcijo skladovnica okvir
lahko obstaja v pomnilniku v določenem času.

16
00:00:47,540 --> 00:00:51,240
Če glavni kliče funkcijo premakniti,
in poteza poziva smer,

17
00:00:51,240 --> 00:00:54,460
vse tri funkcije imajo odprte okvirje.

18
00:00:54,460 --> 00:00:57,350
Ampak ne vsi imajo aktivne okvirje.

19
00:00:57,350 --> 00:00:59,410
Ta ogrodja so razporejeni v skladovnici.

20
00:00:59,410 --> 00:01:01,820
In okvirjem iz
Najbolj nedavno pozval

21
00:01:01,820 --> 00:01:04,390
Funkcija je vedno na vrhu kupa.

22
00:01:04,390 --> 00:01:07,150
In da je vedno aktivna okvir.

23
00:01:07,150 --> 00:01:10,420
Tam je res samo kdaj ena
funkcija, ki je aktivna v trenutku.

24
00:01:10,420 --> 00:01:12,420
To je eden na vrhu kupa.

25
00:01:12,420 --> 00:01:17,620
>> Ko funkcija zahteva drugo
Funkcija je nekako pritisne pavzo.

26
00:01:17,620 --> 00:01:20,590
To nekako je na čakanju, ki čakajo.

27
00:01:20,590 --> 00:01:24,050
In še en kup okvir potisnilo
na skladovnici na vrhu je.

28
00:01:24,050 --> 00:01:26,150
In da postane aktivna okvir.

29
00:01:26,150 --> 00:01:28,600
In okvirjem takoj
Spodaj je treba počakati

30
00:01:28,600 --> 00:01:33,560
dokler ni ponovno aktivna okvir
preden se lahko nadaljuje svoje delo.

31
00:01:33,560 --> 00:01:35,870
Ko funkcija
popolna in to je storil,

32
00:01:35,870 --> 00:01:37,720
njen okvir je izstrelil off kup.

33
00:01:37,720 --> 00:01:38,950
Da je terminologija.

34
00:01:38,950 --> 00:01:41,110
In okvirjem takoj
pod njo, kot sem rekel,

35
00:01:41,110 --> 00:01:42,880
postane novi aktivni okvir.

36
00:01:42,880 --> 00:01:45,960
>> In če to zahteva drugo funkcijo,
to bo spet premor.

37
00:01:45,960 --> 00:01:49,290
Da je nova funkcija je kup okvir bo
treba potisniti na vrhu kupa.

38
00:01:49,290 --> 00:01:50,650
To bom naredil svoje delo.

39
00:01:50,650 --> 00:01:52,100
Morda pop nazaj dol.

40
00:01:52,100 --> 00:01:55,630
In druga funkcija
Spodaj pa lahko spet nadaljuje.

41
00:01:55,630 --> 00:02:00,080
>> Torej, gremo skozi to še enkrat, išče
na idejo faktorski funkcije

42
00:02:00,080 --> 00:02:03,070
da smo definirali v
rekurzija video za prikaz

43
00:02:03,070 --> 00:02:07,770
točno, kako čarobno za to
rekurzivni postopek poteka.

44
00:02:07,770 --> 00:02:09,870
Torej je to naš celoten spis, kajne?

45
00:02:09,870 --> 00:02:14,000
Opredelili smo dva
functions-- glavni in dejstvo.

46
00:02:14,000 --> 00:02:15,980
In kot lahko pričakujemo,
vsak program C se dogaja

47
00:02:15,980 --> 00:02:18,470
začeti na prvi vrstici glavni.

48
00:02:18,470 --> 00:02:21,660
>> Tako smo ustvarili nov sveženj okvir za glavno.

49
00:02:21,660 --> 00:02:23,320
In to se dogaja, da se začnejo prikazovati.

50
00:02:23,320 --> 00:02:25,270
Glavni klici printf.

51
00:02:25,270 --> 00:02:29,390
In printf se dogaja, da
izpisal fakulteto 5.

52
00:02:29,390 --> 00:02:31,440
No, ne vem,
kaj faktorsko 5 je,

53
00:02:31,440 --> 00:02:35,620
in zato je ta poziv je že
odvisno na drugem klicu funkcije.

54
00:02:35,620 --> 00:02:37,270
Torej glavno se dogaja, da se ustavite tam.

55
00:02:37,270 --> 00:02:39,103
Bom zapustil njeno
arrow tam, barvo

56
00:02:39,103 --> 00:02:41,360
je enake barve kot
kup okvir na desni strani,

57
00:02:41,360 --> 00:02:47,720
kar pomeni, da glavno se dogaja, da zamrzne
Tukaj medtem faktorsko 5 se imenuje.

58
00:02:47,720 --> 00:02:49,300
>> Tako faktorski 5 se imenuje.

59
00:02:49,300 --> 00:02:53,160
In to se dogaja, da začnejo pri zelo
začenši od faktorski funkcije.

60
00:02:53,160 --> 00:02:55,440
Sprašuje vprašanje sem enak 1?

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

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

63
00:02:57,410 --> 00:03:01,110
Tako se dogaja, da gredo navzdol
drug del, donosnost n krat

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

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

66
00:03:03,490 --> 00:03:07,070
>> Torej sedaj, faktorsko 5 je
odvisno drug klic

67
00:03:07,070 --> 00:03:09,740
na fakulteto, ki poteka
v 4 kot parameter.

68
00:03:09,740 --> 00:03:14,210
In tako fakulteto
5 okvir, da rdečim okvirjem,

69
00:03:14,210 --> 00:03:17,160
se dogaja, da zamrzne tam
na tej progi sem navedla

70
00:03:17,160 --> 00:03:21,914
in čakati na fakulteto 4 do konca
kaj je potrebno storiti, da bi ga

71
00:03:21,914 --> 00:03:23,330
lahko spet postane aktivna okvirja.

72
00:03:23,330 --> 00:03:26,890
>> Torej fakulteto 4 začne ob
začetek factorial.

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

74
00:03:28,556 --> 00:03:30,180
Ne, tako se dogaja, da storijo enako stvar.

75
00:03:30,180 --> 00:03:31,590
To se dogaja, da gredo navzdol drugega podružnico.

76
00:03:31,590 --> 00:03:33,240
To se dogaja, da pridete do te vrstice kode.

77
00:03:33,240 --> 00:03:35,710
OK, bom vrniti štirikrat.

78
00:03:35,710 --> 00:03:41,270
Oh, faktorski od 3-- tako fakulteto
4 odvisen fakulteto 3 dodelavo.

79
00:03:41,270 --> 00:03:43,055
>> In zato je potrebno poklicati fakulteto 3.

80
00:03:43,055 --> 00:03:45,180
In da se bo šel skozi
spet isti postopek.

81
00:03:45,180 --> 00:03:48,200
Začne skozi, tu dobi.

82
00:03:48,200 --> 00:03:50,980
Faktorski dne 3. odvisna
na fakulteto 1.

83
00:03:50,980 --> 00:03:53,750
Tako faktorski 2 zagonov, dobi tukaj.

84
00:03:53,750 --> 00:03:56,310
To je odvisno od fakulteto 1.

85
00:03:56,310 --> 00:03:57,430
Faktorski od 1 vklopov.

86
00:03:57,430 --> 00:03:57,650
>> V REDU.

87
00:03:57,650 --> 00:03:59,775
Torej, zdaj, smo dobili
nekje zanimivo, kajne?

88
00:03:59,775 --> 00:04:02,190
Sedaj, 1 enak 1.

89
00:04:02,190 --> 00:04:05,130
In tako smo se vrnili 1.

90
00:04:05,130 --> 00:04:06,770
Na tej točki se vračamo.

91
00:04:06,770 --> 00:04:07,880
Funkcija je naredil.

92
00:04:07,880 --> 00:04:11,140
To je vedenje is-- obstaja
nič drugega, za to storiti,

93
00:04:11,140 --> 00:04:17,006
in tako Snop okvir za
faktorski dne 1. pops off.

94
00:04:17,006 --> 00:04:17,589
To je končano.

95
00:04:17,589 --> 00:04:19,480
To je vrnil 1.

96
00:04:19,480 --> 00:04:23,370
In zdaj, faktorski od 2, ki
je okvir takoj pod njim

97
00:04:23,370 --> 00:04:26,160
v skladovnici, postane aktivna okvir.

98
00:04:26,160 --> 00:04:29,030
>> In lahko poberem
točno tam, kjer je končal.

99
00:04:29,030 --> 00:04:32,240
To je čakala za fakulteto
od 1. končati svoje delo.

100
00:04:32,240 --> 00:04:33,610
Zdaj je končano.

101
00:04:33,610 --> 00:04:35,510
In zato smo tukaj.

102
00:04:35,510 --> 00:04:38,080
>> Faktorski dne 1. vrnjena vrednost 1.

103
00:04:38,080 --> 00:04:42,430
Tako faktorski 2 pločevinki
recimo vrniti 2-krat 1.

104
00:04:42,430 --> 00:04:43,680
Njegovo delo je zdaj končano.

105
00:04:43,680 --> 00:04:49,110
To je vrnil 2 za fakulteto
od 3, ki je čakal njo.

106
00:04:49,110 --> 00:04:53,370
Fakulteta za 3 je zdaj top okvir,
aktivna okvir v skladovnici.

107
00:04:53,370 --> 00:04:58,617
In tako pravi, OK, no, jaz grem
, da se vrnete 3 krat 2, ki je 6.

108
00:04:58,617 --> 00:05:00,700
In bom dal, da
cenijo nazaj na fakulteto

109
00:05:00,700 --> 00:05:03,430
od 4, ki je bil me čaka.

110
00:05:03,430 --> 00:05:04,500
Končal sem.

111
00:05:04,500 --> 00:05:09,410
Faktorski dne 3. pops off kup, in
faktorski dne 4. je zdaj aktiven okvir.

112
00:05:09,410 --> 00:05:13,510
>> 4 pravi, OK, grem, da se vrnete 4-krat
fakulteto 3, ki je bil šest.

113
00:05:13,510 --> 00:05:15,980
To je bilo od vrednosti, ki jo
faktorski dne 3. vrnil.

114
00:05:15,980 --> 00:05:19,010
In tako 4 krat 6 je 24.

115
00:05:19,010 --> 00:05:20,990
In grem mimo
da nazaj na fakulteto

116
00:05:20,990 --> 00:05:23,160
5, ki je bil me čaka.

117
00:05:23,160 --> 00:05:25,270
Faktorski 5 je zdaj aktiven okvir.

118
00:05:25,270 --> 00:05:30,700
To se dogaja, da se vrnete 5-krat
fakulteto 4-- 5-krat 24 ali 120--

119
00:05:30,700 --> 00:05:32,722
in daje to vrednost
nazaj na glavno, ki ima

120
00:05:32,722 --> 00:05:35,680
čakali zelo potrpežljivo
Dolgo časa na dnu dimnika.

121
00:05:35,680 --> 00:05:36,640
>> Tam, kjer se je začelo.

122
00:05:36,640 --> 00:05:37,670
To je ta poziv.

123
00:05:37,670 --> 00:05:39,400
Več okvirji prevzel na vrhu.

124
00:05:39,400 --> 00:05:41,890
Zdaj je spet na vrhu kupa.

125
00:05:41,890 --> 00:05:43,450
To je aktivna okvir.

126
00:05:43,450 --> 00:05:47,810
Torej glavni dobil vrednost 120
nazaj od fakulteto 5.

127
00:05:47,810 --> 00:05:50,750
To je čakal, da
natisnete te vrednosti.

128
00:05:50,750 --> 00:05:51,657
In potem je to storjeno.

129
00:05:51,657 --> 00:05:53,240
Ni več vrstic kode v glavnem.

130
00:05:53,240 --> 00:05:56,800
Torej, okvir glavni je pops off
stack, in sva končala.

131
00:05:56,800 --> 00:05:58,992
>> In to je, kako rekurzija deluje.

132
00:05:58,992 --> 00:06:00,200
To je, kako konzoli okvirji delujejo.

133
00:06:00,200 --> 00:06:03,120
Ti klici funkcij
prej, da se je zgodilo

134
00:06:03,120 --> 00:06:06,620
so le na premor, čaka
za nadaljnje klice

135
00:06:06,620 --> 00:06:12,050
do konca, tako da lahko postane aktivna
kompozicije in konča, kaj morajo storiti.

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

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

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