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

2
00:00:05,587 --> 00:00:07,670
Doug LLOYD: Ja esat redzējis
video par recursion,

3
00:00:07,670 --> 00:00:10,170
viss process varētu būt
likās mazliet maģisks.

4
00:00:10,170 --> 00:00:10,930
Kā tas darbojas?

5
00:00:10,930 --> 00:00:15,010
Kā funkcijas zina, ka viņi
jāgaida un gaidīt citu vērtību

6
00:00:15,010 --> 00:00:19,150
atgriezties no citas funkcijas
piezvanīt, lai iegūtu rezultātu mēs gribam?

7
00:00:19,150 --> 00:00:22,550
>> Nu, iemesls tas darbojas, ir tāpēc, ka
par kaut ko sauc par zvanu kaudze.

8
00:00:22,550 --> 00:00:26,360
Kad jūs zvanu funkciju, tad
Sistēma atceļ telpu atmiņā

9
00:00:26,360 --> 00:00:28,120
šai funkcijai darīt savu darbu.

10
00:00:28,120 --> 00:00:31,720
Un mēs aicinām šos gabalos atmiņas ka
tiek atvēlēti katrai funkcijai

11
00:00:31,720 --> 00:00:35,670
zvanīt kaudze rāmi vai funkcija rāmi.

12
00:00:35,670 --> 00:00:38,290
Un, kā jūs varētu gaidīt,
šie kaudze rāmji

13
00:00:38,290 --> 00:00:41,000
dzīvo uz skursteņa daļu atmiņas.

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

15
00:00:43,960 --> 00:00:47,540
>> Vairāk nekā vienu funkciju kaudze rāmis
var pastāvēt atmiņā kādā noteiktā laikā.

16
00:00:47,540 --> 00:00:51,240
Ja galvenais aicina funkciju pārvietot,
un pārvietot aicina virzienu,

17
00:00:51,240 --> 00:00:54,460
visi trīs funkcijas ir atvērtas rāmji.

18
00:00:54,460 --> 00:00:57,350
Bet tie nav visi ir aktīvas rāmji.

19
00:00:57,350 --> 00:00:59,410
Šie rāmji ir izkārtoti skursteni.

20
00:00:59,410 --> 00:01:01,820
Un rāmis no
zvanījis

21
00:01:01,820 --> 00:01:04,390
funkcija ir vienmēr uz augšējās.

22
00:01:04,390 --> 00:01:07,150
Un ka vienmēr ir aktīvs rāmis.

23
00:01:07,150 --> 00:01:10,420
Tur ir tikai tiešām kādreiz viens
funkcija, kas ir aktīva laikā.

24
00:01:10,420 --> 00:01:12,420
Tas ir viens virs skursteņa.

25
00:01:12,420 --> 00:01:17,620
>> Kad funkcija prasa cits
funkcija, tā veida preses pauzi.

26
00:01:17,620 --> 00:01:20,590
Tā veida ir aizturēts, gaida.

27
00:01:20,590 --> 00:01:24,050
Un vēl kaudze rāmis ir uzstājām
uz kaudze uz augšu no tā.

28
00:01:24,050 --> 00:01:26,150
Un tas kļūst aktīvs rāmis.

29
00:01:26,150 --> 00:01:28,600
Un rāmis nekavējoties
Turpmāk tai ir jāgaida

30
00:01:28,600 --> 00:01:33,560
līdz tas ir atkal aktīvs rāmis
pirms tā var atsākt darbu.

31
00:01:33,560 --> 00:01:35,870
Ja funkcija ir
pilnīgs un tas ir darīts,

32
00:01:35,870 --> 00:01:37,720
tā rāmis ir popped off kaudzīti.

33
00:01:37,720 --> 00:01:38,950
Tas ir terminoloģija.

34
00:01:38,950 --> 00:01:41,110
Un rāmis nekavējoties
zem tā, kā es tikko teicu,

