1
00:00:00,000 --> 00:00:05,860
>> [Muzika]

2
00:00:05,860 --> 00:00:09,530
>> DOUG Lloyd: Ju ndoshta mendoni se
Kodi është përdorur vetëm për të kryer një detyrë.

3
00:00:09,530 --> 00:00:10,450
Ju shkruani atë.

4
00:00:10,450 --> 00:00:11,664
Ajo bën diçka.

5
00:00:11,664 --> 00:00:12,580
Kjo është shumë e shumë ajo.

6
00:00:12,580 --> 00:00:13,160
>> Ju përpiloni atë.

7
00:00:13,160 --> 00:00:13,993
Ju drejtuar programin.

8
00:00:13,993 --> 00:00:15,370
Ju jeni të mirë për të shkuar.

9
00:00:15,370 --> 00:00:17,520
>> Por besoni apo jo, nëse
ju kodit për një kohë të gjatë,

10
00:00:17,520 --> 00:00:20,550
ju në fakt mund të vijnë për të parë
Kodi si diçka që është e bukur.

11
00:00:20,550 --> 00:00:23,275
Kjo zgjidh një problem në
një mënyrë shumë interesante,

12
00:00:23,275 --> 00:00:26,510
apo ka vetëm diçka të vërtetë
i zoti në lidhje me mënyrën se si duket.

13
00:00:26,510 --> 00:00:28,750
Ju mund të jetë duke qeshur
në mua, por është e vërtetë.

14
00:00:28,750 --> 00:00:31,530
Dhe Recursion është një mënyrë
për të lloj të merrni këtë ide

15
00:00:31,530 --> 00:00:34,090
e bukur, elegante-looking kod.

16
00:00:34,090 --> 00:00:37,740
Ajo zgjidh problemet në mënyra që
janë interesante, të lehtë për të kujtoj,

17
00:00:37,740 --> 00:00:39,810
dhe çuditërisht të shkurtër.

18
00:00:39,810 --> 00:00:43,190
>> Punimet mënyrë recursion
është, një funksion gjithkund rekursive

19
00:00:43,190 --> 00:00:49,291
është përcaktuar si një funksion që e quan
vetë si pjesë e ekzekutimin e tij.

20
00:00:49,291 --> 00:00:51,790
Kjo mund të duket pak e çuditshme,
dhe ne do të shohim pak

21
00:00:51,790 --> 00:00:53,750
se si kjo punon në një moment.

22
00:00:53,750 --> 00:00:55,560
Por përsëri, këto
Procedurat janë gjithkund rekursive

23
00:00:55,560 --> 00:00:57,730
do të jetë aq elegante
sepse ata do

24
00:00:57,730 --> 00:01:00,410
për të zgjidhur këtë problem pa
që të gjitha këto funksione të tjera

25
00:01:00,410 --> 00:01:02,710
ose këto sythe të gjata.

26
00:01:02,710 --> 00:01:06,310
Ju do të shihni se këto rekursive
Procedurat do të duken aq të shkurtër.

27
00:01:06,310 --> 00:01:10,610
Dhe ata me të vërtetë janë duke shkuar për të bërë
Kodi tuaj duken shumë më të bukur.

28
00:01:10,610 --> 00:01:12,560
>> Unë do të ju jap një shembull
e kjo për të parë se si

29
00:01:12,560 --> 00:01:14,880
një procedurë rekursive mund të përcaktohet.

30
00:01:14,880 --> 00:01:18,202
Pra, nëse ju jeni të njohur me këtë
nga klasa matematikë shumë vite më parë,

31
00:01:18,202 --> 00:01:20,910
Ka diçka të quajtur
funksionin faktorial, e cila është zakonisht

32
00:01:20,910 --> 00:01:25,340
shënohet si një pikë thirrje, e cila
është përcaktuar mbi të gjitha integers pozitiv.

33
00:01:25,340 --> 00:01:28,850
Dhe mënyra se n
faktorial llogaritet

34
00:01:28,850 --> 00:01:31,050
po ju shumohen gjithë
numrat më pak se

35
00:01:31,050 --> 00:01:33,750
ose e barabartë me together-- n
të gjitha integers më pak se

36
00:01:33,750 --> 00:01:34,880
ose e barabartë me n bashku.

