1
00:00:00,000 --> 00:00:05,860
>> [MUSIK SPELA]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Du tror nog att
kod bara för att utföra en uppgift.

3
00:00:09,530 --> 00:00:10,450
Du skriver ut det.

4
00:00:10,450 --> 00:00:11,664
Det gör något.

5
00:00:11,664 --> 00:00:12,580
Det är ganska mycket det.

6
00:00:12,580 --> 00:00:13,160
>> Du kompilera den.

7
00:00:13,160 --> 00:00:13,993
Du kör programmet.

8
00:00:13,993 --> 00:00:15,370
Du är bra att gå.

9
00:00:15,370 --> 00:00:17,520
>> Men tro det eller ej, om
du koda för en lång tid,

10
00:00:17,520 --> 00:00:20,550
du faktiskt kan komma att se
kod som något som är vackert.

11
00:00:20,550 --> 00:00:23,275
Den löser ett problem i
ett mycket intressant sätt,

12
00:00:23,275 --> 00:00:26,510
eller finns det bara något riktigt
snyggt om hur det ser ut.

13
00:00:26,510 --> 00:00:28,750
Du kanske skrattar
på mig, men det är sant.

14
00:00:28,750 --> 00:00:31,530
Och rekursion är ett sätt
att typ av få denna idé

15
00:00:31,530 --> 00:00:34,090
vackra, elegant utseende kod.

16
00:00:34,090 --> 00:00:37,740
Det löser problem på ett sätt som
är intressanta, lätt att visualisera,

17
00:00:37,740 --> 00:00:39,810
och överraskande kort.

18
00:00:39,810 --> 00:00:43,190
>> De sätt rekursion fungerar
är, en rekursiv funktion

19
00:00:43,190 --> 00:00:49,291
definieras som en funktion som anropar
sig själv som en del i genomförandet.

20
00:00:49,291 --> 00:00:51,790
Det kan verka lite konstigt,
och vi får se lite

21
00:00:51,790 --> 00:00:53,750
om hur detta fungerar i ett ögonblick.

22
00:00:53,750 --> 00:00:55,560
Men återigen, dessa
rekursiva procedurer är

23
00:00:55,560 --> 00:00:57,730
kommer att bli så elegant
eftersom de ska

24
00:00:57,730 --> 00:01:00,410
att lösa detta problem utan att
ha alla dessa andra funktioner

25
00:01:00,410 --> 00:01:02,710
eller dessa långa slingor.

26
00:01:02,710 --> 00:01:06,310
Du ser att dessa rekursiva
procedurer kommer att se så kort.

27
00:01:06,310 --> 00:01:10,610
Och de verkligen kommer att göra
koden ser mycket vackrare.

28
00:01:10,610 --> 00:01:12,560
>> Jag ska ge er ett exempel
av detta för att se hur

29
00:01:12,560 --> 00:01:14,880
en rekursiv procedur kan definieras.

30
00:01:14,880 --> 00:01:18,202
Så om du är bekant med detta
från klassen Math för många år sedan,

31
00:01:18,202 --> 00:01:20,910
Det finns något som kallas
faktor funktion, som vanligtvis

32
00:01:20,910 --> 00:01:25,340
betecknas som ett utropstecken, vilket
definieras över alla positiva heltal.

33
00:01:25,340 --> 00:01:28,850
Och sättet att n
fakultet beräknas

34
00:01:28,850 --> 00:01:31,050
är du multiplicera alla
talen mindre än

35
00:01:31,050 --> 00:01:33,750
eller lika med n together--
alla heltal mindre än

36
00:01:33,750 --> 00:01:34,880
eller lika med n tillsammans.

37
00:01:34,880 --> 00:01:39,850
>> Så 5 fakultet är 5 gånger
4 gånger 3 gånger 2 gånger 1.

38
00:01:39,850 --> 00:01:43,020
Och 4 fakultet är 4 gånger
3 gånger 2 gånger 1 och så vidare.

39
00:01:43,020 --> 00:01:44,800
Du får idén.

40
00:01:44,800 --> 00:01:47,060
>> Som programmerare, gör vi inte
Använd n, utropstecken.

41
00:01:47,060 --> 00:01:51,840
Så vi ska definiera fakulteten
funktion som ett faktum av n.

