1
00:00:00,000 --> 00:00:05,860
>> [Muzikos grojimo]

2
00:00:05,860 --> 00:00:09,530
>> Doug LLOYD: Jūs tikriausiai manote, kad
kodas tik naudojamas atlikti užduotį.

3
00:00:09,530 --> 00:00:10,450
Jūs rašote jį.

4
00:00:10,450 --> 00:00:11,664
Ji kažką.

5
00:00:11,664 --> 00:00:12,580
Tai gana daug.

6
00:00:12,580 --> 00:00:13,160
>> Jūs kaupia ją.

7
00:00:13,160 --> 00:00:13,993
Paleidus programą.

8
00:00:13,993 --> 00:00:15,370
Jūs esate gera eiti.

9
00:00:15,370 --> 00:00:17,520
>> Bet tiki jis ar ne, jei
Jūs kodas ilgą laiką,

10
00:00:17,520 --> 00:00:20,550
jūs iš tikrųjų gali ateiti pamatyti
kodas, kaip kažkas, kad yra graži.

11
00:00:20,550 --> 00:00:23,275
Tai išsprendžia problemą į
labai įdomus būdas,

12
00:00:23,275 --> 00:00:26,510
ar ten tiesiog kažkas tikrai
tvarkingas apie tai, kaip jis atrodo.

13
00:00:26,510 --> 00:00:28,750
Jums gali būti juokiasi
ne man, bet tai tiesa.

14
00:00:28,750 --> 00:00:31,530
Ir rekursija yra vienas iš būdų
rūšiuoti gauti šią idėją

15
00:00:31,530 --> 00:00:34,090
iš gražus, elegantiškas atrodančius kodą.

16
00:00:34,090 --> 00:00:37,740
Tai išsprendžia problemas tokiu būdu, kad
yra įdomus, lengva įsivaizduoti,

17
00:00:37,740 --> 00:00:39,810
ir stebėtinai trumpas.

18
00:00:39,810 --> 00:00:43,190
>> Beje Rekursija darbai
yra, grįžtamojo funkcija

19
00:00:43,190 --> 00:00:49,291
yra apibrėžiamas kaip funkcija, kad reikalauja
pati kaip jos vykdymo.

20
00:00:49,291 --> 00:00:51,790
Tai gali atrodyti šiek tiek keista,
ir mes pamatyti šiek tiek

21
00:00:51,790 --> 00:00:53,750
apie, kaip tai veikia iškart.

22
00:00:53,750 --> 00:00:55,560
Bet vėl, tai
Rekurentiniai procedūros

23
00:00:55,560 --> 00:00:57,730
bus tokia elegantiška
nes jie ketina

24
00:00:57,730 --> 00:01:00,410
išspręsti šią problemą, be
turintys visas šias ir kitas funkcijas

25
00:01:00,410 --> 00:01:02,710
ar šie ilgi kilpas.

26
00:01:02,710 --> 00:01:06,310
Pamatysite, kad tai rekursywny
procedūros ketiname ieškoti toks trumpas.

27
00:01:06,310 --> 00:01:10,610
Ir jie tikrai ketina padaryti
Jūsų kodas atrodo daug gražesnė.

28
00:01:10,610 --> 00:01:12,560
>> Aš duosiu jums pavyzdį
tai pamatyti, kaip

29
00:01:12,560 --> 00:01:14,880
rekursywny procedūra gali būti nustatyta.

30
00:01:14,880 --> 00:01:18,202
Taigi, jei esate susipažinę su šiuo
iš matematikos klasės, prieš daugelį metų,

31
00:01:18,202 --> 00:01:20,910
Yra kažkas, vadinamas
faktorialinis funkcija, kuri paprastai

32
00:01:20,910 --> 00:01:25,340
žymimas kaip šauktukas, kuris
yra apibrėžiamas per visi teigiami sveikieji skaičiai.

33
00:01:25,340 --> 00:01:28,850
Ir taip, kad n
faktorialas yra apskaičiuojamas

34
00:01:28,850 --> 00:01:31,050
yra padauginti visus
numeriai mažiau nei

35
00:01:31,050 --> 00:01:33,750
arba lygus n together--
visi sveikieji mažiau nei

