1
00:00:00,000 --> 00:00:05,860
>> [MUSIC nagpe-play]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: marahil sa tingin mo na
code ay ginagamit lamang upang makamit ang isang gawain.

3
00:00:09,530 --> 00:00:10,450
Isulat mo ito.

4
00:00:10,450 --> 00:00:11,664
Ito ang isang bagay.

5
00:00:11,664 --> 00:00:12,580
Iyan ay medyo magkano ito.

6
00:00:12,580 --> 00:00:13,160
>> Sumulat ng libro mo ito.

7
00:00:13,160 --> 00:00:13,993
Patakbuhin mo ang program.

8
00:00:13,993 --> 00:00:15,370
Ikaw ay handa na upang patakbuhin.

9
00:00:15,370 --> 00:00:17,520
>> Ngunit naniniwala ito o hindi, kung
mong code para sa isang mahabang panahon,

10
00:00:17,520 --> 00:00:20,550
ikaw ay tunay na maaaring dumating upang makita ang
code bilang isang bagay na maganda.

11
00:00:20,550 --> 00:00:23,275
Ito malulutas nito ang isang problema sa
isang napaka-kawili-wiling paraan,

12
00:00:23,275 --> 00:00:26,510
o mayroong lamang isang bagay na talagang
malinis at maayos ang tungkol sa mga paraan na ito hitsura.

13
00:00:26,510 --> 00:00:28,750
Maaari kang maging tumatawa
sa akin, ngunit ito ay totoo.

14
00:00:28,750 --> 00:00:31,530
At recursion ay isang paraan
na uri ng makakuha ng ideya na ito

15
00:00:31,530 --> 00:00:34,090
ng maganda, eleganteng-naghahanap code.

16
00:00:34,090 --> 00:00:37,740
Ito malulutas nito ang problema sa mga paraan na
ay kawili-wili, ang pag-visualize,

17
00:00:37,740 --> 00:00:39,810
at nakakagulat na short.

18
00:00:39,810 --> 00:00:43,190
>> Ang mga gawa na paraan recursion
ay, ang isang recursive function

19
00:00:43,190 --> 00:00:49,291
ay tinukoy bilang isang function na ang tawag
ang sarili bilang bahagi ng pagpapatupad nito.

20
00:00:49,291 --> 00:00:51,790
Na maaaring mukhang isang maliit na kakaiba,
at kami na makita ang isang maliit na piraso

21
00:00:51,790 --> 00:00:53,750
tungkol sa kung paano ito gumagana sa isang sandali.

22
00:00:53,750 --> 00:00:55,560
Subalit muli, ang mga ito
recursive pamamaraan ay

23
00:00:55,560 --> 00:00:57,730
magiging kaya eleganteng
dahil sila ay pagpunta

24
00:00:57,730 --> 00:01:00,410
upang malutas ang problemang ito nang walang
pagkakaroon ng lahat ng mga iba pang mga function

25
00:01:00,410 --> 00:01:02,710
o mga long loop.

26
00:01:02,710 --> 00:01:06,310
Makikita mo na ang mga recursive
mga pamamaraan ay pagpunta sa hitsura para sa mga maikling.

27
00:01:06,310 --> 00:01:10,610
At sila ay talagang ay pagpunta sa gumawa
Mas mukhang maganda ang isang pulutong ng iyong code.

28
00:01:10,610 --> 00:01:12,560
>> Bibigyan kita ng isang halimbawa
ng mga ito upang makita kung paano

29
00:01:12,560 --> 00:01:14,880
maaaring tinukoy ng isang recursive procedure.

30
00:01:14,880 --> 00:01:18,202
Kaya't kung ikaw ay pamilyar sa mga ito
mula sa matematika klase sa maraming mga taon na ang nakaraan,

31
00:01:18,202 --> 00:01:20,910
mayroong isang bagay na tinatawag na ang
factorial function, na kung saan ay karaniwang

32
00:01:20,910 --> 00:01:25,340
naitala bilang isang exclamation point, na
ay tinukoy sa lahat ng positibong integer.

33
00:01:25,340 --> 00:01:28,850
At ang paraan na n
factorial ay kinakalkula

34
00:01:28,850 --> 00:01:31,050
ay mong paramihin ang lahat ng
ang mga numero ng mas mababa sa

35
00:01:31,050 --> 00:01:33,750
o patas sa n together--
lahat ng mga integer na mas mababa sa