37
00:01:34,880 --> 00:01:39,850
>> Pra 5 faktorial është 5 herë
4 herë 3 herë 2 herë 1.

38
00:01:39,850 --> 00:01:43,020
Dhe 4 faktorial është 4 herë
3 herë 2 herë 1 dhe kështu me radhë.

39
00:01:43,020 --> 00:01:44,800
Ju merrni ide.

40
00:01:44,800 --> 00:01:47,060
>> Si programuesit, ne nuk e bëjmë
përdorin N, pikë thirrje.

41
00:01:47,060 --> 00:01:51,840
Pra, ne do të definojnë faktorial
funksionojnë si fakt i n.

42
00:01:51,840 --> 00:01:56,897
Dhe ne do të përdorim faktorial për të krijuar
një zgjidhje rekursive për një problem.

43
00:01:56,897 --> 00:01:59,230
Dhe unë mendoj se ju mund të gjeni
se kjo është një shumë më me sy

44
00:01:59,230 --> 00:02:02,380
tërheqës se përsëritës
version i kësaj, që

45
00:02:02,380 --> 00:02:05,010
ne gjithashtu do të marrë një sy në në një moment.

46
00:02:05,010 --> 00:02:08,310
>> Pra, këtu janë disa
pun facts-- intended--

47
00:02:08,310 --> 00:02:10,169
për factorial--
funksioni faktorial.

48
00:02:10,169 --> 00:02:13,090
Faktorial i 1, siç thashë, është 1.

49
00:02:13,090 --> 00:02:15,690
Faktorial i 2 është 2 herë 1.

50
00:02:15,690 --> 00:02:18,470
Faktorial i 3 është 3
herë 2 herë 1, dhe kështu me radhë.

51
00:02:18,470 --> 00:02:20,810
Ne biseduam në lidhje me 4 dhe 5 tashmë.

52
00:02:20,810 --> 00:02:23,940
>> Por duke kërkuar në këtë, nuk është kjo e vërtetë?

53
00:02:23,940 --> 00:02:28,220
A nuk faktorial i 2 vetëm
2 herë faktoriale e 1?

54
00:02:28,220 --> 00:02:31,130
Unë do të thotë, faktorial i 1 është 1.

55
00:02:31,130 --> 00:02:34,940
Pra, pse nuk mund të them vetëm se,
pasi faktorial i 2 është 2 herë 1,

56
00:02:34,940 --> 00:02:38,520
kjo është me të vërtetë vetëm 2 herë
faktorial i 1?

57
00:02:38,520 --> 00:02:40,900
>> Dhe pastaj zgjeruar këtë ide,
nuk është faktorial i 3

58
00:02:40,900 --> 00:02:44,080
vetëm 3 herë faktoriale e 2?

59
00:02:44,080 --> 00:02:50,350
Dhe faktorial i 4 është 4 herë
faktorial i 3, dhe kështu me radhë?

60
00:02:50,350 --> 00:02:52,530
Në fakt, faktorial
e çdo numër mund vetëm

61
00:02:52,530 --> 00:02:54,660
të shprehet nëse ne lloj
e kryer këtë përgjithmonë.

62
00:02:54,660 --> 00:02:56,870
Ne mund të lloj të përgjithësoj
problemi faktorial

63
00:02:56,870 --> 00:02:59,910
pasi ajo është n herë e
faktorial i n minus 1.

64
00:02:59,910 --> 00:03:04,840
Është n herë produkt i
të gjithë numrat më pak se unë.

65
00:03:04,840 --> 00:03:08,890
>> Kjo ide, kjo
përgjithësimi i problemit,

66
00:03:08,890 --> 00:03:13,410
na lejon të Recursively
përcaktojë funksionin faktorial.

67
00:03:13,410 --> 00:03:15,440
Kur ju përcaktoni një funksion
Recursively, ka

68
00:03:15,440 --> 00:03:17,470
dy gjëra që duhet të jetë një pjesë e saj.

69
00:03:17,470 --> 00:03:20,990
Ju duhet të keni diçka që quhet një
rasti bazë, e cila, kur ju shkaktojnë atë,

70
00:03:20,990 --> 00:03:22,480
do të ndalojë procesin gjithkund rekursive.

71
00:03:22,480 --> 00:03:25,300
>> Përndryshe, një funksion që e quan
vetvetiu më si ju mund të imagine--

