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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Ha láttad
A videó rekurzív,

3
00:00:07,670 --> 00:00:10,170
Az egész folyamat lehet,
tűnt egy kicsit varázslatos.

4
00:00:10,170 --> 00:00:10,930
Hogyan működik?

5
00:00:10,930 --> 00:00:15,010
Hogyan funkciókat tudja, hogy
meg kell várni, és várni egy másik érték

6
00:00:15,010 --> 00:00:19,150
hogy visszatérjen egy másik funkció
hívja annak érdekében, hogy az eredmény, amit akar?

7
00:00:19,150 --> 00:00:22,550
>> Nos, az ok ez működik az az oka,
Az valami ismert hívás verem.

8
00:00:22,550 --> 00:00:26,360
Ha hívja a funkciót, a
rendszer félreteszi hely a memóriában

9
00:00:26,360 --> 00:00:28,120
az adott funkcióra, hogy tegye a dolgát.

10
00:00:28,120 --> 00:00:31,720
És hívjuk ezeket a darabokat a memória
a hatályon kívül helyezését az egyes funkciók

11
00:00:31,720 --> 00:00:35,670
hívni egy verem keret vagy funkció keretben.

12
00:00:35,670 --> 00:00:38,290
És ahogy az várható,
Ezek stack frame

13
00:00:38,290 --> 00:00:41,000
él a stack része a memória.

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

15
00:00:43,960 --> 00:00:47,540
>> Egynél több funkciót verem
létezhet a memóriában egy adott időben.

16
00:00:47,540 --> 00:00:51,240
Ha fő meghív egy függvényt lépés,
és a lépés felhívja irányba,

17
00:00:51,240 --> 00:00:54,460
Mindhárom funkció van nyitva kereteket.

18
00:00:54,460 --> 00:00:57,350
De nem minden aktív kereteket.

19
00:00:57,350 --> 00:00:59,410
Ezek a keretek vannak elrendezve egy verem.

20
00:00:59,410 --> 00:01:01,820
És a keretet a
hívtunk

21
00:01:01,820 --> 00:01:04,390
funkció mindig a verem tetején.

22
00:01:04,390 --> 00:01:07,150
És, hogy az mindig az aktív keretben.

23
00:01:07,150 --> 00:01:10,420
Már csak igazán soha egyetlen
funkciót, ami lehet aktív.

24
00:01:10,420 --> 00:01:12,420
Ez az egyik a tetején a verem.

25
00:01:12,420 --> 00:01:17,620
>> Amikor egy függvény meghívja a másik
funkciót, ez a fajta megnyomja szünet.

26
00:01:17,620 --> 00:01:20,590
Ez a fajta van zárva, akkor vár.

27
00:01:20,590 --> 00:01:24,050
És még egy verem keret tolta
a verembe a tetején.

28
00:01:24,050 --> 00:01:26,150
És ez lesz az aktív keretben.

29
00:01:26,150 --> 00:01:28,600
És a keret azonnal
alatta kell várni

30
00:01:28,600 --> 00:01:33,560
amíg ez megint az aktív keret
mielőtt folytatja munkáját.

31
00:01:33,560 --> 00:01:35,870
Amikor egy funkció
teljes és kész,

32
00:01:35,870 --> 00:01:37,720
A keret pattant ki a köteget.

33
00:01:37,720 --> 00:01:38,950
Ez a terminológiát.

34
00:01:38,950 --> 00:01:41,110
És a keret azonnal
alatta, ahogy az előbb mondtam,

35
00:01:41,110 --> 00:01:42,880
lesz az új aktív keretben.

36
00:01:42,880 --> 00:01:45,960
>> És ha felhív egy másik funkció,
ez lesz ismét szünetet.

37
00:01:45,960 --> 00:01:49,290
Ez az új funkció a verem keret
nyomni rá a tetején a verem.

38
00:01:49,290 --> 00:01:50,650
Ez lesz a dolgát.

39
00:01:50,650 --> 00:01:52,100
Lehet, hogy pop vissza le.

40
00:01:52,100 --> 00:01:55,630
És a többi funkció
alatta folytathatja újra.

41
00:01:55,630 --> 00:02:00,080
>> Szóval menjünk át ezt újra, keres
a gondolatra, hogy a faktoriális függvény

42
00:02:00,080 --> 00:02:03,070
hogy meghatározott
rekurzív videó megtekintéséhez

43
00:02:03,070 --> 00:02:07,770
pontosan a mágia mögött
rekurzív folyamat zajlik.

44
00:02:07,770 --> 00:02:09,870
Szóval ez a mi egész fájlt, ugye?

45
00:02:09,870 --> 00:02:14,000
Mi határozza meg a két
functions-- fő- és tény.