36
00:01:33,750 --> 00:01:34,880
o patas sa n magkasama.

37
00:01:34,880 --> 00:01:39,850
>> Kaya 5 factorial ay 5 beses
4 na beses sa 3 beses sa 2 beses 1.

38
00:01:39,850 --> 00:01:43,020
And 4 factorial ay 4 na beses
3 beses sa 2 beses sa 1 at iba pa.

39
00:01:43,020 --> 00:01:44,800
Makukuha mo ang mga ideya.

40
00:01:44,800 --> 00:01:47,060
>> Bilang programmers, ay hindi kami
gumamit n, exclamation point.

41
00:01:47,060 --> 00:01:51,840
Kaya makikita namin tukuyin ang mga factorial
function bilang katunayan ng n.

42
00:01:51,840 --> 00:01:56,897
At gagamitin namin factorial na lumikha
isang recursive solusyon sa isang problema.

43
00:01:56,897 --> 00:01:59,230
At sa tingin ko na maaari mong mahanap
na ito ay isang pulutong mas biswal

44
00:01:59,230 --> 00:02:02,380
akit kaysa sa umuulit
bersyon ng mga ito, na kung saan

45
00:02:02,380 --> 00:02:05,010
gagamitin din namin ang isang tumingin sa ilang mga sandali.

46
00:02:05,010 --> 00:02:08,310
>> Kaya narito ang isang pares ng mga
facts-- pun intended--

47
00:02:08,310 --> 00:02:10,169
tungkol factorial-- ang
factorial function.

48
00:02:10,169 --> 00:02:13,090
Ang factorial ng 1, tulad ng sinabi ko, ay 1.

49
00:02:13,090 --> 00:02:15,690
Ang factorial ng 2 ay 2 beses 1.

50
00:02:15,690 --> 00:02:18,470
Ang factorial ng 3 ay 3
beses 2 beses 1, at iba pa.

51
00:02:18,470 --> 00:02:20,810
Usapan natin ang tungkol sa 4 at 5 na.

52
00:02:20,810 --> 00:02:23,940
>> Ngunit pagtingin sa mga ito, ay hindi totoo?

53
00:02:23,940 --> 00:02:28,220
Ay hindi factorial ng 2 lang
2 beses ang factorial ng 1?

54
00:02:28,220 --> 00:02:31,130
Ibig kong sabihin, ang factorial ng 1 ay 1.

55
00:02:31,130 --> 00:02:34,940
Kaya bakit hindi maaaring sabihin lang namin na,
dahil factorial ng 2 ay 2 beses sa 1,

56
00:02:34,940 --> 00:02:38,520
ito ay talagang 2 beses lang
ang factorial ng 1?

57
00:02:38,520 --> 00:02:40,900
>> At pagkatapos ay pagpapalawak na ideya,
ay hindi ang factorial ng 3

58
00:02:40,900 --> 00:02:44,080
lamang 3 beses ang factorial ng 2?

59
00:02:44,080 --> 00:02:50,350
At ang factorial ng 4 ay 4 na beses
ang factorial ng 3, at iba pa?

60
00:02:50,350 --> 00:02:52,530
Sa katunayan, ang factorial
ng anumang numero Maaari lamang

61
00:02:52,530 --> 00:02:54,660
ipinahayag kung namin uri
ng dalhin ito sa labas magpakailanman.

62
00:02:54,660 --> 00:02:56,870
Maaari namin uri ng tuntuning panlahat
ang factorial problema

63
00:02:56,870 --> 00:02:59,910
bilang na ito ay n beses ang
factorial ng n minus 1.

64
00:02:59,910 --> 00:03:04,840
Ito ay n beses ang produkto ng
lahat ng mga numero na mas mababa kaysa sa akin.

65
00:03:04,840 --> 00:03:08,890
>> Ang ideya na ito, ito
kalahatan ng problema,

66
00:03:08,890 --> 00:03:13,410
ay nagbibigay-daan sa amin upang recursively
tukuyin ang mga factorial function.

67
00:03:13,410 --> 00:03:15,440
Kapag tinukoy mo ang isang function
recursively, may

68
00:03:15,440 --> 00:03:17,470
dalawang bagay na kailangan na maging isang bahagi nito.

69
00:03:17,470 --> 00:03:20,990
Kailangan mong magkaroon ng isang bagay na tinatawag na isang
base kaso, na kung saan, nang ma-trigger mo ito,