36
00:01:33,750 --> 00:01:34,880
arba lygus n kartu.

37
00:01:34,880 --> 00:01:39,850
>> Taigi 5 faktorialas yra 5 kartus
4 kartus 3 kartus 2 kartus 1.

38
00:01:39,850 --> 00:01:43,020
Ir 4 faktorialas yra 4 kartus
3 kartus 2 kartus 1 ir pan.

39
00:01:43,020 --> 00:01:44,800
Jūs gaunate idėja.

40
00:01:44,800 --> 00:01:47,060
>> Kaip programuotojai, mes do not
naudoti N, šauktukas.

41
00:01:47,060 --> 00:01:51,840
Taigi mes apibrėžti faktorialas
funkcija taip sakant n.

42
00:01:51,840 --> 00:01:56,897
Ir mes naudosime faktorialas sukurti
rekursywny sprendimas problema.

43
00:01:56,897 --> 00:01:59,230
Ir manau, kad jūs galite rasti
kad tai daug labiau vizualiai

44
00:01:59,230 --> 00:02:02,380
patrauklus nei kartotinis
versija tai, kuris

45
00:02:02,380 --> 00:02:05,010
mes taip pat pažvelgti į šiuo metu.

46
00:02:05,010 --> 00:02:08,310
>> Taigi čia yra pora
facts-- kalambūras intended--

47
00:02:08,310 --> 00:02:10,169
apie factorial--
faktorialas funkcija.

48
00:02:10,169 --> 00:02:13,090
1 faktorialas, kaip sakiau, yra 1.

49
00:02:13,090 --> 00:02:15,690
2 faktorialas yra 2 kartus 1.

50
00:02:15,690 --> 00:02:18,470
3 faktorialas yra 3
kartų 2 kartus 1, ir taip toliau.

51
00:02:18,470 --> 00:02:20,810
Mes kalbėjome apie 4 ir 5 jau.

52
00:02:20,810 --> 00:02:23,940
>> Bet žiūri šį, nėra tai tiesa?

53
00:02:23,940 --> 00:02:28,220
Ar ne faktorialas 2 tik
2 kartus 1 faktorialas?

54
00:02:28,220 --> 00:02:31,130
Aš turiu galvoje, 1 faktorialas yra 1.

55
00:02:31,130 --> 00:02:34,940
Taigi kodėl mes negalime tiesiog pasakyti, kad
nuo faktorialas 2 yra 2 kartus 1

56
00:02:34,940 --> 00:02:38,520
tai tikrai tik 2 kartus
1 faktorialas?

57
00:02:38,520 --> 00:02:40,900
>> Ir tada išplėsti šią idėją,
nėra 3 faktorialas

58
00:02:40,900 --> 00:02:44,080
tik 3 kartus 2 faktorialas?

59
00:02:44,080 --> 00:02:50,350
Ir iš 4 faktorialas yra 4 kartus
3, ir taip toliau faktorialas?

60
00:02:50,350 --> 00:02:52,530
Tiesą sakant, faktorinė
bet skaičius gali tik

61
00:02:52,530 --> 00:02:54,660
būti išreikštas jei mes natūra
perkėlimų tai iš amžinai.

62
00:02:54,660 --> 00:02:56,870
Mes galime rūšies apibendrinti
Faktorialaus problema

63
00:02:56,870 --> 00:02:59,910
kaip tai n kartų
faktorialas n minus 1.

64
00:02:59,910 --> 00:03:04,840
Tai n kartų iš produkto
visi numeriai mažiau nei mane.

65
00:03:04,840 --> 00:03:08,890
>> Ši idėja, ši
apibendrinimas problemos,

66
00:03:08,890 --> 00:03:13,410
leidžia mums rekursyviai
apibrėžti faktorialas funkciją.

67
00:03:13,410 --> 00:03:15,440
Kai apibrėžti funkciją
rekursyviai, ten

68
00:03:15,440 --> 00:03:17,470
du dalykai, kurie turi būti jos dalimi.

69
00:03:17,470 --> 00:03:20,990
Jums reikia turėti kažką vadinama
bazinį scenarijų, kuris, kai jūs sukelti ją,