42
00:01:51,840 --> 00:01:56,897
Och vi kommer att använda faktor att skapa
en rekursiv lösning på ett problem.

43
00:01:56,897 --> 00:01:59,230
Och jag tror att du kan hitta
att det är en mycket mer visuellt

44
00:01:59,230 --> 00:02:02,380
tilltalande än den iterativa
version av detta, vilket

45
00:02:02,380 --> 00:02:05,010
Vi kommer också att titta på i ett ögonblick.

46
00:02:05,010 --> 00:02:08,310
>> Så här är ett par
facts-- vits intended--

47
00:02:08,310 --> 00:02:10,169
om factorial-- den
fakulteten.

48
00:02:10,169 --> 00:02:13,090
Fakulteten för en, som sagt, är en.

49
00:02:13,090 --> 00:02:15,690
Fakulteten för 2 är 2 gånger 1.

50
00:02:15,690 --> 00:02:18,470
Fakulteten för 3 är 3
gånger 2 gånger 1, och så vidare.

51
00:02:18,470 --> 00:02:20,810
Vi pratade om 4 och 5 redan.

52
00:02:20,810 --> 00:02:23,940
>> Men titta på detta, är inte detta sant?

53
00:02:23,940 --> 00:02:28,220
Är inte fakulteten av 2 bara
2 gånger faktor 1?

54
00:02:28,220 --> 00:02:31,130
Jag menar, är fakulteten av 1 1.

55
00:02:31,130 --> 00:02:34,940
Så varför kan vi inte bara säga att,
eftersom fakulteten av 2 är 2 gånger 1,

56
00:02:34,940 --> 00:02:38,520
Det är egentligen bara 2 gånger
fakulteten för en?

57
00:02:38,520 --> 00:02:40,900
>> Och sedan utvidga den tanken,
är inte fakulteten av 3

58
00:02:40,900 --> 00:02:44,080
bara 3 gånger faktor 2?

59
00:02:44,080 --> 00:02:50,350
Och fakulteten av fyra är 4 gånger
fakulteten av 3, och så vidare?

60
00:02:50,350 --> 00:02:52,530
I själva verket, fakulteten
av valfritt antal kan bara

61
00:02:52,530 --> 00:02:54,660
uttryckas om vi typ
av genomföra detta för alltid.

62
00:02:54,660 --> 00:02:56,870
Vi kan slags generalisera
fakulteten problemet

63
00:02:56,870 --> 00:02:59,910
eftersom det är n gånger
fakulteten av n minus en.

64
00:02:59,910 --> 00:03:04,840
Det är n gånger produkten av
alla nummer mindre än mig.

65
00:03:04,840 --> 00:03:08,890
>> Denna idé, detta
generalisering av problemet,

66
00:03:08,890 --> 00:03:13,410
ger oss möjlighet att rekursivt
definiera fakulteten.

67
00:03:13,410 --> 00:03:15,440
När du definierar en funktion
rekursivt, det finns

68
00:03:15,440 --> 00:03:17,470
två saker som måste vara en del av det.

69
00:03:17,470 --> 00:03:20,990
Du måste ha något som kallas en
basfall, som när du utlösa det,

70
00:03:20,990 --> 00:03:22,480
kommer att stoppa den rekursiva processen.

71
00:03:22,480 --> 00:03:25,300
>> Annars en funktion som anropar
itself-- som du kanske imagine--

72
00:03:25,300 --> 00:03:26,870
skulle kunna fortsätta i evigheter.

73
00:03:26,870 --> 00:03:29,047
Funktionsanrop funktionen
kallar funktionsanrop

74
00:03:29,047 --> 00:03:30,380
funktionen anropar funktionen.

75
00:03:30,380 --> 00:03:32,380
Om du inte har ett sätt
att stoppa det, ditt program

76
00:03:32,380 --> 00:03:34,760
kommer att på ett effektivt sätt fastnat
vid en oändlig slinga.

77
00:03:34,760 --> 00:03:37,176
Det kommer att krascha småningom,
eftersom det kommer att få slut på minne.

78
00:03:37,176 --> 00:03:38,990
Men det är ovidkommande.