70
00:03:20,990 --> 00:03:22,480
titigil ang recursive proseso.

71
00:03:22,480 --> 00:03:25,300
>> Kung hindi man, ang isang function na ang tawag
itself-- bilang maaari mong imagine--

72
00:03:25,300 --> 00:03:26,870
maaaring pumunta sa magpakailanman.

73
00:03:26,870 --> 00:03:29,047
Function tawag function
tawag ang function ng mga tawag

74
00:03:29,047 --> 00:03:30,380
ang function tawag ang function.

75
00:03:30,380 --> 00:03:32,380
Kung hindi ka magkaroon ng isang paraan
upang itigil ito, ang iyong mga program

76
00:03:32,380 --> 00:03:34,760
epektibo ay natigil
sa isang walang-katapusang loop.

77
00:03:34,760 --> 00:03:37,176
Ito ay pag-crash sa huli,
dahil ito ay mauubusan ng memory.

78
00:03:37,176 --> 00:03:38,990
Ngunit na sa tabi ng point.

79
00:03:38,990 --> 00:03:42,210
>> Kailangan namin na magkaroon ng ilang mga iba pang mga paraan upang ihinto ang
mga bagay-bagay maliban sa aming pag-crash na programa,

80
00:03:42,210 --> 00:03:46,010
dahil sa isang programa na nag-crash ay
marahil ay hindi maganda o eleganteng.

81
00:03:46,010 --> 00:03:47,690
At kaya tawag namin ito ang base kaso.

82
00:03:47,690 --> 00:03:50,610
Ito ay isang simpleng solusyon
sa isang problema na tumitigil

83
00:03:50,610 --> 00:03:52,770
ang recursive proseso mula sa nangyari.

84
00:03:52,770 --> 00:03:55,220
Kaya na ang isang bahagi ng
isang recursive function.

85
00:03:55,220 --> 00:03:56,820
>> Ang ikalawang bahagi ay ang recursive kaso.

86
00:03:56,820 --> 00:03:59,195
At ito ay kung saan ang recursion
ay tunay na magaganap.

87
00:03:59,195 --> 00:04:02,200
Ito ay kung saan ang
function ay tumawag mismo.

88
00:04:02,200 --> 00:04:05,940
>> Hindi ito ay tumawag mismo sa eksakto
sa parehong paraan na ito ay tinatawag na.

89
00:04:05,940 --> 00:04:08,880
Makikita ito ay isang bahagyang pagkakaiba-iba
na gumagawa ng mga problemang ito ay

90
00:04:08,880 --> 00:04:11,497
nagsisikap na malutas ang isang maliit bit mas maliit.

91
00:04:11,497 --> 00:04:14,330
Ngunit ito ay karaniwang pumasa sa usang lalaki
ng paglutas sa karamihan ng mga solusyon

92
00:04:14,330 --> 00:04:17,450
sa ibang call down ang linya.

93
00:04:17,450 --> 00:04:20,290
>> Alin sa mga ito na tingin
tulad ng base kaso dito?

94
00:04:20,290 --> 00:04:25,384
Aling isa sa mga ito ay ganito ang hitsura ng
pinakasimpleng solusyon sa isang problema?

95
00:04:25,384 --> 00:04:27,550
Kami ay may isang bungkos ng mga factorials,
at maaari naming patuloy

96
00:04:27,550 --> 00:04:30,470
pagpunta on-- 6, 7, 8, 9, 10, at iba pa.

97
00:04:30,470 --> 00:04:34,130
>> Ngunit isa sa mga ito hitsura tulad ng isang
mahusay na kaso na ang base kaso.

98
00:04:34,130 --> 00:04:35,310
Ito ay isang napaka-simpleng solusyon.

99
00:04:35,310 --> 00:04:37,810
Hindi natin kailangang gawin ang anumang bagay na espesyal.

100
00:04:37,810 --> 00:04:40,560
>> Ang factorial ng 1 ay 1 lang.

101
00:04:40,560 --> 00:04:42,790
Hindi natin kailangang gawin ang anumang
pagpaparami sa lahat.

102
00:04:42,790 --> 00:04:45,248
Tila tulad ng kung kami ay pagpunta
upang subukan at malutas ang problemang ito,

103
00:04:45,248 --> 00:04:47,600
at kailangan naming ihinto ang
recursion sa isang lugar,