70
00:03:20,990 --> 00:03:22,480
nustos rekursinį procesą.

71
00:03:22,480 --> 00:03:25,300
>> Priešingu atveju, funkcija, kuri ragina
itself-- kaip galima imagine--

72
00:03:25,300 --> 00:03:26,870
gali tęstis amžinai.

73
00:03:26,870 --> 00:03:29,047
Funkcija ragina funkciją
vadina funkcija skambučius

74
00:03:29,047 --> 00:03:30,380
funkcija iškviečia funkciją.

75
00:03:30,380 --> 00:03:32,380
Jei jūs neturite būdas
jį sustabdyti, savo programą

76
00:03:32,380 --> 00:03:34,760
bus veiksmingai įstrigo
ne begalinis ciklas.

77
00:03:34,760 --> 00:03:37,176
Tai bus katastrofos, galų gale,
nes jis bus paleisti iš atminties.

78
00:03:37,176 --> 00:03:38,990
Bet tai šalia taško.

79
00:03:38,990 --> 00:03:42,210
>> Mums reikia turėti kokį nors kitą būdą, kaip sustabdyti
dalykų Be mūsų programos kritimo,

80
00:03:42,210 --> 00:03:46,010
nes programa, kuri avarijos yra
tikriausiai ne gražus ar elegantiška.

81
00:03:46,010 --> 00:03:47,690
Ir taip mes vadiname tai bazinį scenarijų.

82
00:03:47,690 --> 00:03:50,610
Tai yra paprastas sprendimas
į problemą, kuri nutraukia

83
00:03:50,610 --> 00:03:52,770
grįžtamojo proceso pasikartojimui.

84
00:03:52,770 --> 00:03:55,220
Taigi, kad viena dalis
rekursywny funkcija.

85
00:03:55,220 --> 00:03:56,820
>> Antroji dalis yra grįžtamojo atveju.

86
00:03:56,820 --> 00:03:59,195
Ir tai yra, kai rekursinio
bus iš tikrųjų vyksta.

87
00:03:59,195 --> 00:04:02,200
Tai yra, kur
funkcija skambinti pati.

88
00:04:02,200 --> 00:04:05,940
>> Jis nebus skambinti pati tiksliai
tas pats, kaip jis buvo vadinamas.

89
00:04:05,940 --> 00:04:08,880
Jis bus šiek tiek variacijos
kad daro problemą, tai

90
00:04:08,880 --> 00:04:11,497
bando išspręsti smulkutis šiek tiek mažesnis.

91
00:04:11,497 --> 00:04:14,330
Bet tai paprastai praeina spardytis
išspręsti tirpalo urmu

92
00:04:14,330 --> 00:04:17,450
į kitą skambutį žemyn linija.

93
00:04:17,450 --> 00:04:20,290
>> Kuris iš šių išvaizda
kaip bazine čia?

94
00:04:20,290 --> 00:04:25,384
Kuris iš šių atrodo kaip
Paprasčiausias sprendimas yra problema?

95
00:04:25,384 --> 00:04:27,550
Mes turime Factorial krūva,
ir galėtume toliau

96
00:04:27,550 --> 00:04:30,470
vyksta on-- 6, 7, 8, 9, 10 ir pan.

97
00:04:30,470 --> 00:04:34,130
>> Tačiau vienas iš šių išvaizda
geras pavyzdys būtų bazinį scenarijų.

98
00:04:34,130 --> 00:04:35,310
Tai labai paprastas sprendimas.

99
00:04:35,310 --> 00:04:37,810
Neturime nieko ypatingo.

100
00:04:37,810 --> 00:04:40,560
>> 1 faktorialas yra tik 1.

101
00:04:40,560 --> 00:04:42,790
Neturime daryti bet
daugyba ne visiems.

102
00:04:42,790 --> 00:04:45,248
Atrodo, kad jei mes ketiname
pabandyti ir išspręsti šią problemą,

103
00:04:45,248 --> 00:04:47,600
ir mes turime sustabdyti
Rekursija kažkur,

104
00:04:47,600 --> 00:04:50,610
mes tikriausiai norite sustabdyti
tai kai mes gauti iki 1.