72
00:03:25,300 --> 00:03:26,870
mund të vazhdojë përgjithmonë.

73
00:03:26,870 --> 00:03:29,047
Funksioni i quan funksionin
thërret thirrjet funksion

74
00:03:29,047 --> 00:03:30,380
funksioni quan funksionin.

75
00:03:30,380 --> 00:03:32,380
Nëse ju nuk keni një mënyrë
për ta ndaluar atë, programin tuaj

76
00:03:32,380 --> 00:03:34,760
do të mbërthyer në mënyrë efektive
në një lak të pafund.

77
00:03:34,760 --> 00:03:37,176
Ajo do të rrëzimit përfundimisht,
për shkak se ajo do të dalë jashtë kujtesës.

78
00:03:37,176 --> 00:03:38,990
Por kjo është jashtë diskutimit.

79
00:03:38,990 --> 00:03:42,210
>> Ne duhet të kemi disa rrugë të tjera për të ndaluar
gjëra përveç crashing tonë të programit,

80
00:03:42,210 --> 00:03:46,010
sepse një program që punon është i
ndoshta jo i bukur apo elegante.

81
00:03:46,010 --> 00:03:47,690
Dhe kështu që ne e quajmë këtë rast bazë.

82
00:03:47,690 --> 00:03:50,610
Kjo është një zgjidhje e thjeshtë
një problem i cili ndalon

83
00:03:50,610 --> 00:03:52,770
procesi rekursive nga ndodhin.

84
00:03:52,770 --> 00:03:55,220
Pra, kjo është një pjesë e
një funksion gjithkund rekursive.

85
00:03:55,220 --> 00:03:56,820
>> Pjesa e dytë është rasti rekursive.

86
00:03:56,820 --> 00:03:59,195
Dhe ky është vendi ku recursion
në fakt do të zhvillohet.

87
00:03:59,195 --> 00:04:02,200
Ky është vendi ku
Funksioni do të thërrasë vetë.

88
00:04:02,200 --> 00:04:05,940
>> Kjo nuk do të thërrasë veten pikërisht në
në të njëjtën mënyrë ajo u quajt.

89
00:04:05,940 --> 00:04:08,880
Ajo do të jetë një ndryshim të vogël
që e bën problemin kjo është

90
00:04:08,880 --> 00:04:11,497
duke u përpjekur për të zgjidhur pak vockël i vogël.

91
00:04:11,497 --> 00:04:14,330
Por ajo në përgjithësi kalon dollar
e zgjidhjes pjesa më e madhe e zgjidhjes

92
00:04:14,330 --> 00:04:17,450
në një telefonatë tjetër poshtë vijës.

93
00:04:17,450 --> 00:04:20,290
>> Cila nga këto duket
si rastin bazë këtu?

94
00:04:20,290 --> 00:04:25,384
Cili prej këtyre duket si
Zgjidhja më e thjeshtë për një problem?

95
00:04:25,384 --> 00:04:27,550
Ne kemi një bandë e factorials,
dhe ne mund të vazhdojë

96
00:04:27,550 --> 00:04:30,470
do on-- 6, 7, 8, 9, 10, dhe kështu me radhë.

97
00:04:30,470 --> 00:04:34,130
>> Por një prej këtyre duket si një
rast i mirë që të jetë rasti bazë.

98
00:04:34,130 --> 00:04:35,310
Kjo është një zgjidhje shumë e thjeshtë.

99
00:04:35,310 --> 00:04:37,810
Ne nuk duhet të bëjmë ndonjë gjë të veçantë.

100
00:04:37,810 --> 00:04:40,560
>> Faktorial i 1 është vetëm 1.

101
00:04:40,560 --> 00:04:42,790
Ne nuk duhet të bëjmë ndonjë
shumëzimin në të gjitha.

102
00:04:42,790 --> 00:04:45,248
Duket si në qoftë se ne jemi duke shkuar
për të provoni dhe zgjidhur këtë problem,

103
00:04:45,248 --> 00:04:47,600
dhe ne kemi nevojë për të ndaluar
Recursion diku,

104
00:04:47,600 --> 00:04:50,610
ne ndoshta dëshironi të ndaluar
ajo kur ne të merrni për 1.

105
00:04:50,610 --> 00:04:54,580
Ne nuk duam të ndalet para se.

