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

2
00:00:05,587 --> 00:00:07,670
DOUG Lloyd: Nëse e keni parë
video mbi recursion,

3
00:00:07,670 --> 00:00:10,170
i gjithë procesi mund të ketë
dukej pak magjike.

4
00:00:10,170 --> 00:00:10,930
Si punon?

5
00:00:10,930 --> 00:00:15,010
Si mund funksionet e dinë se ata
duhet të presë dhe të presin për një tjetër vlerë

6
00:00:15,010 --> 00:00:19,150
për t'u kthyer nga një funksion të ndryshëm
të thirrur në mënyrë që të merrni rezultatin që duam?

7
00:00:19,150 --> 00:00:22,550
>> E pra, arsyeja punon kjo është për shkak se
për diçka të njohur si thirrjes rafte.

8
00:00:22,550 --> 00:00:26,360
Kur ju telefononi një funksioneve,
Sistemi i vë mënjanë hapësirë ​​në memorie

9
00:00:26,360 --> 00:00:28,120
për atë funksion për të bërë punën e saj.

10
00:00:28,120 --> 00:00:31,720
Dhe ne i quajmë këto chunks e kujtesës që
janë duke u vendosur mënjanë për çdo funksion

11
00:00:31,720 --> 00:00:35,670
thërrasë një kornizë rafte apo një kornizë funksion.

12
00:00:35,670 --> 00:00:38,290
Dhe si ju mund të presin,
Këto korniza rafte

13
00:00:38,290 --> 00:00:41,000
jetojnë në pjesën rafte e kujtesës.

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

15
00:00:43,960 --> 00:00:47,540
>> Më shumë se një funksion kornizë rafte
mund të ekzistojë në kujtesë në një kohë të dhënë.

16
00:00:47,540 --> 00:00:51,240
Nëse kryesore quan një lëvizje funksion,
dhe veprim quan drejtim,

17
00:00:51,240 --> 00:00:54,460
Të tre funksionet ketë korniza të hapura.

18
00:00:54,460 --> 00:00:57,350
Por jo të gjithë kanë korniza aktive.

19
00:00:57,350 --> 00:00:59,410
Këto korniza janë të rregulluar në një pirg.

20
00:00:59,410 --> 00:01:01,820
Dhe korniza nga
quajtur më të fundit

21
00:01:01,820 --> 00:01:04,390
funksion është gjithmonë në majë të pirg.

22
00:01:04,390 --> 00:01:07,150
Dhe kjo është gjithmonë kornizë aktiv.

23
00:01:07,150 --> 00:01:10,420
Ka vetëm me të vërtetë ndonjëherë një
funksion që është aktiv në një kohë.

24
00:01:10,420 --> 00:01:12,420
Kjo është një në krye të rafte.

25
00:01:12,420 --> 00:01:17,620
>> Kur një funksion thërret një tjetër
funksion, ai lloj i shtyn pauzë.

26
00:01:17,620 --> 00:01:20,590
Kjo lloj është në pritje, në pritje.

27
00:01:20,590 --> 00:01:24,050
Dhe një tjetër kornizë rafte është shtyrë
mbi rafte në krye të saj.

28
00:01:24,050 --> 00:01:26,150
Dhe kjo bëhet kornizë aktiv.

29
00:01:26,150 --> 00:01:28,600
Dhe kornizë menjëherë
më poshtë ajo duhet të presë

30
00:01:28,600 --> 00:01:33,560
deri sa ajo është përsëri kornizë aktiv
para se të mund të rifillojë punën e saj.

31
00:01:33,560 --> 00:01:35,870
Kur një funksion është
i plotë dhe kjo është bërë,

32
00:01:35,870 --> 00:01:37,720
kornizë saj është popped off rafte.

33
00:01:37,720 --> 00:01:38,950
Kjo është terminologjia.

34
00:01:38,950 --> 00:01:41,110
Dhe kornizë menjëherë
poshtë tij, si unë vetëm i tha,