104
00:04:47,600 --> 00:04:50,610
marahil gusto nating huminto
ito kapag kami makakuha ng hanggang 1.

105
00:04:50,610 --> 00:04:54,580
Hindi namin nais na huminto sa bago na.

106
00:04:54,580 --> 00:04:56,660
>> Kaya kung kami ay pagtukoy
aming factorial function,

107
00:04:56,660 --> 00:04:58,690
narito ang isang balangkas para sa
kung paano namin maaaring gawin iyon.

108
00:04:58,690 --> 00:05:03,110
Kailangan namin mag-plug ng mga dalawang bagay-
ang base kaso at ang recursive kaso.

109
00:05:03,110 --> 00:05:04,990
Ano ang base kaso?

110
00:05:04,990 --> 00:05:10,150
Kung n ay katumbas ng 1, bumalik 1-- na
isang tunay na simpleng problema sa paglutas.

111
00:05:10,150 --> 00:05:11,890
>> Ang factorial ng 1 ay 1.

112
00:05:11,890 --> 00:05:13,860
Ito ay hindi 1 beses kahit ano.

113
00:05:13,860 --> 00:05:15,020
Ito ay 1 lang.

114
00:05:15,020 --> 00:05:17,170
Ito ay isang napakadaling katotohanan.

115
00:05:17,170 --> 00:05:19,620
At sa gayon ay maaari maging ang aming base kaso.

116
00:05:19,620 --> 00:05:24,730
Kung kami makakuha ng lumipas 1 sa ito
function, babalik kami 1 lang.

117
00:05:24,730 --> 00:05:27,320
>> Ano ang recursive
kaso malamang ganito ang hitsura?

118
00:05:27,320 --> 00:05:32,445
Para sa lahat ng iba pang numero
bukod sa 1, ano ang pattern?

119
00:05:32,445 --> 00:05:35,780
Well, kung kami ay pagkuha
ang factorial ng n,

120
00:05:35,780 --> 00:05:38,160
ito ay n beses ang factorial ng n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Kung kami ay ang pagkuha ng mga factorial ng 3,
ito ay 3 beses ang factorial ng 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
At kaya kung kami ay hindi
naghahanap sa 1, kung hindi,

124
00:05:47,330 --> 00:05:51,710
return n beses ang
factorial ng n minus 1.

125
00:05:51,710 --> 00:05:53,210
Ito ay medyo tapat.

126
00:05:53,210 --> 00:05:57,360
>> At para sa kapakanan ng pagkakaroon ng bahagyang
mas malinis at mas eleganteng code,

127
00:05:57,360 --> 00:06:01,440
malaman na kung kami ay may single-line loops
o single-line kondisyon sanga,

128
00:06:01,440 --> 00:06:04,490
maaari naming kumuha alisan ng lahat ng mga
curly braces sa kanilang paligid.

129
00:06:04,490 --> 00:06:06,850
Kaya maaari naming pagsamahin ito sa mga ito.

130
00:06:06,850 --> 00:06:09,640
Ito ay eksakto ang parehong
functionality bilang na ito.

131
00:06:09,640 --> 00:06:13,850
>> Tingin lang ako sa pagkuha ng malayo ang kulot
braces, dahil mayroon lamang isang linya

132
00:06:13,850 --> 00:06:18,500
sa loob ng mga kondisyon sanga.

133
00:06:18,500 --> 00:06:21,160
Kaya ang mga ito kumilos na magkapareho.

134
00:06:21,160 --> 00:06:23,800
Kung n ay katumbas ng 1, bumalik 1.

135
00:06:23,800 --> 00:06:28,351
Kung hindi man bumalik n ulit
ang factorial ng n minus 1.

136
00:06:28,351 --> 00:06:29,850
Kaya ginagawa namin ang problema mas maliit.

137
00:06:29,850 --> 00:06:33,850
Kung n nagsisimula bilang 5, kami ay pagpunta sa
bumalik 5 beses ang factorial ng 4.

138
00:06:33,850 --> 00:06:37,100
At kami na makita sa isang minuto kapag ang usapan namin
tungkol sa stack-- tawag sa isa pang video

139
00:06:37,100 --> 00:06:39,390
kung saan ang pinag-uusapan natin ang
tumawag stack-- namin malaman

140
00:06:39,390 --> 00:06:41,630
tungkol sa kung bakit gumagana nang eksakto ang proseso na ito.