106
00:04:54,580 --> 00:04:56,660
>> Pra, nëse ne jemi duke përcaktuar
Funksioni ynë faktorial,

107
00:04:56,660 --> 00:04:58,690
këtu është një skelet për
se si ne mund të bëjmë atë.

108
00:04:58,690 --> 00:05:03,110
Ne duhet të plug në ato dy things--
rasti bazë dhe rasti rekursive.

109
00:05:03,110 --> 00:05:04,990
Çfarë është rasti bazë?

110
00:05:04,990 --> 00:05:10,150
Nëse n është e barabartë me 1, që është kthyer 1--
një problem të vërtetë të thjeshtë për të zgjidhur.

111
00:05:10,150 --> 00:05:11,890
>> Faktorial i 1 është 1.

112
00:05:11,890 --> 00:05:13,860
Kjo nuk është 1 herë çdo gjë.

113
00:05:13,860 --> 00:05:15,020
Është vetëm 1.

114
00:05:15,020 --> 00:05:17,170
Është një fakt shumë e lehtë.

115
00:05:17,170 --> 00:05:19,620
Dhe kështu që mund të jetë rasti ynë bazë.

116
00:05:19,620 --> 00:05:24,730
Në qoftë se ne të merrni kaluar 1 në këtë
funksion, ne do të kthehen vetëm 1.

117
00:05:24,730 --> 00:05:27,320
>> Çfarë është gjithkund rekursive
Rasti ndoshta duken si?

118
00:05:27,320 --> 00:05:32,445
Për çdo numër tjetër
përveç 1, çfarë është model?

119
00:05:32,445 --> 00:05:35,780
E pra, në qoftë se ne jemi duke marrë
faktorial i N,

120
00:05:35,780 --> 00:05:38,160
ajo është herë n faktorial i n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Nëse ne jemi duke marrë faktorial i 3,
kjo është 3 herë faktorial i 3 minus 1,

122
00:05:42,130 --> 00:05:43,070
ose 2.

123
00:05:43,070 --> 00:05:47,330
Dhe kështu që në qoftë se ne nuk jemi
duke kërkuar në 1, ndryshe

124
00:05:47,330 --> 00:05:51,710
Kthimi n herë e
faktorial i n minus 1.

125
00:05:51,710 --> 00:05:53,210
Është shumë i thjeshtë.

126
00:05:53,210 --> 00:05:57,360
>> Dhe për hir të pasurit pak
pastër dhe kodin më elegante,

127
00:05:57,360 --> 00:06:01,440
e di se në qoftë se ne kemi sythe vetme-line
apo vetme-line degët kushtëzuara,

128
00:06:01,440 --> 00:06:04,490
ne mund të shpëtoj nga të gjitha të
formatimin e teksteve kaçurrel rreth tyre.

129
00:06:04,490 --> 00:06:06,850
Pra, ne mund të konsoliduar këtë për këtë.

130
00:06:06,850 --> 00:06:09,640
Kjo ka të njëjtë
Funksionalitetin si kjo.

131
00:06:09,640 --> 00:06:13,850
>> Unë jam vetëm duke larguar kaçurrel
formatimin e teksteve, sepse ka vetëm një linjë

132
00:06:13,850 --> 00:06:18,500
brenda këtyre degëve të kushtëzuara.

133
00:06:18,500 --> 00:06:21,160
Pra, këto sillen njëlloj.

134
00:06:21,160 --> 00:06:23,800
Nëse n është e barabartë me 1, kthehen 1.

135
00:06:23,800 --> 00:06:28,351
Përndryshe kthehen herë n
faktorial i n minus 1.

136
00:06:28,351 --> 00:06:29,850
Pra, ne jemi duke e bërë problem më i vogël.

137
00:06:29,850 --> 00:06:33,850
Nëse n fillon si 5, ne jemi duke shkuar për
kthimin 5 herë faktoriale e 4.

138
00:06:33,850 --> 00:06:37,100
Dhe ne do të shohim në një minutë kur flasim
rreth stack-- thirrjes në një tjetër video

139
00:06:37,100 --> 00:06:39,390
ku ne flasim për
quajmë stack-- ne do të mësoni

140
00:06:39,390 --> 00:06:41,630
se pse pikërisht ky proces funksionon.