35
00:01:41,110 --> 00:01:42,880
bëhet kornizë e re aktive.

36
00:01:42,880 --> 00:01:45,960
>> Dhe në qoftë se ai e quan një funksion tjetër,
ajo do të ndalemi përsëri.

37
00:01:45,960 --> 00:01:49,290
Kornizë rafte se funksioni i ri do
të shtyhet në pjesën e sipërme të pirg.

38
00:01:49,290 --> 00:01:50,650
Ajo do të bëjë punën e saj.

39
00:01:50,650 --> 00:01:52,100
Ajo mund të pop përsëri jashtë.

40
00:01:52,100 --> 00:01:55,630
Dhe funksioni tjetër
më poshtë ai mund të rifillojë përsëri.

41
00:01:55,630 --> 00:02:00,080
>> Pra, le të kalojnë nëpër këtë përsëri, duke kërkuar
në idenë e funksionit faktorial

42
00:02:00,080 --> 00:02:03,070
ne përkufizuar në
Recursion video për të parë

43
00:02:03,070 --> 00:02:07,770
saktësisht se si magji pas kësaj
Procesi rekursive është duke u zhvilluar.

44
00:02:07,770 --> 00:02:09,870
Pra, kjo është skedari ynë e tërë, e drejtë?

45
00:02:09,870 --> 00:02:14,000
Ne përcaktuar dy
functions-- kryesor dhe fakt.

46
00:02:14,000 --> 00:02:15,980
Dhe si ne mund të presim,
ndonjë program C po ndodh

47
00:02:15,980 --> 00:02:18,470
të fillojë në rreshtin e parë të kryesore.

48
00:02:18,470 --> 00:02:21,660
>> Pra, ne të krijojë një kornizë të re rafte për kryesor.

49
00:02:21,660 --> 00:02:23,320
Dhe ajo do të fillojë running.

50
00:02:23,320 --> 00:02:25,270
Thirrjet kryesore printf.

51
00:02:25,270 --> 00:02:29,390
Dhe printf do të
shtypura nga faktorial prej 5.

52
00:02:29,390 --> 00:02:31,440
E pra, kjo nuk e di
çfarë faktorial i 5 është,

53
00:02:31,440 --> 00:02:35,620
dhe kështu që kjo thirrje është tashmë
në varësi të një tjetër telefonatë funksion.

54
00:02:35,620 --> 00:02:37,270
Pra, kryesor do të pauzë të drejtë atje.

55
00:02:37,270 --> 00:02:39,103
Unë jam gonna të lënë të saj
shigjetë e drejtë atje, ngjyra

56
00:02:39,103 --> 00:02:41,360
ajo të njëjtën ngjyrë si
rafte kornizë në të djathtë,

57
00:02:41,360 --> 00:02:47,720
për të treguar se kryesore do të ngrijë
këtu ndërsa faktorial i 5 është quajtur.

58
00:02:47,720 --> 00:02:49,300
>> Pra faktorial i 5 është quajtur.

59
00:02:49,300 --> 00:02:53,160
Dhe ajo do të fillojë në shumë
fillimi i funksionit faktorial.

60
00:02:53,160 --> 00:02:55,440
Ai shtron pyetjen jam e barabartë me 1?

61
00:02:55,440 --> 00:02:56,810
5 është e barabartë me 1?

62
00:02:56,810 --> 00:02:57,410
E pra, nuk ka.

63
00:02:57,410 --> 00:03:01,110
Kështu ajo do të zbresin në
pjesë tjetër, kthimi n herë

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

65
00:03:02,990 --> 00:03:03,490
E pra, në rregull.

66
00:03:03,490 --> 00:03:07,070
>> Deri tani, faktorial i 5 është
në varësi të një tjetër telefonatë

67
00:03:07,070 --> 00:03:09,740
të faktorial, duke kaluar
në 4 si parametër.

68
00:03:09,740 --> 00:03:14,210
Dhe kështu faktorial i
5 kornizë, që kornizë të kuqe,