105
00:04:50,610 --> 00:04:54,580
Mes nenorime sustoti prieš tai.

106
00:04:54,580 --> 00:04:56,660
>> Taigi, jei mes apibrėžti
Mūsų faktorialas funkcija,

107
00:04:56,660 --> 00:04:58,690
čia už skeletas
kaip mes galime tai padaryti.

108
00:04:58,690 --> 00:05:03,110
Mums reikia prijungti šių dviejų Quake
bazinį scenarijų ir grįžtamojo atveju.

109
00:05:03,110 --> 00:05:04,990
Kas bazinį scenarijų?

110
00:05:04,990 --> 00:05:10,150
Jei n yra lygus 1, grįžti 1-- tai
tikrai paprasta problemą išspręsti.

111
00:05:10,150 --> 00:05:11,890
>> 1 faktorialas yra 1.

112
00:05:11,890 --> 00:05:13,860
Tai ne 1 kartų nieko.

113
00:05:13,860 --> 00:05:15,020
Tai tik 1.

114
00:05:15,020 --> 00:05:17,170
Tai labai paprasta faktas.

115
00:05:17,170 --> 00:05:19,620
Ir taip, kad gali būti mūsų bazinį scenarijų.

116
00:05:19,620 --> 00:05:24,730
Jei mes gauti išlaikė 1 į tai
funkcija, mes tiesiog return 1.

117
00:05:24,730 --> 00:05:27,320
>> Koks grįžtamojo
atvejis greičiausiai atrodys?

118
00:05:27,320 --> 00:05:32,445
Dėl visų kitų skaičių
Be to 1, koks modelis?

119
00:05:32,445 --> 00:05:35,780
Na, jei mes atsižvelgti
iš n faktorialas,

120
00:05:35,780 --> 00:05:38,160
Tai n kartų iš n faktorialas atėmus 1.

121
00:05:38,160 --> 00:05:42,130
>> Jei mes radote faktorialas 3,
tai 3 kartus 3 minus 1 faktorialas,

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

123
00:05:43,070 --> 00:05:47,330
Ir todėl, jei mes ne
žiūri 1, priešingu atveju

124
00:05:47,330 --> 00:05:51,710
grąža n kartų
faktorialas n minus 1.

125
00:05:51,710 --> 00:05:53,210
Tai gana paprasta.

126
00:05:53,210 --> 00:05:57,360
>> Ir dėl turintys šiek tiek labui
švaresnis ir labiau elegantiškas kodas,

127
00:05:57,360 --> 00:06:01,440
žino, kad jei mes turime viena linija kilpų
arba vieno linija sąlyginės filialai,

128
00:06:01,440 --> 00:06:04,490
galime atsikratyti visas
garbanotas petnešos aplink juos.

129
00:06:04,490 --> 00:06:06,850
Taigi, mes galime sujungti tai tai.

130
00:06:06,850 --> 00:06:09,640
Tai lygiai tas pats
funkcionalumas kaip šis.

131
00:06:09,640 --> 00:06:13,850
>> Aš tiesiog neatimtų garbanotas
petnešos, nes ten tik viena eilutė

132
00:06:13,850 --> 00:06:18,500
viduje tų sąlyginių šakų.

133
00:06:18,500 --> 00:06:21,160
Taigi jie elgiasi vienodai.

134
00:06:21,160 --> 00:06:23,800
Jei n yra lygus 1, grąžinti 1.

135
00:06:23,800 --> 00:06:28,351
Priešingu atveju grįžti n kartų
iš n minus 1 faktorialas.

136
00:06:28,351 --> 00:06:29,850
Taigi mes darome problemą mažesnis.

137
00:06:29,850 --> 00:06:33,850
Jei n prasideda kaip 5, mes ketiname
grįžti 5 kartus 4 faktorialas.

138
00:06:33,850 --> 00:06:37,100
Ir mes pamatysime per minutę, kai mes kalbame
apie skambučius stack-- kitoje vaizdo

139
00:06:37,100 --> 00:06:39,390
kur mes kalbame apie
skambinti stack-- mes išmokti