141
00:06:41,630 --> 00:06:46,970
>> Por, ndërsa faktorial i 5 thotë
kthehen 5 herë faktorial i 4, dhe 4

142
00:06:46,970 --> 00:06:49,710
do të thotë, OK, mirë, kthimi
4 herë faktoriale e 3.

143
00:06:49,710 --> 00:06:51,737
Dhe si ju mund të shihni, ne jemi
lloj i afrohet 1.

144
00:06:51,737 --> 00:06:53,820
Ne jemi duke iu afruar dhe
më afër me atë rastin bazë.

145
00:06:53,820 --> 00:06:58,180
>> Dhe një herë ne goditi rastin bazë,
të gjithë nga funksionet e mëparshme

146
00:06:58,180 --> 00:07:00,540
kanë përgjigjen ata po kërkoni.

147
00:07:00,540 --> 00:07:03,900
Faktorial i 2 thoshte kthim
2 herë faktoriale e 1.

148
00:07:03,900 --> 00:07:06,760
E pra, faktorial e 1 kthimit 1.

149
00:07:06,760 --> 00:07:10,090
Pra, thirrja për faktorial
e 2 mund të kthehen 2 herë 1,

150
00:07:10,090 --> 00:07:13,980
dhe jap atë përsëri në faktorial të
3, e cila është duke pritur për atë rezultat.

151
00:07:13,980 --> 00:07:17,110
>> Dhe atëherë ajo mund të llogarisë
rezultat e tij, 3 herë 2 është 6,

152
00:07:17,110 --> 00:07:18,907
dhe të japë atë përsëri në faktoriale e 4.

153
00:07:18,907 --> 00:07:20,740
Dhe përsëri, ne kemi një
Video në thirrje rafte

154
00:07:20,740 --> 00:07:23,810
ku kjo është e ilustruar pak
më shumë se ajo që unë jam duke thënë se të drejtë tani.

155
00:07:23,810 --> 00:07:25,300
Por kjo është ajo.

156
00:07:25,300 --> 00:07:29,300
Kjo vetëm është zgjidhje për
llogaritjen e faktorial e një numri.

157
00:07:29,300 --> 00:07:31,527
>> Është vetëm katër rreshta të kodit.

158
00:07:31,527 --> 00:07:32,610
Kjo është pretty cool, e drejtë?

159
00:07:32,610 --> 00:07:35,480
Kjo është lloj i sexy.

160
00:07:35,480 --> 00:07:38,580
>> Pra në përgjithësi, por jo
gjithmonë, një funksion gjithkund rekursive

161
00:07:38,580 --> 00:07:41,190
mund të zëvendësojë një lak në një
jo-funksion gjithkund rekursive.

162
00:07:41,190 --> 00:07:46,100
Kështu që këtu, krah për krah, është përsëritës
Versioni i funksionit faktorial.

163
00:07:46,100 --> 00:07:49,650
Të dyja këto Llogarit
saktësisht e njëjta gjë.

164
00:07:49,650 --> 00:07:52,170
>> Ata të dy llogaritur faktoriale e n.

165
00:07:52,170 --> 00:07:54,990
Versioni në të majtë
përdor recursion për të bërë atë.

166
00:07:54,990 --> 00:07:58,320
Versioni në të djathtë
përdor përsëritje për të bërë atë.

167
00:07:58,320 --> 00:08:02,050
>> Dhe vini re, ne duhet të deklarojnë
një variabël një produkt numër të plotë.

168
00:08:02,050 --> 00:08:02,940
Dhe pastaj ne lak.

169
00:08:02,940 --> 00:08:06,790
Aq sa n është më i madh se 0, ne
mbajtur shumëzuar se produkti me n

170
00:08:06,790 --> 00:08:09,890
dhe decrementing n deri
ne llogarisim produktin.

171
00:08:09,890 --> 00:08:14,600
Pra, këto dy funksione, përsëri,
bëjnë pikërisht të njëjtën gjë.

172
00:08:14,600 --> 00:08:19,980
Por ata nuk e bëjmë atë në
saktësisht në të njëjtën mënyrë.

173
00:08:19,980 --> 00:08:22,430
>> Tani, është e mundur të
kanë më shumë se një bazë

174
00:08:22,430 --> 00:08:25,770
rast ose me teper se nje
rast gjithkund rekursive, në varësi