141
00:06:41,630 --> 00:06:46,970
>> Ngunit habang factorial 5 sabi
bumalik 5 beses factorial ng 4, at 4

142
00:06:46,970 --> 00:06:49,710
ay pagpunta sa sabihin, OK, well, return
4 na beses ang factorial ng 3.

143
00:06:49,710 --> 00:06:51,737
At tulad ng makikita mo, hindi namin
uri ng papalapit 1.

144
00:06:51,737 --> 00:06:53,820
Kami ay nakakakuha ng mas malapit at
mas malapit sa na base kaso.

145
00:06:53,820 --> 00:06:58,180
>> At sa sandaling pindutin namin ang base kaso,
lahat ng mga nakaraang mga pag-andar

146
00:06:58,180 --> 00:07:00,540
magkakaroon ng sagot na kanilang hinahanap.

147
00:07:00,540 --> 00:07:03,900
Factorial ng 2 ay sinasabi return
2 beses ang factorial ng 1.

148
00:07:03,900 --> 00:07:06,760
Well, factorial ng 1 nagbabalik 1.

149
00:07:06,760 --> 00:07:10,090
Kaya ang tawag para sa factorial
ng 2 makakabalik 2 beses sa 1,

150
00:07:10,090 --> 00:07:13,980
at bigyan na bumalik sa factorial ng
3, na kung saan ay naghihintay para sa resultang iyon.

151
00:07:13,980 --> 00:07:17,110
>> At pagkatapos ay maaari itong makalkula
kanyang resulta, 3 beses 2 ay 6,

152
00:07:17,110 --> 00:07:18,907
at nagbibigay ng mga ito pabalik sa factorial ng 4.

153
00:07:18,907 --> 00:07:20,740
At muli, kami ay may isang
video sa stack ng tawag

154
00:07:20,740 --> 00:07:23,810
kung saan ito ay may larawan ng isang maliit na
higit sa kung ano ang sinasabi ko ngayon.

155
00:07:23,810 --> 00:07:25,300
Ngunit ito ay ito.

156
00:07:25,300 --> 00:07:29,300
Ito nag-iisa ay ang solusyon sa
pagkalkula ng factorial ng isang numero.

157
00:07:29,300 --> 00:07:31,527
>> Ito ay linya lamang ang apat ng mga code.

158
00:07:31,527 --> 00:07:32,610
Iyan ay medyo cool, di ba?

159
00:07:32,610 --> 00:07:35,480
Ito ay uri ng sexy.

160
00:07:35,480 --> 00:07:38,580
>> Kaya sa pangkalahatan, ngunit hindi
laging, isang recursive function

161
00:07:38,580 --> 00:07:41,190
maaaring palitan ng isang loop sa isang
non-recursive function.

162
00:07:41,190 --> 00:07:46,100
Kaya dito, tabi-tabi, ay ang umuulit
bersyon ng factorial function.

163
00:07:46,100 --> 00:07:49,650
Pareho sa mga ito ang Calculate
eksakto ang parehong bagay.

164
00:07:49,650 --> 00:07:52,170
>> Sila ay parehong makalkula ang factorial ng n.

165
00:07:52,170 --> 00:07:54,990
Ang bersyon sa kaliwa
ay gumagamit ng recursion na gawin ito.

166
00:07:54,990 --> 00:07:58,320
Ang bersyon sa kanan
ay gumagamit ng pag-ulit upang gawin ito.

167
00:07:58,320 --> 00:08:02,050
>> At pansinin, mayroon kaming na idedeklara
isang variable ng isang produkto ng integer.

168
00:08:02,050 --> 00:08:02,940
At pagkatapos naming loop.

169
00:08:02,940 --> 00:08:06,790
Hanggat n ay mas malaki kaysa sa 0, kami ay
panatilihin ang pag-multiply na produkto sa pamamagitan n

170
00:08:06,790 --> 00:08:09,890
at decrementing n hanggang
namin makalkula ang mga produkto.

171
00:08:09,890 --> 00:08:14,600
Kaya ang dalawang pag-andar, muli,
gawin ang eksaktong parehong bagay.

172
00:08:14,600 --> 00:08:19,980
Subalit hindi nila gawin ito sa
eksakto sa parehong paraan.

173
00:08:19,980 --> 00:08:22,430
>> Ngayon, ito ay posible na
may higit sa isang base

174
00:08:22,430 --> 00:08:25,770
kaso o higit pa sa isang
recursive kaso, depende