69
00:03:14,210 --> 00:03:17,160
do të ngrijë të drejtë ka
në këtë linjë e kam treguar

70
00:03:17,160 --> 00:03:21,914
dhe të presin për faktoriale e 4 të përfunduar
çfarë ajo ka nevojë për të bërë kështu që atëherë ajo

71
00:03:21,914 --> 00:03:23,330
mund të bëhet kuadër aktive përsëri.

72
00:03:23,330 --> 00:03:26,890
>> Pra faktorial i 4 fillon në
fillimi i faktorial.

73
00:03:26,890 --> 00:03:28,556
4 është e barabartë me 1?

74
00:03:28,556 --> 00:03:30,180
Jo, kështu që ajo do të bëjë të njëjtën gjë.

75
00:03:30,180 --> 00:03:31,590
Ajo do të shkojë poshtë tjetër degë.

76
00:03:31,590 --> 00:03:33,240
Ajo do të marrë në këtë linjë të kodit.

77
00:03:33,240 --> 00:03:35,710
OK, unë jam duke shkuar për të kthyer katër herë.

78
00:03:35,710 --> 00:03:41,270
Oh, faktorial i 3-- kështu faktorial i
4 varet faktoriale e 3 përfunduar.

79
00:03:41,270 --> 00:03:43,055
>> Dhe kështu që ajo ka nevojë për të thirrur faktoriale e 3.

80
00:03:43,055 --> 00:03:45,180
Dhe kjo është gonna të shkojnë nëpër
i njëjti proces përsëri.

81
00:03:45,180 --> 00:03:48,200
Ajo fillon me, merr këtu.

82
00:03:48,200 --> 00:03:50,980
Faktorial i 3 varet
në faktorial prej 1.

83
00:03:50,980 --> 00:03:53,750
Pra faktorial e 2 fillon, merr këtu.

84
00:03:53,750 --> 00:03:56,310
Kjo varet nga faktoriale e 1.

85
00:03:56,310 --> 00:03:57,430
Faktorial e 1 fillon.

86
00:03:57,430 --> 00:03:57,650
>> NE RREGULL.

87
00:03:57,650 --> 00:03:59,775
Deri tani, ne jemi duke marrë
diku interesant, e drejtë?

88
00:03:59,775 --> 00:04:02,190
Kështu, 1 eshte e barabarte me 1.

89
00:04:02,190 --> 00:04:05,130
Dhe kështu kthehemi 1.

90
00:04:05,130 --> 00:04:06,770
Në këtë pikë, ne jemi të kthyer.

91
00:04:06,770 --> 00:04:07,880
Është bërë funksioni.

92
00:04:07,880 --> 00:04:11,140
Është sjellje is-- ka
asgjë tjetër për atë për të bërë,

93
00:04:11,140 --> 00:04:17,006
dhe kështu kornizë rafte për
faktorial i 1 pops off.

94
00:04:17,006 --> 00:04:17,589
Është përfunduar.

95
00:04:17,589 --> 00:04:19,480
Ajo u kthye 1.

96
00:04:19,480 --> 00:04:23,370
Dhe tani, faktorial i 2, i cili
ishte korniza menjëherë poshtë saj

97
00:04:23,370 --> 00:04:26,160
në rafte, bëhet kornizë aktiv.

98
00:04:26,160 --> 00:04:29,030
>> Dhe kjo mund të marr
pikërisht aty ku u ndërpre.

99
00:04:29,030 --> 00:04:32,240
Ajo është duke pritur për një faktorial
nga 1 për të përfunduar punën e saj.

100
00:04:32,240 --> 00:04:33,610
Ajo ka mbaruar tani.

101
00:04:33,610 --> 00:04:35,510
Dhe kështu që këtu ne jemi.

102
00:04:35,510 --> 00:04:38,080
>> Faktorial nga 1 kthyer një vlerë prej 1.

103
00:04:38,080 --> 00:04:42,430
Pra faktorial i 2 mund
të themi kthehen 2 herë 1.