79
00:03:38,990 --> 00:03:42,210
>> Vi måste ha något annat sätt att stoppa
saker förutom vårt program kraschar,

80
00:03:42,210 --> 00:03:46,010
eftersom ett program som kraschar är
förmodligen inte vacker eller elegant.

81
00:03:46,010 --> 00:03:47,690
Och så vi kallar detta basfall.

82
00:03:47,690 --> 00:03:50,610
Detta är en enkel lösning
ett problem som stannar

83
00:03:50,610 --> 00:03:52,770
den rekursiva processen uppstår.

84
00:03:52,770 --> 00:03:55,220
Så det är en del av
en rekursiv funktion.

85
00:03:55,220 --> 00:03:56,820
>> Den andra delen är den rekursiva fallet.

86
00:03:56,820 --> 00:03:59,195
Och det är där rekursion
faktiskt kommer att äga rum.

87
00:03:59,195 --> 00:04:02,200
Det är där
funktionen kalla sig.

88
00:04:02,200 --> 00:04:05,940
>> Det kommer inte att kalla sig på exakt
på samma sätt som det hette.

89
00:04:05,940 --> 00:04:08,880
Det blir en liten variation
som gör problemet är det

90
00:04:08,880 --> 00:04:11,497
försöker lösa ett pyttelitet lite mindre.

91
00:04:11,497 --> 00:04:14,330
Men den passerar allmänhet buck
att lösa huvuddelen av lösningen

92
00:04:14,330 --> 00:04:17,450
till en annan samtals fram.

93
00:04:17,450 --> 00:04:20,290
>> Vilken av dessa ser
som grund fallet här?

94
00:04:20,290 --> 00:04:25,384
Vilken av dessa ser ut som den
enklaste lösningen på ett problem?

95
00:04:25,384 --> 00:04:27,550
Vi har ett gäng faktorial,
och vi kunde fortsätta

96
00:04:27,550 --> 00:04:30,470
gå on-- 6, 7, 8, 9, 10, och så vidare.

97
00:04:30,470 --> 00:04:34,130
>> Men en av dessa ser ut som en
bra fall för att vara basen fallet.

98
00:04:34,130 --> 00:04:35,310
Det är en mycket enkel lösning.

99
00:04:35,310 --> 00:04:37,810
Vi behöver inte göra något speciellt.

100
00:04:37,810 --> 00:04:40,560
>> Fakulteten för en är bara en.

101
00:04:40,560 --> 00:04:42,790
Vi behöver inte göra något
multiplikation alls.

102
00:04:42,790 --> 00:04:45,248
Det verkar som om vi tänker
att försöka lösa detta problem,

103
00:04:45,248 --> 00:04:47,600
och vi måste stoppa
rekursion någonstans,

104
00:04:47,600 --> 00:04:50,610
vi förmodligen vill sluta
det när vi kommer till en.

105
00:04:50,610 --> 00:04:54,580
Vi vill inte sluta innan dess.

106
00:04:54,580 --> 00:04:56,660
>> Så om vi definierar
vår faktoriell funktion,

107
00:04:56,660 --> 00:04:58,690
Här är ett skelett för
hur vi kan göra det.

108
00:04:58,690 --> 00:05:03,110
Vi måste koppla in dessa två saker--
basfallet och rekursiva fallet.

109
00:05:03,110 --> 00:05:04,990
Vad är basen fallet?

110
00:05:04,990 --> 00:05:10,150
Om n är lika med ett, retur 1-- det är
ett riktigt enkelt problem att lösa.

111
00:05:10,150 --> 00:05:11,890
>> Fakulteten för 1 är en.

112
00:05:11,890 --> 00:05:13,860
Det är inte 1 gånger någonting.

113
00:05:13,860 --> 00:05:15,020
Det är bara en.

114
00:05:15,020 --> 00:05:17,170
Det är ett mycket enkelt faktum.

115
00:05:17,170 --> 00:05:19,620
Och så det kan vara vår bas fallet.

116
00:05:19,620 --> 00:05:24,730
Om vi ​​få passerat 1 till detta
funktion, kommer vi bara tillbaka en.

117
00:05:24,730 --> 00:05:27,320
>> Vad är den rekursiva
väska antagligen ut?