140
00:06:39,390 --> 00:06:41,630
apie tai, kodėl būtent šis procesas veikia.

141
00:06:41,630 --> 00:06:46,970
>> Tačiau, nors faktorialas 5 sako
grįžti 5 kartus faktorialas 4 ir 4

142
00:06:46,970 --> 00:06:49,710
ketina pasakyti, gerai, gerai, grąžinimo
4 kartus 3 faktorialas.

143
00:06:49,710 --> 00:06:51,737
Ir, kaip matote, mes
Rūšiuoti artėja 1 d.

144
00:06:51,737 --> 00:06:53,820
Mes vis arčiau ir
priartinti prie pagrindo atveju.

145
00:06:53,820 --> 00:06:58,180
>> Ir kai mes paspauskite pagrindą,
visi ankstesnių funkcijų

146
00:06:58,180 --> 00:07:00,540
turi atsakyti jie ieško.

147
00:07:00,540 --> 00:07:03,900
Faktorinė 2 kalbėjo grąžą
2 kartus 1 faktorialas.

148
00:07:03,900 --> 00:07:06,760
Na, faktorinė iš 1 grąža 1 d.

149
00:07:06,760 --> 00:07:10,090
Taigi už faktorialas skambutis
2 gali grąžinti 2 kartus 1

150
00:07:10,090 --> 00:07:13,980
ir duoti, kad atgal į Faktorialas
3, kuri yra laukia, kad rezultatas.

151
00:07:13,980 --> 00:07:17,110
>> Ir tada jis gali apskaičiuoti
jos rezultatas, 3 kartus 2 6,

152
00:07:17,110 --> 00:07:18,907
ir duoti jį atgal į faktorialas 4.

153
00:07:18,907 --> 00:07:20,740
Ir vėl, mes turime
Vaizdo skambučių kamino

154
00:07:20,740 --> 00:07:23,810
kur tai yra pavaizduotas šiek tiek
daugiau nei tai, ką aš sakau dabar.

155
00:07:23,810 --> 00:07:25,300
Bet tai jis.

156
00:07:25,300 --> 00:07:29,300
Vien tai yra, kad sprendimas
Skaičiuojant skaičiaus faktorialas.

157
00:07:29,300 --> 00:07:31,527
>> Tai tik keturias eilutes kodo.

158
00:07:31,527 --> 00:07:32,610
Tai gana kietas, tiesa?

159
00:07:32,610 --> 00:07:35,480
Tai tipo seksualus.

160
00:07:35,480 --> 00:07:38,580
>> Taigi, apskritai, bet ne
visada, rekursywny funkcija

161
00:07:38,580 --> 00:07:41,190
gali pakeisti kilpa
ne rekursywny funkcija.

162
00:07:41,190 --> 00:07:46,100
Taigi čia, side by side, yra iteracinis
versija Faktorialaus funkcija.

163
00:07:46,100 --> 00:07:49,650
Abu šie Skaičiuoti
lygiai tas pats dalykas.

164
00:07:49,650 --> 00:07:52,170
>> Jie abu apskaičiuoti n faktorialas.

165
00:07:52,170 --> 00:07:54,990
Kairėje versija
naudoja rekursija tai padaryti.

166
00:07:54,990 --> 00:07:58,320
Dešinėje versija
naudoja iteracijos tai padaryti.

167
00:07:58,320 --> 00:08:02,050
>> Ir pranešimas, turime pripažinti
kintamasis sveikas produktas.

168
00:08:02,050 --> 00:08:02,940
Ir tada mes kilpa.

169
00:08:02,940 --> 00:08:06,790
Tol, kol n yra didesnis už 0, mes
išlaikyti padauginus n produktą

170
00:08:06,790 --> 00:08:09,890
ir mažėjančio n iki
mes galime apskaičiuoti produktą.

171
00:08:09,890 --> 00:08:14,600
Taigi, šie du funkcijos, vėl,
padaryti lygiai tą patį.

172
00:08:14,600 --> 00:08:19,980
Tačiau jie neturi daryti
lygiai taip pat.

173
00:08:19,980 --> 00:08:22,430
>> Dabar, tai yra įmanoma, kad
turi daugiau nei vieną bazę