35
00:01:41,110 --> 00:01:42,880
kļūst par jauno aktīvo rāmis.

36
00:01:42,880 --> 00:01:45,960
>> Un, ja tas prasa citu funkciju,
tas notiek, lai apturētu vēlreiz.

37
00:01:45,960 --> 00:01:49,290
Ka jauna funkcija ir kaudze rāmis
uzstājām uz augšu kaudze.

38
00:01:49,290 --> 00:01:50,650
Tas būs darīt savu darbu.

39
00:01:50,650 --> 00:01:52,100
Tas varētu pop atpakaļ off.

40
00:01:52,100 --> 00:01:55,630
Un citas funkcijas
Turpmāk tas var atsākt no jauna.

41
00:01:55,630 --> 00:02:00,080
>> So iesim cauri šis atkal meklē
pie ideju Faktoriāla funkcijas

42
00:02:00,080 --> 00:02:03,070
ka mēs definēts
rekursijas video, lai redzētu

43
00:02:03,070 --> 00:02:07,770
tieši tā, kā burvju aiz šī
rekursīvs process notiek.

44
00:02:07,770 --> 00:02:09,870
Tātad šis ir mūsu visu failu, vai ne?

45
00:02:09,870 --> 00:02:14,000
Mēs definēti divi
functions-- galvenais un fakts.

46
00:02:14,000 --> 00:02:15,980
Un, kā mēs varētu gaidīt,
jebkurš C programma ir gatavojas

47
00:02:15,980 --> 00:02:18,470
sākt pirmajā rindā galvenais.

48
00:02:18,470 --> 00:02:21,660
>> Tātad, mēs izveidot jaunu kaudze rāmis galvenais.

49
00:02:21,660 --> 00:02:23,320
Un tas notiek, lai sāktu darboties.

50
00:02:23,320 --> 00:02:25,270
Galvenie zvani printf.

51
00:02:25,270 --> 00:02:29,390
Un printf gatavojas
izdrukāt faktoriālu 5.

52
00:02:29,390 --> 00:02:31,440
Nu, tas nav zināms
kāda factorial 5 ir,

53
00:02:31,440 --> 00:02:35,620
un tāpēc šis aicinājums ir jau
Atkarībā no citu funkciju zvanu.

54
00:02:35,620 --> 00:02:37,270
Tātad galvenais gatavojas pauze turpat.

55
00:02:37,270 --> 00:02:39,103
Es esmu gonna atstāt tās
bultiņa pa labi tur, krāsu

56
00:02:39,103 --> 00:02:41,360
tas tādā pašā krāsā kā
kaudze rāmis labajā pusē,

57
00:02:41,360 --> 00:02:47,720
norādīt, ka galvenais gatavojas iesaldēt
šeit, kamēr faktoriālu no 5 sauc.

58
00:02:47,720 --> 00:02:49,300
>> Tātad faktoriālu no 5 sauc.

59
00:02:49,300 --> 00:02:53,160
Un tas notiek, lai sāktu pie ļoti
sākot no faktoriālo funkciju.

60
00:02:53,160 --> 00:02:55,440
Tā uzdod jautājumu man vienāds ar 1?

61
00:02:55,440 --> 00:02:56,810
Ir 5 vienāds ar 1?

62
00:02:56,810 --> 00:02:57,410
Nu, nē.

63
00:02:57,410 --> 00:03:01,110
Tātad tas notiek, lai iet uz leju, lai
cits daļa, atgriešanās n reizes

64
00:03:01,110 --> 00:03:02,990
factorial n mīnus 1.

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

66
00:03:03,490 --> 00:03:07,070
>> Tāpēc tagad, faktoriālu 5 ir
Atkarībā no citu zvanu

67
00:03:07,070 --> 00:03:09,740
uz Faktoriāls, iet
in 4 kā parametru.

68
00:03:09,740 --> 00:03:14,210
Un tā faktoriālu
5 rāmis, ka sarkanā rāmī,