175
00:08:25,770 --> 00:08:27,670
sa kung ano ang iyong function na ay sinusubukan na gawin.

176
00:08:27,670 --> 00:08:31,650
Ay hindi kinakailangan mo lamang limitado sa
isang solong base kaso o isang solong recursive

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

178
00:08:32,370 --> 00:08:35,320
Kaya ang isang halimbawa ng isang bagay
may maramihang base kaso

179
00:08:35,320 --> 00:08:37,830
maaaring this-- ang
Fibonacci number sequence.

180
00:08:37,830 --> 00:08:41,549
>> Maaari mong isipin ang mula sa
elementarya araw ng paaralan

181
00:08:41,549 --> 00:08:45,740
na ang pagkakasunod-sunod Fibonacci ay tinukoy
tulad this-- ang unang elemento ay 0.

182
00:08:45,740 --> 00:08:46,890
Ang pangalawang elemento ay 1.

183
00:08:46,890 --> 00:08:49,230
Pareho sa mga ito ay sa pamamagitan lamang ng kahulugan.

184
00:08:49,230 --> 00:08:55,920
>> Pagkatapos bawat iba pang mga elemento ay tinukoy
bilang ang kabuuan ng n minus 1 at n minus 2.

185
00:08:55,920 --> 00:09:00,330
Kaya ang ikatlong elemento
ay magiging 0 plus 1 ay 1.

186
00:09:00,330 --> 00:09:03,280
At pagkatapos ay ang ika-apat na elemento
ay ang pangalawang elemento, 1,

187
00:09:03,280 --> 00:09:06,550
plus ang ikatlong elemento, 1.

188
00:09:06,550 --> 00:09:08,507
At iyon ay magiging 2.

189
00:09:08,507 --> 00:09:09,340
At iba pa at iba pa.

190
00:09:09,340 --> 00:09:11,680
>> Kaya sa kasong ito, kami ay may dalawang base kaso.

191
00:09:11,680 --> 00:09:14,850
Kung n ay katumbas ng 1, bumalik 0.

192
00:09:14,850 --> 00:09:18,560
Kung n ay katumbas ng 2, bumalik 1.

193
00:09:18,560 --> 00:09:25,930
Kung hindi, bumalik Fibonacci ng n
minus 1 plus Fibonacci ng n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Kaya na ang maramihang mga base kaso.

195
00:09:27,180 --> 00:09:29,271
Ano ang tungkol sa maramihang recursive kaso?

196
00:09:29,271 --> 00:09:31,520
Well, may isang bagay
tinatawag na ang Collatz haka-haka.

197
00:09:31,520 --> 00:09:34,630
Hindi ako pupunta sa mga sinasabi,
alam mo kung ano na,

198
00:09:34,630 --> 00:09:38,170
dahil ito ay aktwal na ang aming huling
Ang problema para sa partikular na video.

199
00:09:38,170 --> 00:09:43,220
At ito ay ang aming exercise
upang magtulungan pa.

200
00:09:43,220 --> 00:09:46,760
>> Kaya narito ang kung ano ang
Collatz haka-haka is--

201
00:09:46,760 --> 00:09:48,820
ito ay sumasaklaw sa bawat positibong integer.

202
00:09:48,820 --> 00:09:51,500
At ito speculates na ito ay
laging posible upang makabalik

203
00:09:51,500 --> 00:09:55,060
sa 1 kung susundin mo ang mga hakbang na ito.

204
00:09:55,060 --> 00:09:57,560
Kung n ay 1, itigil.

205
00:09:57,560 --> 00:10:00,070
Mayroon kaming bumalik sa 1 kung n ay 1.

206
00:10:00,070 --> 00:10:05,670
>> Kung hindi man, pumunta sa pamamagitan ng
proseso muli sa n hinati sa 2.

207
00:10:05,670 --> 00:10:08,200
At makita kung maaari kang makakuha ng bumalik sa 1.

208
00:10:08,200 --> 00:10:13,260
Kung hindi man, kung n ay kakaiba, pumunta sa pamamagitan ng
ang proseso na ito muli sa 3n plus 1,

209
00:10:13,260 --> 00:10:15,552
o 3 beses n plus 1.

210
00:10:15,552 --> 00:10:17,010
Kaya dito kami ay may isang solong base kaso.

211
00:10:17,010 --> 00:10:18,430
Kung n ay katumbas ng 1, itigil.