174
00:08:22,430 --> 00:08:25,770
atveju arba daugiau nei vieną
rekursywny atveju, priklausomai nuo

175
00:08:25,770 --> 00:08:27,670
ką jūsų funkcija bando daryti.

176
00:08:27,670 --> 00:08:31,650
Jūs nebūtinai tik "
vieną bazinį scenarijų arba vieno rekursywny

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

178
00:08:32,370 --> 00:08:35,320
Taigi AN kažką pavyzdys
su keliais baziniais atvejais

179
00:08:35,320 --> 00:08:37,830
gali būti this--
Fibonačio skaičius, seka.

180
00:08:37,830 --> 00:08:41,549
>> Jūs galite prisiminti iš
pradinių mokyklų dienų

181
00:08:41,549 --> 00:08:45,740
kad Fibonačio seka apibrėžta
kaip this-- pirmasis elementas yra 0.

182
00:08:45,740 --> 00:08:46,890
Antrasis elementas yra 1.

183
00:08:46,890 --> 00:08:49,230
Abu jie yra tiesiog pagal apibrėžimą.

184
00:08:49,230 --> 00:08:55,920
>> Tada kiekvienas kitas elementas apibrėžiamas
kaip n minus 1 ir n minus 2 suma.

185
00:08:55,920 --> 00:09:00,330
Taigi trečiąjį elementą
Būtų 0 ir 1 yra 1.

186
00:09:00,330 --> 00:09:03,280
Ir tada ketvirtas elementas
būtų antra elementas, 1,

187
00:09:03,280 --> 00:09:06,550
plius trečiasis elementas, 1.

188
00:09:06,550 --> 00:09:08,507
Ir tai būtų 2.

189
00:09:08,507 --> 00:09:09,340
Ir taip toliau, ir taip toliau.

190
00:09:09,340 --> 00:09:11,680
>> Taigi šiuo atveju, mes turime dvi bazines bylas.

191
00:09:11,680 --> 00:09:14,850
Jei n yra lygus 1, grąžinti 0.

192
00:09:14,850 --> 00:09:18,560
Jei n yra lygus 2, grąžinti 1.

193
00:09:18,560 --> 00:09:25,930
Priešingu atveju, grįžti Fibonacci n
atėmus 1 plius Fibonačio n ± 2.

194
00:09:25,930 --> 00:09:27,180
>> Taigi, kad kelis bazinius atvejus.

195
00:09:27,180 --> 00:09:29,271
Ką apie kelių rekursyvių atvejais?

196
00:09:29,271 --> 00:09:31,520
Na, kažkas
vadinamas Collatz spėjimas.

197
00:09:31,520 --> 00:09:34,630
Nesiruošiu sakyti,
jūs žinote, kas tai yra,

198
00:09:34,630 --> 00:09:38,170
nes tai tikrai mūsų galutinis
problema šiuo konkrečiu vaizdo.

199
00:09:38,170 --> 00:09:43,220
Ir tai mūsų pratybos
dirbti kartu.

200
00:09:43,220 --> 00:09:46,760
>> Taigi čia ką
Collatz spėjimas is--

201
00:09:46,760 --> 00:09:48,820
jis taikomas kiekvieną teigiamą sveikąjį skaičių.

202
00:09:48,820 --> 00:09:51,500
Ir tai spėja, kad tai
visada galima grįžti

203
00:09:51,500 --> 00:09:55,060
1, jei atlikite šiuos veiksmus.

204
00:09:55,060 --> 00:09:57,560
Jei n yra 1, sustabdyti.

205
00:09:57,560 --> 00:10:00,070
Mes turime grįžti į 1, jei n yra 1.

206
00:10:00,070 --> 00:10:05,670
>> Priešingu atveju, eiti per tai
procesas vėl n padalytą iš 2.

207
00:10:05,670 --> 00:10:08,200
Ir pamatyti, jei jūs galite gauti atgal į 1.

208
00:10:08,200 --> 00:10:13,260
Priešingu atveju, jei n yra nelyginis, eiti per
šis procesas vėl 3N plius 1,

209
00:10:13,260 --> 00:10:15,552
arba 3 kartus n plius 1.