118
00:05:27,320 --> 00:05:32,445
För varje annat nummer
förutom ett, vad är mönstret?

119
00:05:32,445 --> 00:05:35,780
Tja, om vi tar
fakulteten av n,

120
00:05:35,780 --> 00:05:38,160
det är n gånger fakulteten av n minus en.

121
00:05:38,160 --> 00:05:42,130
>> Om vi ​​tar fakulteten av 3
Det är 3 gånger fakulteten av 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
Och så om vi inte
tittar på en, annars

124
00:05:47,330 --> 00:05:51,710
retur N gånger
fakulteten av n minus en.

125
00:05:51,710 --> 00:05:53,210
Det är ganska enkelt.

126
00:05:53,210 --> 00:05:57,360
>> Och för den skull ha något
renare och mer elegant kod,

127
00:05:57,360 --> 00:06:01,440
vet att om vi har en enda rad slingor
eller enradig villkorliga grenar,

128
00:06:01,440 --> 00:06:04,490
vi kan bli av med alla de
klamrar runt dem.

129
00:06:04,490 --> 00:06:06,850
Så vi kan konsolidera denna till detta.

130
00:06:06,850 --> 00:06:09,640
Detta har exakt samma
funktion som redan.

131
00:06:09,640 --> 00:06:13,850
>> Jag bara ta bort lockigt
hängslen, eftersom det bara finns en rad

132
00:06:13,850 --> 00:06:18,500
insidan av dessa villkorliga förgreningar.

133
00:06:18,500 --> 00:06:21,160
Så dessa beter sig på samma sätt.

134
00:06:21,160 --> 00:06:23,800
Om n är lika med 1, returnera ett.

135
00:06:23,800 --> 00:06:28,351
Annars åter n gånger
fakulteten av n minus 1.

136
00:06:28,351 --> 00:06:29,850
Så vi gör problemet mindre.

137
00:06:29,850 --> 00:06:33,850
Om n börjar som 5, ska vi
tillbaka 5 gånger fakulteten av fyra.

138
00:06:33,850 --> 00:06:37,100
Och vi får se i en minut när vi talar
om samtalet stack-- i en annan video

139
00:06:37,100 --> 00:06:39,390
där vi talar om
Ring stack-- vi lär

140
00:06:39,390 --> 00:06:41,630
om varför just den här processen fungerar.

141
00:06:41,630 --> 00:06:46,970
>> Men medan fakulteten av 5 säger
tillbaka 5 gånger fakulteten av fyra, och fyra

142
00:06:46,970 --> 00:06:49,710
kommer att säga, OK, ja, retur
4 gånger faktor 3.

143
00:06:49,710 --> 00:06:51,737
Och som ni kan se, vi är
sorts närmar 1.

144
00:06:51,737 --> 00:06:53,820
Vi får närmare och
närmare den basfall.

145
00:06:53,820 --> 00:06:58,180
>> Och när vi slog basfallet,
alla de tidigare funktionerna

146
00:06:58,180 --> 00:07:00,540
har svaret de letade efter.

147
00:07:00,540 --> 00:07:03,900
Fakulteten av 2 sade avkastning
2 gånger faktor 1.

148
00:07:03,900 --> 00:07:06,760
Tja, fakulteten för 1 returnerar 1.

149
00:07:06,760 --> 00:07:10,090
Så uppmaningen till fakulteten
2 kan återvända 2 gånger 1,

150
00:07:10,090 --> 00:07:13,980
och ge det tillbaka till fakulteten av
3, som väntar på det resultatet.

151
00:07:13,980 --> 00:07:17,110
>> Och då kan det beräkna
dess resultat, 3 gånger 2 är 6,

152
00:07:17,110 --> 00:07:18,907
och ge det tillbaka till fakulteten av fyra.

153
00:07:18,907 --> 00:07:20,740
Och återigen, vi har en
video på anropsstacken

154
00:07:20,740 --> 00:07:23,810
där detta illustreras lite
mer än vad jag säger just nu.

155
00:07:23,810 --> 00:07:25,300
Men det är det.

156
00:07:25,300 --> 00:07:29,300
Bara detta är lösningen på
beräkna fakulteten för ett tal.