46
00:02:14,000 --> 00:02:15,980
És ahogy az várható,
minden C program folyik

47
00:02:15,980 --> 00:02:18,470
kezdeni az első sorban a fő.

48
00:02:18,470 --> 00:02:21,660
>> Így létrejön egy verem keret fő.

49
00:02:21,660 --> 00:02:23,320
És ez meg fog ezután kezdődhet el.

50
00:02:23,320 --> 00:02:25,270
Fő hívások printf.

51
00:02:25,270 --> 00:02:29,390
És a printf fog
nyomtassa ki faktoriálisát 5.

52
00:02:29,390 --> 00:02:31,440
Nos, ez nem tudom,
mi faktoriálisát 5,

53
00:02:31,440 --> 00:02:35,620
és így ez a hívás már
attól függően, hogy egy másik függvényhívás.

54
00:02:35,620 --> 00:02:37,270
Tehát fő fog szünet ott.

55
00:02:37,270 --> 00:02:39,103
Fogom hagyni, hogy
nyíl ott, színes

56
00:02:39,103 --> 00:02:41,360
ez ugyanolyan színű, mint a
verem a jobb oldalon,

57
00:02:41,360 --> 00:02:47,720
jelezve, hogy a fő megy, hogy fagyassza
Itt míg faktoriálisát 5 nevezik.

58
00:02:47,720 --> 00:02:49,300
>> Tehát faktoriálisát 5 nevezik.

59
00:02:49,300 --> 00:02:53,160
És ez meg fog kezdeni a nagyon
elején a faktoriális függvény.

60
00:02:53,160 --> 00:02:55,440
Ez teszi fel a kérdést én egyenlő 1?

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

62
00:02:56,810 --> 00:02:57,410
Hát nem.

63
00:02:57,410 --> 00:03:01,110
Szóval ez fog lemenni
A más részét, cserébe n-szer

64
00:03:01,110 --> 00:03:02,990
faktoriálisát n mínusz 1.

65
00:03:02,990 --> 00:03:03,490
Akkor jó.

66
00:03:03,490 --> 00:03:07,070
>> Tehát most, faktoriálisát 5
attól függően, hogy egy másik hívást

67
00:03:07,070 --> 00:03:09,740
a faktoriális, átadva
4 paraméterként.

68
00:03:09,740 --> 00:03:14,210
És így faktoriálisát
5 keret, hogy a piros kerettel,

69
00:03:14,210 --> 00:03:17,160
megy, hogy fagyassza ott
abban vonal, amit megjelölt

70
00:03:17,160 --> 00:03:21,914
és várjon faktoriálisát 4 befejezni
mit kell tenni annak érdekében, hogy akkor

71
00:03:21,914 --> 00:03:23,330
válhat az aktív frame újra.

72
00:03:23,330 --> 00:03:26,890
>> Tehát faktoriálisát 4 kezdet
Az elején faktoros.

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

74
00:03:28,556 --> 00:03:30,180
Nem, így fog tenni ugyanezt.

75
00:03:30,180 --> 00:03:31,590
Meg fog lemenni az else ág.

76
00:03:31,590 --> 00:03:33,240
Meg fog eljutni, hogy kódsort.

77
00:03:33,240 --> 00:03:35,710
OK, megyek vissza négyszer.

78
00:03:35,710 --> 00:03:41,270
Ó, faktoriálisát 3-- így faktoriálisát
4 függ faktoriálisát 3 befejező.

79
00:03:41,270 --> 00:03:43,055
>> És ezért kell hívni faktoriálisát 3.

80
00:03:43,055 --> 00:03:45,180
És ez fog átmenni
ugyanez a folyamat újra.

81
00:03:45,180 --> 00:03:48,200
Ez a tanulás, ideér.

82
00:03:48,200 --> 00:03:50,980
Faktoriálisát 3 múlik
A faktoriálisát 1.

83
00:03:50,980 --> 00:03:53,750
Tehát faktoriálisát 2 kezdődik, ideér.

84
00:03:53,750 --> 00:03:56,310
Attól függ, faktoriálisát 1.

85
00:03:56,310 --> 00:03:57,430
Faktoriálisát 1 megkezdődik.

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

87
00:03:57,650 --> 00:03:59,775
Tehát most, mi megvagyunk
Valahol érdekes, ugye?

88
00:03:59,775 --> 00:04:02,190
Tehát most, 1 egyenlő 1.

89
00:04:02,190 --> 00:04:05,130
És így visszatérünk 1.

90
00:04:05,130 --> 00:04:06,770
Ezen a ponton visszatérünk.

91
00:04:06,770 --> 00:04:07,880
A funkció kész.