175
00:08:25,770 --> 00:08:27,670
në çfarë funksioni juaj është duke u përpjekur për të bërë.

176
00:08:27,670 --> 00:08:31,650
Ju nuk janë domosdo të kufizuara vetëm për të
një rast i vetëm bazë ose një rekursive vetme

177
00:08:31,650 --> 00:08:32,370
rast.

178
00:08:32,370 --> 00:08:35,320
Pra, një shembull i diçkaje
me raste të shumta bazë

179
00:08:35,320 --> 00:08:37,830
mund të jetë this--
Fibonacci rend numër.

180
00:08:37,830 --> 00:08:41,549
>> Ju mund të kujtojnë nga
ditë shkolle fillore

181
00:08:41,549 --> 00:08:45,740
se Fibonacci sequence është përcaktuar
si this-- elementi i parë është 0.

182
00:08:45,740 --> 00:08:46,890
Elementi i dytë është 1.

183
00:08:46,890 --> 00:08:49,230
Të dyja këto janë vetëm sipas definicionit.

184
00:08:49,230 --> 00:08:55,920
>> Atëherë çdo element tjetër është përcaktuar
si shuma n minus 1 dhe n minus 2.

185
00:08:55,920 --> 00:09:00,330
Pra, elementi i tretë
do të jetë 0 plus 1 është 1.

186
00:09:00,330 --> 00:09:03,280
Dhe pastaj elementi i katërt
do të jetë elementi i dytë, 1,

187
00:09:03,280 --> 00:09:06,550
plus elementi i tretë, 1.

188
00:09:06,550 --> 00:09:08,507
Dhe kjo do të jetë 2.

189
00:09:08,507 --> 00:09:09,340
Dhe kështu me radhë e kështu me radhë.

190
00:09:09,340 --> 00:09:11,680
>> Pra, në këtë rast, ne kemi dy raste bazë.

191
00:09:11,680 --> 00:09:14,850
Nëse n është e barabartë me 1, kthehen 0.

192
00:09:14,850 --> 00:09:18,560
Nëse n është e barabartë me 2, kthehen 1.

193
00:09:18,560 --> 00:09:25,930
Përndryshe, kthimin Fibonacci të n
minus 1 plus Fibonacci i n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Pra, kjo është raste të shumta bazë.

195
00:09:27,180 --> 00:09:29,271
Po në lidhje me raste të shumta gjithkund rekursive?

196
00:09:29,271 --> 00:09:31,520
E pra, ka diçka
quajtur hamendje Collatz.

197
00:09:31,520 --> 00:09:34,630
Unë nuk jam duke shkuar për të thënë,
ju e dini se çka është,

198
00:09:34,630 --> 00:09:38,170
sepse kjo është në fakt finale ynë
Problemi për këtë video të veçantë.

199
00:09:38,170 --> 00:09:43,220
Dhe kjo është ushtrim ynë
për të punuar së bashku.

200
00:09:43,220 --> 00:09:46,760
>> Kështu që këtu është ajo që
Collatz hamendje is--

201
00:09:46,760 --> 00:09:48,820
kjo vlen për çdo numër i plotë pozitiv.

202
00:09:48,820 --> 00:09:51,500
Dhe kjo spekulon se kjo është
gjithmonë e mundur për të marrë përsëri

203
00:09:51,500 --> 00:09:55,060
për 1 nëse ju do të ndiqni këto hapa.

204
00:09:55,060 --> 00:09:57,560
Nëse n është 1, të ndaluar.

205
00:09:57,560 --> 00:10:00,070
Ne kemi marrë përsëri në 1 nëse n është 1.

206
00:10:00,070 --> 00:10:05,670
>> Përndryshe, kalojnë nëpër këtë
Procesi përsëri në n ndarë nga 2.

207
00:10:05,670 --> 00:10:08,200
Dhe shihni nëse ju mund të merrni përsëri në 1.

208
00:10:08,200 --> 00:10:13,260
Përndryshe, nëse n është i rastësishëm, të shkojnë nëpër
ky proces përsëri në 3N plus 1,

209
00:10:13,260 --> 00:10:15,552
ose 3 herë n plus 1.

210
00:10:15,552 --> 00:10:17,010
Pra, këtu ne kemi një rast të vetëm bazë.