157
00:07:29,300 --> 00:07:31,527
>> Det är bara fyra rader kod.

158
00:07:31,527 --> 00:07:32,610
Det är ganska coolt, va?

159
00:07:32,610 --> 00:07:35,480
Det finns en slags sexig.

160
00:07:35,480 --> 00:07:38,580
>> Så i allmänhet, men inte
alltid, en rekursiv funktion

161
00:07:38,580 --> 00:07:41,190
kan ersätta en slinga i ett
icke-rekursiv funktion.

162
00:07:41,190 --> 00:07:46,100
Så här, sida vid sida, är den iterativa
versionen av fakulteten.

163
00:07:46,100 --> 00:07:49,650
Båda dessa kalkylera
exakt samma sak.

164
00:07:49,650 --> 00:07:52,170
>> De båda beräkna fakulteten av n.

165
00:07:52,170 --> 00:07:54,990
Versionen till vänster
använder rekursion att göra det.

166
00:07:54,990 --> 00:07:58,320
Versionen på höger
använder iteration att göra det.

167
00:07:58,320 --> 00:08:02,050
>> Och varsel, måste vi förklara
en variabel ett heltal produkt.

168
00:08:02,050 --> 00:08:02,940
Och då är vi loop.

169
00:08:02,940 --> 00:08:06,790
Så länge som n är större än 0, vi
hålla multiplicera produkten med n

170
00:08:06,790 --> 00:08:09,890
och nedräkna n tills
vi beräkna produkten.

171
00:08:09,890 --> 00:08:14,600
Så dessa två funktioner, återigen,
gör exakt samma sak.

172
00:08:14,600 --> 00:08:19,980
Men de gör det inte i
exakt samma sätt.

173
00:08:19,980 --> 00:08:22,430
>> Nu är det möjligt att
ha mer än en bas

174
00:08:22,430 --> 00:08:25,770
ärende eller mer än en
rekursiv fall beroende

175
00:08:25,770 --> 00:08:27,670
på vad din funktion försöker göra.

176
00:08:27,670 --> 00:08:31,650
Du är inte nödvändigtvis bara begränsat till
en enda bas ärende eller en enda rekursiv

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

178
00:08:32,370 --> 00:08:35,320
Så ett exempel på något
med flera bas fall

179
00:08:35,320 --> 00:08:37,830
kan vara this-- den
Sekvensen Fibonacci nummer.

180
00:08:37,830 --> 00:08:41,549
>> Ni kanske minns från
elementära skoldagar

181
00:08:41,549 --> 00:08:45,740
att Fibonacci sekvensen definieras
liknande this-- det första elementet är 0.

182
00:08:45,740 --> 00:08:46,890
Den andra delen är en.

183
00:08:46,890 --> 00:08:49,230
Båda dessa är bara genom definition.

184
00:08:49,230 --> 00:08:55,920
>> Sedan varannan element definieras
som summan av n minus 1 och n minus 2.

185
00:08:55,920 --> 00:09:00,330
Så det tredje elementet
skulle vara 0 plus 1 är en.

186
00:09:00,330 --> 00:09:03,280
Och sedan det fjärde elementet
skulle vara det andra elementet, en,

187
00:09:03,280 --> 00:09:06,550
plus den tredje delen, 1.

188
00:09:06,550 --> 00:09:08,507
Och det skulle vara två.

189
00:09:08,507 --> 00:09:09,340
Och så vidare och så vidare.

190
00:09:09,340 --> 00:09:11,680
>> Så i det här fallet har vi två bas fall.

191
00:09:11,680 --> 00:09:14,850
Om n är lika med 1, returnerar 0.

192
00:09:14,850 --> 00:09:18,560
Om n är lika med 2, returnera ett.

193
00:09:18,560 --> 00:09:25,930
Annars åter Fibonacci n
minus en plus Fibonacci av n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Så det är flera bas fall.

195
00:09:27,180 --> 00:09:29,271
Vad sägs om flera rekursiva fall?

196
00:09:29,271 --> 00:09:31,520
Tja, det finns något
kallas Collatz gissningar.

197
00:09:31,520 --> 00:09:34,630
Jag tänker inte säga,
du vet vad det är,