69
00:03:14,210 --> 00:03:17,160
gatavojas iesaldēt turpat
tajā rindā es esmu norādījis

70
00:03:17,160 --> 00:03:21,914
un gaidīt faktoriālu 4 līdz beigām
kas tas ir jādara tā, lai pēc tam to

71
00:03:21,914 --> 00:03:23,330
var kļūt aktīvās kadra vēlreiz.

72
00:03:23,330 --> 00:03:26,890
>> Tātad faktoriālu 4 sākas
sākums faktori.

73
00:03:26,890 --> 00:03:28,556
Ir 4 vienāds ar 1?

74
00:03:28,556 --> 00:03:30,180
Nē, tā tas būs darīt to pašu.

75
00:03:30,180 --> 00:03:31,590
Tas notiek, lai iet uz leju cits filiāli.

76
00:03:31,590 --> 00:03:33,240
Tas notiek, lai saņemtu to, ka koda rindu.

77
00:03:33,240 --> 00:03:35,710
Labi, es esmu gatavojas atgriezties četras reizes.

78
00:03:35,710 --> 00:03:41,270
Ak, faktoriālu no 3-- tik faktoriālu
4 atkarīgs faktoriālu 3 apdari.

79
00:03:41,270 --> 00:03:43,055
>> Un tā tas ir nepieciešams, lai izsauktu faktoriālu 3.

80
00:03:43,055 --> 00:03:45,180
Un tas ir gonna iet cauri
pats process vēlreiz.

81
00:03:45,180 --> 00:03:48,200
Tas sākas ar, izpaužas šeit.

82
00:03:48,200 --> 00:03:50,980
Faktoriāls gada 3. atkarīgs
par faktoriālu 1.

83
00:03:50,980 --> 00:03:53,750
Tātad factorial 2 sākas, izpaužas šeit.

84
00:03:53,750 --> 00:03:56,310
Tas ir atkarīgs no faktoriālu 1.

85
00:03:56,310 --> 00:03:57,430
Faktoriāls no 1 sākas.

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

87
00:03:57,650 --> 00:03:59,775
Tāpēc tagad mēs esam nonākuši
kaut kur interesanti, vai ne?

88
00:03:59,775 --> 00:04:02,190
Tātad tagad, 1 ir vienāds ar 1.

89
00:04:02,190 --> 00:04:05,130
Un tā mēs atgriežamies 1.

90
00:04:05,130 --> 00:04:06,770
Šajā brīdī, mēs atgriežamies.

91
00:04:06,770 --> 00:04:07,880
Funkcija ir darīts.

92
00:04:07,880 --> 00:04:11,140
Tā ir rīcība is-- tur
nekas cits, lai to darīt,

93
00:04:11,140 --> 00:04:17,006
un tā kaudze rāmis
faktoriālu no 1 pops off.

94
00:04:17,006 --> 00:04:17,589
Tas ir pabeigts.

95
00:04:17,589 --> 00:04:19,480
Tas atgriezās 1.

96
00:04:19,480 --> 00:04:23,370
Un tagad, faktoriālu 2, kas
uzreiz bija rāmis zem tā

97
00:04:23,370 --> 00:04:26,160
kaudze, kļūst aktīvs rāmis.

98
00:04:26,160 --> 00:04:29,030
>> Un tas var uzņemt
tieši tur, kur tas tika pārtraukts.

99
00:04:29,030 --> 00:04:32,240
Tas ir bijis gaida faktoriālo
no 1 līdz pabeigt savu darbu.

100
00:04:32,240 --> 00:04:33,610
Tā tagad ir pabeigta.

101
00:04:33,610 --> 00:04:35,510
Un tāpēc šeit mēs esam.

102
00:04:35,510 --> 00:04:38,080
>> Faktoriāls gada 1. atgriezās vērtību 1.

103
00:04:38,080 --> 00:04:42,430
Tātad faktoriālu no 2 var
teiksim atgriezties 2 reizes 1.