211
00:10:17,010 --> 00:10:18,430
Nëse n është e barabartë me 1, të ndaluar.

212
00:10:18,430 --> 00:10:20,230
Ne nuk jemi duke bërë ndonjë recursion më shumë.

213
00:10:20,230 --> 00:10:23,730
>> Por ne kemi dy raste gjithkund rekursive.

214
00:10:23,730 --> 00:10:28,750
Nëse n është edhe më, ne bëjmë një rekursive
rast, duke e quajtur n ndarë nga 2.

215
00:10:28,750 --> 00:10:33,950
Nëse n është i rastësishëm, ne bëjmë një tjetër
Rasti rekursive mbi 3 herë n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> Dhe kështu qëllimi për këtë video është
për të marrë një të dytë, pauzë video,

217
00:10:39,120 --> 00:10:42,440
dhe të përpiqen dhe të shkruaj kjo
funksioni rekursiv Collatz

218
00:10:42,440 --> 00:10:47,640
ku ju të kalojë në një n vlerës, dhe
ajo llogarit sa hapa ajo

219
00:10:47,640 --> 00:10:52,430
merr për të marrë me 1 nëse ju filloni nga n
dhe ju do të ndiqni këto hapa lart.

220
00:10:52,430 --> 00:10:56,660
Nëse n është 1, merr 0 hapa.

221
00:10:56,660 --> 00:11:00,190
Përndryshe, ajo do të
marrë një hap plus megjithatë

222
00:11:00,190 --> 00:11:06,200
shumë hapa ajo merr në të dyja n
ndarë nga 2, nëse n është edhe më, ose 3N plus 1

223
00:11:06,200 --> 00:11:08,100
nëse n është i rastësishëm.

224
00:11:08,100 --> 00:11:11,190
>> Tani, unë e kam vënë në ekran këtu
disa gjëra test për ju,

225
00:11:11,190 --> 00:11:15,690
një çift i testeve rasteve për ju, për të parë
çfarë këto shifra të ndryshme Collatz janë,

226
00:11:15,690 --> 00:11:17,440
dhe gjithashtu një ilustrim
nga hapat që

227
00:11:17,440 --> 00:11:20,390
duhet të jetë zhdukur nëpër kështu që ju mund
lloj e shohin këtë proces në veprim.

228
00:11:20,390 --> 00:11:24,222
Kështu që nëse n është e barabartë me
1, Collatz prej n eshte 0.

229
00:11:24,222 --> 00:11:26,180
Ju nuk keni për të bërë
çdo gjë për të marrë përsëri në 1.

230
00:11:26,180 --> 00:11:27,600
Ju jeni tashmë atje.

231
00:11:27,600 --> 00:11:30,550
>> Nëse n është 2, merr
një hap për të marrë në 1.

232
00:11:30,550 --> 00:11:31,810
Ju filloni me 2.

233
00:11:31,810 --> 00:11:33,100
Dhe, 2 nuk është e barabartë me 1.

234
00:11:33,100 --> 00:11:36,580
Pra, kjo do të jetë një hap
plus megjithatë shumë hapat që

235
00:11:36,580 --> 00:11:38,015
merr n ndarë nga 2.

236
00:11:38,015 --> 00:11:41,280

237
00:11:41,280 --> 00:11:42,910
>> 2 ndarë nga 2 është 1.

238
00:11:42,910 --> 00:11:47,200
Pra, ajo merr një hap plus megjithatë
shumë hapa ajo merr për 1.

239
00:11:47,200 --> 00:11:49,720
1 merr zero hapa.

240
00:11:49,720 --> 00:11:52,370
>> Për 3, siç mund ta shihni, nuk ka
mjaft disa hapa të përfshirë.

241
00:11:52,370 --> 00:11:53,590
Ju shkoni nga 3.

242
00:11:53,590 --> 00:11:56,710
Dhe pastaj ju shkoni në
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Ajo merr shtatë hapa për të marrë përsëri në 1.

244
00:11:58,804 --> 00:12:01,220
Dhe si ju mund të shihni, ka një
çift ​​raste të tjera provë këtu

245
00:12:01,220 --> 00:12:02,470
për të provuar programin tuaj.

246
00:12:02,470 --> 00:12:03,970
Pra, përsëri, pauzë video.