198
00:09:34,630 --> 00:09:38,170
eftersom det är faktiskt vår sista
problem för denna viss video.

199
00:09:38,170 --> 00:09:43,220
Och det är vår träning
att arbeta tillsammans.

200
00:09:43,220 --> 00:09:46,760
>> Så här är vad
Collatz förmodanden är--

201
00:09:46,760 --> 00:09:48,820
det gäller för varje positivt heltal.

202
00:09:48,820 --> 00:09:51,500
Och det spekulerar att det är
alltid möjligt att få tillbaka

203
00:09:51,500 --> 00:09:55,060
till 1 om du följer dessa steg.

204
00:09:55,060 --> 00:09:57,560
Om n är 1, sluta.

205
00:09:57,560 --> 00:10:00,070
Vi har kommit tillbaka till 1 om n är 1.

206
00:10:00,070 --> 00:10:05,670
>> Annars går igenom detta
processen igen på n dividerat med två.

207
00:10:05,670 --> 00:10:08,200
Och se om du kan komma tillbaka till ett.

208
00:10:08,200 --> 00:10:13,260
Annars, om n är udda, gå igenom
denna process igen på 3n plus 1,

209
00:10:13,260 --> 00:10:15,552
eller 3 gånger n plus 1.

210
00:10:15,552 --> 00:10:17,010
Så här har vi en enda bas fallet.

211
00:10:17,010 --> 00:10:18,430
Om n är lika med 1, sluta.

212
00:10:18,430 --> 00:10:20,230
Vi ska inte göra något mer rekursion.

213
00:10:20,230 --> 00:10:23,730
>> Men vi har två rekursiva fall.

214
00:10:23,730 --> 00:10:28,750
Om n är ännu, gör vi en rekursiva
fall, Ringa n dividerat med två.

215
00:10:28,750 --> 00:10:33,950
Om n är udda, vi gör en annan
rekursiva fall på 3 gånger n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> Och så målet för den här videon är
att ta en andra, pausa videon,

217
00:10:39,120 --> 00:10:42,440
och försöka skriva detta
rekursiv funktion Collatz

218
00:10:42,440 --> 00:10:47,640
där du passerar på ett värde n, och
Det beräknar hur många steg det

219
00:10:47,640 --> 00:10:52,430
tar för att komma till en om du börjar från n
och du följer dessa steg upp ovan.

220
00:10:52,430 --> 00:10:56,660
Om n är 1, det tar 0 steg.

221
00:10:56,660 --> 00:11:00,190
Annars kommer det att
ta ett steg plus dock

222
00:11:00,190 --> 00:11:06,200
många steg det tar på antingen n
dividerat med 2 om n är ännu, eller 3n plus 1

223
00:11:06,200 --> 00:11:08,100
om n är udda.

224
00:11:08,100 --> 00:11:11,190
>> Nu, jag har lagt upp på skärmen här
ett par test saker för dig,

225
00:11:11,190 --> 00:11:15,690
ett par tester fall för dig, för att se
vad dessa olika Collatz siffror är,

226
00:11:15,690 --> 00:11:17,440
och även en illustration
av de åtgärder som

227
00:11:17,440 --> 00:11:20,390
måste gås igenom så att du kan
sorts se denna process i aktion.

228
00:11:20,390 --> 00:11:24,222
Så om n är lika med
1, Collatz n är 0.

229
00:11:24,222 --> 00:11:26,180
Du behöver inte göra
något att komma tillbaka till ett.

230
00:11:26,180 --> 00:11:27,600
Du är redan där.

231
00:11:27,600 --> 00:11:30,550
>> Om n är 2, det tar
ett steg för att komma till en.

232
00:11:30,550 --> 00:11:31,810
Du börjar med 2.

233
00:11:31,810 --> 00:11:33,100
Tja, är två inte är lika med ett.

234
00:11:33,100 --> 00:11:36,580
Så det kommer att bli ett steg
plus hur många steg det

235
00:11:36,580 --> 00:11:38,015
tar på n dividerat med två.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 delat med 2 är en.

238
00:11:42,910 --> 00:11:47,200
Så det tar ett steg plus dock
många steg det tar för en.

239
00:11:47,200 --> 00:11:49,720
1 tar noll steg.