92
00:04:07,880 --> 00:04:11,140
Ez a magatartása is-- van
semmi mást nem kell tennie,

93
00:04:11,140 --> 00:04:17,006
és így a verem keret
faktoriálisát 1 durran ki.

94
00:04:17,006 --> 00:04:17,589
Kész van.

95
00:04:17,589 --> 00:04:19,480
Ez iránt 1.

96
00:04:19,480 --> 00:04:23,370
És most, faktoriálisát 2, amely
volt a keret közvetlenül alatta

97
00:04:23,370 --> 00:04:26,160
a verem, lesz az aktív keretben.

98
00:04:26,160 --> 00:04:29,030
>> És akkor vegye fel
pontosan ott, ahol abbahagyta.

99
00:04:29,030 --> 00:04:32,240
Ez már vár egy faktoros
1 befejezni a munkát.

100
00:04:32,240 --> 00:04:33,610
Mára elkészült.

101
00:04:33,610 --> 00:04:35,510
És így itt vagyunk.

102
00:04:35,510 --> 00:04:38,080
>> Faktoriálisát 1 visszaadott értéke 1.

103
00:04:38,080 --> 00:04:42,430
Tehát faktoriálisát 2 doboz
mondjuk visszatér 2-szer 1.

104
00:04:42,430 --> 00:04:43,680
Munkáját most történik.

105
00:04:43,680 --> 00:04:49,110
Ez visszatért 2 faktoriális
3, amely már várt is.

106
00:04:49,110 --> 00:04:53,370
Faktoriálisát 3 most a felső keret,
Az aktív keret a stack.

107
00:04:53,370 --> 00:04:58,617
És ez így mondja, OK, nos, én megyek
hogy visszatérjen 3-szor 2, amely 6.

108
00:04:58,617 --> 00:05:00,700
És fogok adni, hogy
értéket vissza faktoros

109
00:05:00,700 --> 00:05:03,430
4, amely már várt rám.

110
00:05:03,430 --> 00:05:04,500
Végeztem.

111
00:05:04,500 --> 00:05:09,410
Faktoriálisát 3 durran ki a köteget,
faktoriálisát 4 jelenleg az aktív keretben.

112
00:05:09,410 --> 00:05:13,510
>> 4. mondja, OK, megyek vissza 4-szer
faktoriálisát 3 volt, ami hat.

113
00:05:13,510 --> 00:05:15,980
Ez volt az érték,
faktoriálisát 3 visszatért.

114
00:05:15,980 --> 00:05:19,010
És így 4-szer 6 24.

115
00:05:19,010 --> 00:05:20,990
És megyek át
hogy vissza Faktoriális

116
00:05:20,990 --> 00:05:23,160
5, amely már várt rám.

117
00:05:23,160 --> 00:05:25,270
Faktoriálisát 5 most az aktív keret.

118
00:05:25,270 --> 00:05:30,700
Meg fog visszatérni 5 alkalommal
faktoriálisát 4-- 5-ször 24, illetve 120--

119
00:05:30,700 --> 00:05:32,722
és adja az értéket
vissza a fő, amely

120
00:05:32,722 --> 00:05:35,680
vártunk nagyon türelmesen egy
hosszú ideig alján a verem.

121
00:05:35,680 --> 00:05:36,640
>> Ez ahonnan indultak.

122
00:05:36,640 --> 00:05:37,670
Ez tette ezt a hívást.

123
00:05:37,670 --> 00:05:39,400
Több keretek vette át a tetején.

124
00:05:39,400 --> 00:05:41,890
Ez most vissza a köteg tetején.

125
00:05:41,890 --> 00:05:43,450
Ez az aktív keret.

126
00:05:43,450 --> 00:05:47,810
Tehát fő kapott értéket 120
vissza faktoriálisát 5.

127
00:05:47,810 --> 00:05:50,750
Ez már várja, hogy
nyomtassa ki ezt az értéket.

128
00:05:50,750 --> 00:05:51,657
És akkor kell ezt csinálni.

129
00:05:51,657 --> 00:05:53,240
Nincs több sornyi kódot fő.

130
00:05:53,240 --> 00:05:56,800
Tehát a fő frame durran ki
verem, és már készen is vagyunk.

131
00:05:56,800 --> 00:05:58,992
>> És így rekurzió működik.

132
00:05:58,992 --> 00:06:00,200
Így stack frame dolgozni.

133
00:06:00,200 --> 00:06:03,120
Azok a funkciót hívások
ez történt korábban

134
00:06:03,120 --> 00:06:06,620
csak a szünet, vár
A következő hívás

135
00:06:06,620 --> 00:06:12,050
befejezni így lesz aktív
váz és befejezni, amit tennie kell.

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

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

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