212
00:10:18,430 --> 00:10:20,230
Hindi kami gumagawa ng anumang mga mas recursion.

213
00:10:20,230 --> 00:10:23,730
>> Ngunit kami ay may dalawang recursive kaso.

214
00:10:23,730 --> 00:10:28,750
Kung n ay kahit na, ginagawa namin ang isa recursive
kaso, pagtawag n hinati sa 2.

215
00:10:28,750 --> 00:10:33,950
Kung n ay kakaiba, gawin namin ang isang iba't ibang mga
recursive kaso sa 3 beses n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> At upang ang mga layunin para sa video na ito ay
upang kumuha ng isang segundo, i-pause ang video,

217
00:10:39,120 --> 00:10:42,440
at subukan at isulat ito
recursive function Collatz

218
00:10:42,440 --> 00:10:47,640
kung saan kayo na ipasa sa ang halaga ng n, at
ito kinakalkula kung gaano karaming mga hakbang na ito

219
00:10:47,640 --> 00:10:52,430
kinakailangan upang makakuha ng sa 1 kung nagsimula ka mula n
at susundin mo ang mga hakbang na ito up sa itaas.

220
00:10:52,430 --> 00:10:56,660
Kung n ay 1, ito ay tumatagal ng 0 na mga hakbang.

221
00:10:56,660 --> 00:11:00,190
Kung hindi man, ito ay pagpunta sa
kumuha ng isang hakbang plus gayunpaman

222
00:11:00,190 --> 00:11:06,200
maraming mga hakbang na ito ay tumatagal sa alinman n
hinati sa 2 kung n ay kahit na, o 3n plus 1

223
00:11:06,200 --> 00:11:08,100
kung n ay kakaiba.

224
00:11:08,100 --> 00:11:11,190
>> Ngayon, na ilagay up ako sa screen dito
isang pares ng mga pagsubok para sa iyo,

225
00:11:11,190 --> 00:11:15,690
isang pares ng mga kaso pagsusuri para sa iyo, upang makita
kung ano ang mga iba't-ibang numero Collatz ay,

226
00:11:15,690 --> 00:11:17,440
at din ng isang paglalarawan ng halimbawa
sa mga hakbang na

227
00:11:17,440 --> 00:11:20,390
kailangan ay wala na sa pamamagitan gayon ay maaari mo
uri ng makita ang proseso na ito sa aksyon.

228
00:11:20,390 --> 00:11:24,222
Kaya kung n ay katumbas ng
1, Collatz ng n ay 0.

229
00:11:24,222 --> 00:11:26,180
Hindi mo na kailangang gawin
anumang bagay upang makabalik sa 1.

230
00:11:26,180 --> 00:11:27,600
Ikaw ay naka-doon.

231
00:11:27,600 --> 00:11:30,550
>> Kung n ay 2, ito ay tumatagal ng
isang hakbang upang makakuha ng 1.

232
00:11:30,550 --> 00:11:31,810
Magsisimula ka na may 2.

233
00:11:31,810 --> 00:11:33,100
Well, 2 ay hindi katumbas ng 1.

234
00:11:33,100 --> 00:11:36,580
Kaya ito ay magiging isang hakbang
plus gayunpaman maraming mga hakbang na ito

235
00:11:36,580 --> 00:11:38,015
tumatagal sa n hinati sa 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 hinati sa 2 ay 1.

238
00:11:42,910 --> 00:11:47,200
Kaya ito ay tumatagal ng isang hakbang plus gayunpaman
maraming mga hakbang na kailangan para sa 1.

239
00:11:47,200 --> 00:11:49,720
1 ay dadalhin zero na mga hakbang.

240
00:11:49,720 --> 00:11:52,370
>> Para sa 3, tulad ng makikita mo, may
kasangkot lubos ng ilang mga hakbang.

241
00:11:52,370 --> 00:11:53,590
Pumunta ka mula sa 3.

242
00:11:53,590 --> 00:11:56,710
At pagkatapos mong pumunta sa
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Ito ay tumatagal ng pitong mga hakbang upang makabalik sa 1.

244
00:11:58,804 --> 00:12:01,220
At tulad ng makikita mo, may isang
ilang iba pang mga kaso ng pagsubok dito

245
00:12:01,220 --> 00:12:02,470
upang subukan ang iyong mga programa.