247
00:12:03,970 --> 00:12:09,210
Dhe unë do të shkoj hidhen përsëri tani për
çfarë procesi aktual është këtu,

248
00:12:09,210 --> 00:12:11,390
ajo që kjo hamendje është.

249
00:12:11,390 --> 00:12:14,140
>> Shih nëse ju mund të kuptoj se
si për të përcaktuar Collatz të n

250
00:12:14,140 --> 00:12:19,967
në mënyrë që ajo llogarit se sa shumë
hapa që duhet për të marrë në 1.

251
00:12:19,967 --> 00:12:23,050
Kështu që shpresojmë se, ju keni ndaluar video
dhe ju nuk jeni vetëm duke pritur për mua

252
00:12:23,050 --> 00:12:25,820
për të ju jap përgjigje këtu.

253
00:12:25,820 --> 00:12:29,120
Por nëse ju jeni, mirë,
këtu është përgjigje gjithsesi.

254
00:12:29,120 --> 00:12:33,070
>> Kështu që këtu është një përkufizim i mundshëm
e funksionit Collatz.

255
00:12:33,070 --> 00:12:35,610
Baza jonë case-- nëse n është
barabarte me 1, ne kthim 0.

256
00:12:35,610 --> 00:12:38,250
Ajo nuk ka marrë ndonjë
hapa për të marrë përsëri në 1.

257
00:12:38,250 --> 00:12:42,710
>> Përndryshe, ne kemi dy cases-- gjithkund rekursive
një për edhe numrat dhe një për rastësishëm.

258
00:12:42,710 --> 00:12:47,164
Mënyrën se si unë testuar edhe për numrat
është për të kontrolluar nëse n mod 2 është e barabartë me 0.

259
00:12:47,164 --> 00:12:49,080
Kjo është në thelb, përsëri,
duke i kërkuar pyetjen,

260
00:12:49,080 --> 00:12:54,050
në qoftë se ju kujtohet is-- çfarë mod nëse unë
ndani n nga 2 është atje ka mbetur?

261
00:12:54,050 --> 00:12:55,470
Kjo do të jetë një numër çift.

262
00:12:55,470 --> 00:13:01,370
>> Dhe kështu që nëse n mod 2 është e barabartë me 0 është
Testimi është ky një numër edhe më.

263
00:13:01,370 --> 00:13:04,250
Nëse është kështu, unë dua të kthehen 1,
sepse kjo është padyshim

264
00:13:04,250 --> 00:13:09,270
duke marrë një hap plus Collatz e
çfarëdo numri është gjysma e mua.

265
00:13:09,270 --> 00:13:13,910
Përndryshe, unë dua të kthehen 1
plus Collatz e 3 herë n plus 1.

266
00:13:13,910 --> 00:13:16,060
Kjo ishte tjetri
hap rekursive që ne

267
00:13:16,060 --> 00:13:19,470
mund të marrë për të llogaritur
Collatz-- numrin e hapave

268
00:13:19,470 --> 00:13:22,610
ajo merr për të marrë përsëri
për 1 jepet një numër.

269
00:13:22,610 --> 00:13:24,610
Kështu që shpresojmë se, ky shembull
ju dha pak

270
00:13:24,610 --> 00:13:26,620
e një shije të procedurave gjithkund rekursive.

271
00:13:26,620 --> 00:13:30,220
Shpresojmë, ju mendoni se është një kod
pak më të bukur në qoftë se zbatohet

272
00:13:30,220 --> 00:13:32,760
në një mënyrë elegante, gjithkund rekursive.

273
00:13:32,760 --> 00:13:35,955
Por edhe në qoftë se nuk, recursion është një
mjet të vërtetë i fuqishëm megjithatë.

274
00:13:35,955 --> 00:13:38,330
Dhe kështu kjo është patjetër diçka
për të marrë kokën tuaj rreth,

275
00:13:38,330 --> 00:13:41,360
sepse ju do të jetë në gjendje të krijojë
Programet pretty cool përdorur recursion

276
00:13:41,360 --> 00:13:45,930
që përndryshe mund të jetë i ndërlikuar për të shkruar
në qoftë se ju jeni duke përdorur sythe dhe përsëritje.

277
00:13:45,930 --> 00:13:46,980
Unë jam Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Kjo është CS50.

279
00:13:48,780 --> 00:13:50,228