210
00:10:15,552 --> 00:10:17,010
Taigi čia mes turime vieną bazinį scenarijų.

211
00:10:17,010 --> 00:10:18,430
Jei n yra lygus 1, sustabdyti.

212
00:10:18,430 --> 00:10:20,230
Mes nedarome, bet daugiau rekursija.

213
00:10:20,230 --> 00:10:23,730
>> Bet mes turime dvi rekursinių atvejus.

214
00:10:23,730 --> 00:10:28,750
Jei n yra lygus, mes darome vieną rekursinį
atveju, ragindamas N padalytą iš 2.

215
00:10:28,750 --> 00:10:33,950
Jei n yra nelyginis, mes skirtingi
rekursywny byla dėl 3 times n plius 1 d.

216
00:10:33,950 --> 00:10:39,120
>> Ir taip už šį video tikslas
imtis sekundę, pristabdyti vaizdo įrašą,

217
00:10:39,120 --> 00:10:42,440
ir pabandyti ir rašau tai
rekursywny funkcija Collatz

218
00:10:42,440 --> 00:10:47,640
kur praeiti vertės n ir
jis apskaičiuoja, kiek žingsnių jį

219
00:10:47,640 --> 00:10:52,430
mano, kad gauti 1, jei jums pradėti iš n
ir atlikite šiuos veiksmus iki viršaus.

220
00:10:52,430 --> 00:10:56,660
Jei n yra 1, tai užima 0 žingsnius.

221
00:10:56,660 --> 00:11:00,190
Priešingu atveju, jis ketina
išgerkite vieną žingsnį plius tačiau

222
00:11:00,190 --> 00:11:06,200
daug žingsnių jis pasiima arba n
padalintas iš 2, jei n yra lygus, ar 3n plius 1

223
00:11:06,200 --> 00:11:08,100
jei n yra keista.

224
00:11:08,100 --> 00:11:11,190
>> Dabar, aš supakuoti ekrane čia
Bandinių dalykų už jus pora,

225
00:11:11,190 --> 00:11:15,690
testų atvejais pora jums, norėdami pamatyti,
ką šie įvairūs COLLATZ numeriai,

226
00:11:15,690 --> 00:11:17,440
ir taip pat iliustracija
iš žingsnių, kad

227
00:11:17,440 --> 00:11:20,390
reikia išgyveno todėl jūs galite
rūšiuoti pamatyti šį procesą veiksmų.

228
00:11:20,390 --> 00:11:24,222
Taigi, jei n yra lygus
1, Collatz n yra 0.

229
00:11:24,222 --> 00:11:26,180
Jūs neturite daryti
nieko grįžti iki 1.

230
00:11:26,180 --> 00:11:27,600
Jūs jau esate ten.

231
00:11:27,600 --> 00:11:30,550
>> Jei n yra 2, tai užima
vienas žingsnis gauti iki 1.

232
00:11:30,550 --> 00:11:31,810
Jūs pradedate su 2.

233
00:11:31,810 --> 00:11:33,100
Na, 2 yra ne lygus 1.

234
00:11:33,100 --> 00:11:36,580
Taigi, tai bus vienas žingsnis
plius Tačiau daugelis veiksmų, kurių ji

235
00:11:36,580 --> 00:11:38,015
įgauna N padalytą iš 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2, padalytą iš 2 1.

238
00:11:42,910 --> 00:11:47,200
Taigi ji mano vieną žingsnį plius tačiau
daug žingsnių užtrunka 1 d.

239
00:11:47,200 --> 00:11:49,720
1 užtrunka nulį veiksmus.

240
00:11:49,720 --> 00:11:52,370
>> 3, kaip matote, yra
nemažai etapus.

241
00:11:52,370 --> 00:11:53,590
Nueini iš 3.

242
00:11:53,590 --> 00:11:56,710
Ir tada jūs einate į
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Tai užtrunka septynių žingsnių grįžti prie 1 d.

244
00:11:58,804 --> 00:12:01,220
Ir, kaip matote, ten
pora kitų bandymų atvejus čia

245
00:12:01,220 --> 00:12:02,470
išbandyti savo programą.