246
00:12:02,470 --> 00:12:03,970
Kaya muli, i-pause ang video.

247
00:12:03,970 --> 00:12:09,210
At kukunin ko na pumunta lumipat pabalik ngayon upang
kung ano ang aktwal na proseso ay dito,

248
00:12:09,210 --> 00:12:11,390
kung ano ang ito haka-haka ay.

249
00:12:11,390 --> 00:12:14,140
>> Tingnan kung maaari mong malaman kung
kung paano matukoy Collatz ng n

250
00:12:14,140 --> 00:12:19,967
upang ito ay kinakalkula kung gaano karaming
hakbang na aabutin upang makakuha ng 1.

251
00:12:19,967 --> 00:12:23,050
Kaya sana, ikaw ay naka-pause ang video
at ikaw ay hindi lamang naghihintay para sa akin

252
00:12:23,050 --> 00:12:25,820
upang mabigyan ka ng sagot dito.

253
00:12:25,820 --> 00:12:29,120
Ngunit kung ikaw ay, well,
narito pa rin ang sagot.

254
00:12:29,120 --> 00:12:33,070
>> Kaya dito ang isang posibleng kahulugan
ng Collatz function.

255
00:12:33,070 --> 00:12:35,610
Ang aming base case-- kung n ay
katumbas ng 1, bumalik kami 0.

256
00:12:35,610 --> 00:12:38,250
Ito ay hindi kumuha ng anumang mga
hakbang na ito upang makakuha ng bumalik sa 1.

257
00:12:38,250 --> 00:12:42,710
>> Kung hindi man, kami ay may dalawang recursive cases--
isa para sa kahit na mga numero at ang isa ay para sa kakaiba.

258
00:12:42,710 --> 00:12:47,164
Ang paraan test ko para sa kahit na mga numero
ay upang suriin kung n mod 2 ay katumbas ng 0.

259
00:12:47,164 --> 00:12:49,080
Ito ay isa lamang, muli,
humihingi ng tanong,

260
00:12:49,080 --> 00:12:54,050
kung isipin mo kung ano ang mod is-- kung ako
hatiin n pamamagitan ng 2 ay may walang nalalabing?

261
00:12:54,050 --> 00:12:55,470
Iyon ay magiging isang kahit na numero.

262
00:12:55,470 --> 00:13:01,370
>> At kaya kung n mod 2 ay katumbas ng 0 ay
testing ay ito ng isang kahit na numero.

263
00:13:01,370 --> 00:13:04,250
Kung gayon, gusto kong bumalik 1,
dahil ito ay siguradong

264
00:13:04,250 --> 00:13:09,270
pagkuha ng isang hakbang plus Collatz ng
kahit anong numero ay kalahati ng sa akin.

265
00:13:09,270 --> 00:13:13,910
Kung hindi man, gusto kong bumalik 1
plus Collatz ng 3 beses n plus 1.

266
00:13:13,910 --> 00:13:16,060
Iyon ay ang iba pang mga
recursive step na tayo

267
00:13:16,060 --> 00:13:19,470
maaaring tumagal ng upang makalkula ang
Collatz-- ang bilang ng mga hakbang

268
00:13:19,470 --> 00:13:22,610
ito ay tumatagal upang makabalik
sa 1 bibigyan ng isang numero.

269
00:13:22,610 --> 00:13:24,610
Kaya sana, halimbawa na ito
nagbigay sa iyo ng isang maliit na piraso

270
00:13:24,610 --> 00:13:26,620
ng isang lasa ng recursive pamamaraan.

271
00:13:26,620 --> 00:13:30,220
Sana, sa tingin mo na code ay isang
maliit na mas maganda kung ipinatupad

272
00:13:30,220 --> 00:13:32,760
sa isang eleganteng, recursive na paraan.

273
00:13:32,760 --> 00:13:35,955
Ngunit kahit na hindi, recursion ay isang
talagang malakas na kasangkapan gayunman.

274
00:13:35,955 --> 00:13:38,330
At sa gayon ito ay talagang isang bagay
upang makakuha ng inyong ulo sa paligid,

275
00:13:38,330 --> 00:13:41,360
dahil ikaw ay maaaring lumikha ng
medyo cool programa gamit recursion

276
00:13:41,360 --> 00:13:45,930
na maaaring sa kabilang banda ay mahirap unawain na magsulat
kung gumagamit ka ng mga loop at pag-ulit.

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

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

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