104
00:04:42,430 --> 00:04:43,680
Tās darbs tagad ir paveikts.

105
00:04:43,680 --> 00:04:49,110
Tas atgriezās no 2 līdz Faktoriāls
3, kas gaidīja to.

106
00:04:49,110 --> 00:04:53,370
Faktoriāls 3. tagad top rāmis,
aktīvā rāmis kaudze.

107
00:04:53,370 --> 00:04:58,617
Un tā tas saka, OK, labi, es eju
lai atgrieztos 3 reizes 2, kas ir 6.

108
00:04:58,617 --> 00:05:00,700
Un es esmu gatavojas sniegt, ka
vērtējam atpakaļ faktoriālo

109
00:05:00,700 --> 00:05:03,430
4, kas gaidīja mani.

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

111
00:05:04,500 --> 00:05:09,410
Faktoriāls gada 3. pops off kaudze, un
factorial 4. tagad ir aktīvs rāmis.

112
00:05:09,410 --> 00:05:13,510
>> 4 saka, OK, es esmu gatavojas atgriezties 4 reizes
faktoriālu 3, kas bija seši.

113
00:05:13,510 --> 00:05:15,980
Tas bija par vērtību,
faktoriālu no 3 atgriezās.

114
00:05:15,980 --> 00:05:19,010
Un tā 4 reizes 6 ir 24.

115
00:05:19,010 --> 00:05:20,990
Un es esmu gatavojas iet
ka atpakaļ uz Faktoriāls

116
00:05:20,990 --> 00:05:23,160
5, kas gaidīja mani.

117
00:05:23,160 --> 00:05:25,270
Faktoriāls 5. tagad ir aktīvs rāmis.

118
00:05:25,270 --> 00:05:30,700
Tas notiek, lai atgrieztos 5 reizes
faktoriālu no 4-- 5 reizes 24 vai 120--

119
00:05:30,700 --> 00:05:32,722
un dot šo vērtību
atpakaļ uz galveno, kas ir

120
00:05:32,722 --> 00:05:35,680
gaidīja ļoti pacietīgi priekšlikums
ilgu laiku apakšā krāvuma.

121
00:05:35,680 --> 00:05:36,640
>> Tas ir, ja tas viss sākās.

122
00:05:36,640 --> 00:05:37,670
Tas padarīja šo aicinājumu.

123
00:05:37,670 --> 00:05:39,400
Vairāki rāmji pārņēma augšpusē.

124
00:05:39,400 --> 00:05:41,890
Tagad ir atpakaļ uz augšu kaudze.

125
00:05:41,890 --> 00:05:43,450
Tas ir aktīvs rāmis.

126
00:05:43,450 --> 00:05:47,810
Tātad galvenais ieguva vērtību 120
atpakaļ no faktoriālu 5.

127
00:05:47,810 --> 00:05:50,750
Tas ir bijis gaida
izdrukāt šo vērtību.

128
00:05:50,750 --> 00:05:51,657
Un tad tas ir darīts.

129
00:05:51,657 --> 00:05:53,240
Nav vairāk rindiņas kodu galvenajā.

130
00:05:53,240 --> 00:05:56,800
Tātad galvenais ir rāmis pops off
kaudze, un mēs esam darījuši.

131
00:05:56,800 --> 00:05:58,992
>> Un tas, kā rekursijas darbi.

132
00:05:58,992 --> 00:06:00,200
Tas ir kā kaudze rāmji strādāt.

133
00:06:00,200 --> 00:06:03,120
Šie funkcija zvani
kas noticis iepriekš

134
00:06:03,120 --> 00:06:06,620
ir tikai uz pauzes, gaidot
par turpmākiem uzaicinājumiem

135
00:06:06,620 --> 00:06:12,050
lai pabeigtu, lai viņi varētu kļūt par aktīvo
rāmis un pabeigt to, ko viņi ir jādara.

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

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

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