246
00:12:02,470 --> 00:12:03,970
Taigi dar kartą, pristabdyti vaizdo įrašą.

247
00:12:03,970 --> 00:12:09,210
Ir aš eisiu šokti atgal dabar
kas tikrasis procesas yra čia

248
00:12:09,210 --> 00:12:11,390
ką tai hipotezė yra.

249
00:12:11,390 --> 00:12:14,140
>> Žr jeigu jūs galite išsiaiškinti
Kaip apibrėžti COLLATZ n

250
00:12:14,140 --> 00:12:19,967
taip, kad jis skaičiuoja, kiek
žingsniai užtrunka gauti iki 1.

251
00:12:19,967 --> 00:12:23,050
Taigi tikiuosi, jūs sustabdytas video
o jūs ne tik manęs laukia

252
00:12:23,050 --> 00:12:25,820
kad turėtumėte atsakyti čia.

253
00:12:25,820 --> 00:12:29,120
Bet jei jūs esate, gerai,
Štai atsakymas vistiek.

254
00:12:29,120 --> 00:12:33,070
>> Taigi čia galima apibrėžimas
iš Collatz funkcija.

255
00:12:33,070 --> 00:12:35,610
Mūsų bazė case-- jei n yra
lygus 1, mes grįžti 0.

256
00:12:35,610 --> 00:12:38,250
Ji neatsižvelgia į bet
žingsnių grįžti prie 1 d.

257
00:12:38,250 --> 00:12:42,710
>> Priešingu atveju, mes turime du rekursinį cases--
vienas net numerius ir vienas keista.

258
00:12:42,710 --> 00:12:47,164
Kaip aš išbandyti net numerius
yra patikrinti, ar n mod 2 yra lygus 0.

259
00:12:47,164 --> 00:12:49,080
Tai yra, iš esmės, vėl,
klausia klausimą,

260
00:12:49,080 --> 00:12:54,050
Jei prisimenate ką mod is-- jei aš
skaldyk N iš 2 ten nėra likusi?

261
00:12:54,050 --> 00:12:55,470
Kad būtų lyginis skaičius.

262
00:12:55,470 --> 00:13:01,370
>> Ir todėl, jei n mod 2 yra lygus 0 yra
bandymai yra tai lyginis skaičius.

263
00:13:01,370 --> 00:13:04,250
Jei taip, aš noriu grįžti 1,
nes tai tikrai

264
00:13:04,250 --> 00:13:09,270
atsižvelgiant vieną žingsnį plius COLLATZ dėl
kokia numeris yra pusė mane.

265
00:13:09,270 --> 00:13:13,910
Priešingu atveju, aš noriu grįžti 1
plius Collatz 3 times n plius 1.

266
00:13:13,910 --> 00:13:16,060
Kad buvo kita
rekursywny žingsnis, kad mes

267
00:13:16,060 --> 00:13:19,470
galėtų apskaičiuoti
Collatz-- žingsnių skaičių

268
00:13:19,470 --> 00:13:22,610
ji mano, kad grįžti
1 suteikiamas numeris.

269
00:13:22,610 --> 00:13:24,610
Taigi tikiuosi, šis pavyzdys
padovanojo tau truputį

270
00:13:24,610 --> 00:13:26,620
iš rekursyvių procedūrų skonį.

271
00:13:26,620 --> 00:13:30,220
Tikimės, kad jūs manote kodas yra
tiek gražesnė jei bus įgyvendintos

272
00:13:30,220 --> 00:13:32,760
elegantiškas, grįžtamojo būdu.

273
00:13:32,760 --> 00:13:35,955
Bet net jei ne, rekursija yra
tikrai galingas įrankis vis.

274
00:13:35,955 --> 00:13:38,330
Ir taip tai tikrai kažkas
gauti savo galvą aplink,

275
00:13:38,330 --> 00:13:41,360
nes jūs galėsite sukurti
pretty cool programas, naudojant rekursija

276
00:13:41,360 --> 00:13:45,930
kad priešingu atveju būtų sudėtinga rašyti
jei jūs naudojate kilpos ir iteracijos.

277
00:13:45,930 --> 00:13:46,980
Aš Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Tai CS50.

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