104
00:04:42,430 --> 00:04:43,680
Puna e saj është bërë tani.

105
00:04:43,680 --> 00:04:49,110
Është kthyer në 2 faktorial
e 3, i cili ishte duke pritur për të.

106
00:04:49,110 --> 00:04:53,370
Faktorial i 3 tani është kornizë të lartë,
korniza aktive në rafte.

107
00:04:53,370 --> 00:04:58,617
Dhe kështu ai thotë, OK, mirë, unë jam duke shkuar
për t'u kthyer 3 herë 2, e cila është 6.

108
00:04:58,617 --> 00:05:00,700
Dhe unë jam duke shkuar për të dhënë atë
vlerësojnë përsëri në faktorial

109
00:05:00,700 --> 00:05:03,430
i 4, i cili ka qenë duke pritur për mua.

110
00:05:03,430 --> 00:05:04,500
Mbarova.

111
00:05:04,500 --> 00:05:09,410
Faktorial i 3 pops off rafte, dhe
faktorial i 4 është tani kornizë aktiv.

112
00:05:09,410 --> 00:05:13,510
>> 4 thotë, OK, unë jam duke shkuar për të kthyer 4 herë
faktorial i 3, e cila ishte gjashtë.

113
00:05:13,510 --> 00:05:15,980
Kjo ishte me vlerë që
faktorial i 3 kthye.

114
00:05:15,980 --> 00:05:19,010
Dhe kështu 4 herë 6 është 24.

115
00:05:19,010 --> 00:05:20,990
Dhe unë jam duke shkuar për të kaluar
që përsëri të faktorial

116
00:05:20,990 --> 00:05:23,160
e 5, e cila është duke pritur për mua.

117
00:05:23,160 --> 00:05:25,270
Faktorial i 5 është tani kornizë aktiv.

118
00:05:25,270 --> 00:05:30,700
Ajo do të kthehen 5 herë
faktorial i 4-- 5 herë 24, ose 120--

119
00:05:30,700 --> 00:05:32,722
dhe të japë këtë vlerë
Mbrapsht në kryesore, e cila ka

120
00:05:32,722 --> 00:05:35,680
pritur shumë durim për një
kohë të gjatë në fund të rafte.

121
00:05:35,680 --> 00:05:36,640
>> Kjo është ajo ku ajo filloi.

122
00:05:36,640 --> 00:05:37,670
Ajo e bëri këtë thirrje.

123
00:05:37,670 --> 00:05:39,400
Disa korniza mori në krye.

124
00:05:39,400 --> 00:05:41,890
Ajo është tani përsëri në krye të rafte.

125
00:05:41,890 --> 00:05:43,450
Kjo është kornizë aktive.

126
00:05:43,450 --> 00:05:47,810
Pra kryesor mori vlerën 120
prapa nga faktorial i 5.

127
00:05:47,810 --> 00:05:50,750
Ajo është në pritje për
shtypura nga atë vlerë.

128
00:05:50,750 --> 00:05:51,657
Dhe pastaj është bërë.

129
00:05:51,657 --> 00:05:53,240
Nuk ka më shumë rreshta të kodit në kryesore.

130
00:05:53,240 --> 00:05:56,800
Pra, kornizë kryesore të pops off
rafte, dhe ne jemi duke bërë.

131
00:05:56,800 --> 00:05:58,992
>> Dhe kjo është se si funksionon recursion.

132
00:05:58,992 --> 00:06:00,200
Kjo është se si të punojnë korniza rafte.

133
00:06:00,200 --> 00:06:03,120
Këto thirrje funksion
që ka ndodhur më parë

134
00:06:03,120 --> 00:06:06,620
janë vetëm në pauzë, duke pritur
për thirrjet pasuese

135
00:06:06,620 --> 00:06:12,050
të përfundojë në mënyrë që ata mund të bëhet aktive
kornizë dhe të përfundojë se çfarë ata duhet të bëjnë.

136
00:06:12,050 --> 00:06:13,060
>> Unë jam Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Kjo është CS50.

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