240
00:11:49,720 --> 00:11:52,370
>> För tre, som ni kan se, det finns
ett par steg inblandade.

241
00:11:52,370 --> 00:11:53,590
Du går från 3.

242
00:11:53,590 --> 00:11:56,710
Och sedan gå till
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Det tar sju steg för att komma tillbaka till ett.

244
00:11:58,804 --> 00:12:01,220
Och som ni kan se, det finns en
par andra testfall här

245
00:12:01,220 --> 00:12:02,470
att testa programmet.

246
00:12:02,470 --> 00:12:03,970
Så återigen, pausa videon.

247
00:12:03,970 --> 00:12:09,210
Och jag ska gå hoppa tillbaka nu
vad själva processen är här,

248
00:12:09,210 --> 00:12:11,390
vad denna hypotes är.

249
00:12:11,390 --> 00:12:14,140
>> Se om du kan räkna ut
hur man definierar Collatz n

250
00:12:14,140 --> 00:12:19,967
så att den beräknar hur många
steg som krävs för att komma till en.

251
00:12:19,967 --> 00:12:23,050
Så förhoppningsvis har du pausat videon
och du inte bara väntar på mig

252
00:12:23,050 --> 00:12:25,820
för att ge dig svaret här.

253
00:12:25,820 --> 00:12:29,120
Men om du är, tja,
Här är svaret ändå.

254
00:12:29,120 --> 00:12:33,070
>> Så här är en möjlig definition
av Collatz funktionen.

255
00:12:33,070 --> 00:12:35,610
Vår bas case-- om n är
lika med 1, återvänder vi 0.

256
00:12:35,610 --> 00:12:38,250
Det tar inte någon
åtgärder för att komma tillbaka till ett.

257
00:12:38,250 --> 00:12:42,710
>> Annars har vi två rekursiva cases--
en för jämna nummer och ett för udda.

258
00:12:42,710 --> 00:12:47,164
Som jag testa jämna nummer
är att kontrollera om n mod 2 är lika med 0.

259
00:12:47,164 --> 00:12:49,080
Detta är i grunden, återigen,
ställer frågan,

260
00:12:49,080 --> 00:12:54,050
om du minns vad mod är-- om jag
dividera n med 2 finns det ingen resten?

261
00:12:54,050 --> 00:12:55,470
Det skulle vara ett jämnt antal.

262
00:12:55,470 --> 00:13:01,370
>> Och så om n mod 2 är lika med 0 är
testning är detta ett jämnt antal.

263
00:13:01,370 --> 00:13:04,250
Om så är fallet, jag vill återvända 1,
eftersom detta är definitivt

264
00:13:04,250 --> 00:13:09,270
tar ett steg plus Collatz av
oavsett antal är hälften av mig.

265
00:13:09,270 --> 00:13:13,910
Annars, jag vill återvända 1
plus Collatz av 3 gånger n plus 1.

266
00:13:13,910 --> 00:13:16,060
Det var den andra
rekursiva steg som vi

267
00:13:16,060 --> 00:13:19,470
kan vidta för att beräkna
Collatz-- antalet steg

268
00:13:19,470 --> 00:13:22,610
det tar att komma tillbaka
1 ges ett nummer.

269
00:13:22,610 --> 00:13:24,610
Så förhoppningsvis detta exempel
gav dig lite

270
00:13:24,610 --> 00:13:26,620
en smak av rekursiva procedurer.

271
00:13:26,620 --> 00:13:30,220
Förhoppningsvis tycker du koden är en
lite vackrare om de genomförs

272
00:13:30,220 --> 00:13:32,760
i en elegant, rekursiv sätt.

273
00:13:32,760 --> 00:13:35,955
Men även om det inte är rekursion en
verkligen kraftfullt verktyg ändå.

274
00:13:35,955 --> 00:13:38,330
Och så det är definitivt något
att få huvudet runt,

275
00:13:38,330 --> 00:13:41,360
eftersom du kommer att kunna skapa
ganska cool program med rekursion

276
00:13:41,360 --> 00:13:45,930
som annars skulle vara komplicerat att skriva
Om du använder loopar och iteration.

277
00:13:45,930 --> 00:13:46,980
Jag är Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Detta är CS50.

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