1
00:00:00,000 --> 00:00:05,860
>> [Bermain muzik]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Anda mungkin berfikir bahawa
kod hanya digunakan untuk menyelesaikan sesuatu tugas.

3
00:00:09,530 --> 00:00:10,450
Anda menulis keluar.

4
00:00:10,450 --> 00:00:11,664
Ia melakukan sesuatu.

5
00:00:11,664 --> 00:00:12,580
Yang cukup banyak ia.

6
00:00:12,580 --> 00:00:13,160
>> Anda menyusun ia.

7
00:00:13,160 --> 00:00:13,993
Anda menjalankan program ini.

8
00:00:13,993 --> 00:00:15,370
Anda baik untuk pergi.

9
00:00:15,370 --> 00:00:17,520
>> Tetapi percaya atau tidak, jika
anda kod untuk masa yang lama,

10
00:00:17,520 --> 00:00:20,550
anda sebenarnya mungkin datang untuk melihat
kod sebagai sesuatu yang indah.

11
00:00:20,550 --> 00:00:23,275
Ia menyelesaikan masalah di
cara yang sangat menarik,

12
00:00:23,275 --> 00:00:26,510
atau ada hanya sesuatu yang benar-benar
kemas tentang cara ia kelihatan.

13
00:00:26,510 --> 00:00:28,750
Anda mungkin ketawa
pada saya, tetapi ia adalah benar.

14
00:00:28,750 --> 00:00:31,530
Dan rekursi adalah salah satu cara
untuk menyusun mendapat idea ini

15
00:00:31,530 --> 00:00:34,090
cantik, anggun-cari kod.

16
00:00:34,090 --> 00:00:37,740
Ia menyelesaikan masalah dengan cara yang
yang menarik, mudah untuk menggambarkan,

17
00:00:37,740 --> 00:00:39,810
dan menghairankan pendek.

18
00:00:39,810 --> 00:00:43,190
>> Kerja-kerja cara rekursi
adalah, fungsi rekursi

19
00:00:43,190 --> 00:00:49,291
ditakrifkan sebagai fungsi yang menyeru
sendiri sebagai sebahagian daripada pelaksanaannya.

20
00:00:49,291 --> 00:00:51,790
Yang mungkin kelihatan sedikit pelik,
dan kita akan melihat sedikit

21
00:00:51,790 --> 00:00:53,750
tentang bagaimana kerja-kerja ini dalam seketika.

22
00:00:53,750 --> 00:00:55,560
Tetapi sekali lagi, ini
prosedur rekursi adalah

23
00:00:55,560 --> 00:00:57,730
akan menjadi begitu elegan
kerana mereka akan

24
00:00:57,730 --> 00:01:00,410
untuk menyelesaikan masalah ini tanpa
yang mempunyai semua fungsi-fungsi lain

25
00:01:00,410 --> 00:01:02,710
atau ini gelung panjang.

26
00:01:02,710 --> 00:01:06,310
Anda akan melihat bahawa ini rekursi
prosedur akan kelihatan begitu pendek.

27
00:01:06,310 --> 00:01:10,610
Dan mereka benar-benar akan membuat
kod anda kelihatan lebih lebih cantik.

28
00:01:10,610 --> 00:01:12,560
>> Saya akan memberikan contoh
ini untuk melihat bagaimana

29
00:01:12,560 --> 00:01:14,880
prosedur rekursi mungkin ditakrifkan.

30
00:01:14,880 --> 00:01:18,202
Jadi, jika anda sudah biasa dengan ini
dari kelas matematik tahun yang lalu,

31
00:01:18,202 --> 00:01:20,910
ada yang sesuatu yang dinamakan
fungsi faktorial, yang biasanya

32
00:01:20,910 --> 00:01:25,340
ditandakan sebagai tanda seru, yang
ditakrifkan atas semua integer positif.

33
00:01:25,340 --> 00:01:28,850
Dan cara yang n
faktorial dikira

34
00:01:28,850 --> 00:01:31,050
adalah anda membiak semua
nombor kurang daripada

35
00:01:31,050 --> 00:01:33,750
atau sama dengan n together--
semua integer kurang daripada

36
00:01:33,750 --> 00:01:34,880
atau sama dengan n bersama-sama.

37
00:01:34,880 --> 00:01:39,850
>> Jadi 5 faktorial adalah 5 kali
4 kali 3 kali 2 kali 1.

38
00:01:39,850 --> 00:01:43,020
Dan 4 faktorial adalah 4 kali
3 kali 2 kali 1 dan sebagainya.

39
00:01:43,020 --> 00:01:44,800
Anda akan mendapat idea.

40
00:01:44,800 --> 00:01:47,060
>> Sebagai pengaturcara, kita tidak
menggunakan n, tanda seru.

41
00:01:47,060 --> 00:01:51,840
Oleh itu, kita akan menentukan faktorial
berfungsi sebagai hakikat n.

42
00:01:51,840 --> 00:01:56,897
Dan kami akan menggunakan faktorial untuk mewujudkan
penyelesaian rekursi kepada masalah.

43
00:01:56,897 --> 00:01:59,230
Dan saya fikir anda mungkin mendapati
bahawa ia banyak lebih visual

44
00:01:59,230 --> 00:02:02,380
menarik daripada lelaran
versi ini, yang

45
00:02:02,380 --> 00:02:05,010
kami juga akan mengambil lihat di dalam seketika.

46
00:02:05,010 --> 00:02:08,310
>> Jadi di sini adalah beberapa
pun facts-- intended--

47
00:02:08,310 --> 00:02:10,169
tentang factorial-- yang
fungsi faktorial.

48
00:02:10,169 --> 00:02:13,090
Faktorial 1, seperti yang saya katakan, adalah 1.

49
00:02:13,090 --> 00:02:15,690
Faktorial 2 adalah 2 kali 1.

50
00:02:15,690 --> 00:02:18,470
Faktorial 3 adalah 3
kali 2 kali 1, dan sebagainya.

51
00:02:18,470 --> 00:02:20,810
Kita bercakap tentang 4 dan 5 sudah.

52
00:02:20,810 --> 00:02:23,940
>> Tetapi melihat ini, tidak adakah ini benar?

53
00:02:23,940 --> 00:02:28,220
Bukankah faktorial 2 Sama
2 kali faktorial 1?

54
00:02:28,220 --> 00:02:31,130
Maksud saya, faktorial 1 adalah 1.

55
00:02:31,130 --> 00:02:34,940
Jadi mengapa tidak boleh kita hanya mengatakan bahawa,
sejak faktorial 2 adalah 2 kali 1,

56
00:02:34,940 --> 00:02:38,520
ia adalah benar-benar hanya 2 kali
faktorial 1?

57
00:02:38,520 --> 00:02:40,900
>> Dan kemudian melanjutkan idea itu,
tidak faktorial 3

58
00:02:40,900 --> 00:02:44,080
hanya 3 kali faktorial 2?

59
00:02:44,080 --> 00:02:50,350
Dan faktorial 4 adalah 4 kali
faktorial 3, dan sebagainya?

60
00:02:50,350 --> 00:02:52,530
Malah, faktorial yang
mana-mana nombor boleh hanya

61
00:02:52,530 --> 00:02:54,660
dinyatakan jika kita jenis
untuk melaksanakan ini selama-lamanya.

62
00:02:54,660 --> 00:02:56,870
Kita boleh jenis umum
masalah faktorial

63
00:02:56,870 --> 00:02:59,910
kerana ia adalah n kali
faktorial n tolak 1.

64
00:02:59,910 --> 00:03:04,840
Ia adalah n kali hasil daripada
semua nombor yang kurang daripada saya.

65
00:03:04,840 --> 00:03:08,890
>> Idea ini, ini
generalisasi masalah ini,

66
00:03:08,890 --> 00:03:13,410
membolehkan kita untuk secara rekursif
menentukan fungsi faktorial.

67
00:03:13,410 --> 00:03:15,440
Apabila anda menentukan fungsi
secara berulang, ada

68
00:03:15,440 --> 00:03:17,470
dua perkara yang perlu menjadi sebahagian daripadanya.

69
00:03:17,470 --> 00:03:20,990
Anda perlu mempunyai sesuatu yang dipanggil
kes asas, yang apabila anda mencetuskan ia,

70
00:03:20,990 --> 00:03:22,480
akan menghentikan proses rekursi.

71
00:03:22,480 --> 00:03:25,300
>> Jika tidak, satu majlis yang menyeru
itself-- kerana anda mungkin imagine--

72
00:03:25,300 --> 00:03:26,870
boleh pergi selama-lamanya.

73
00:03:26,870 --> 00:03:29,047
Fungsi panggilan fungsi
memanggil panggilan fungsi

74
00:03:29,047 --> 00:03:30,380
fungsi panggilan fungsi.

75
00:03:30,380 --> 00:03:32,380
Jika anda tidak mempunyai cara yang
untuk menghentikannya, program anda

76
00:03:32,380 --> 00:03:34,760
akan terperangkap dengan berkesan
di gelung tak terhingga.

77
00:03:34,760 --> 00:03:37,176
Ia akan kemalangan akhirnya,
kerana ia akan kehabisan memori.

78
00:03:37,176 --> 00:03:38,990
Tetapi itu pokoknya.

79
00:03:38,990 --> 00:03:42,210
>> Kita perlu mempunyai cara lain untuk menghentikan
perkara selain terhempas program kami,

80
00:03:42,210 --> 00:03:46,010
kerana program yang kemalangan adalah
mungkin tidak cantik atau elegan.

81
00:03:46,010 --> 00:03:47,690
Dan dengan itu kita panggil ini kes asas.

82
00:03:47,690 --> 00:03:50,610
Ini adalah penyelesaian yang mudah
kepada masalah yang berhenti

83
00:03:50,610 --> 00:03:52,770
proses rekursi daripada berlaku.

84
00:03:52,770 --> 00:03:55,220
Jadi itulah satu bahagian
fungsi rekursi.

85
00:03:55,220 --> 00:03:56,820
>> Bahagian kedua adalah kes rekursi.

86
00:03:56,820 --> 00:03:59,195
Dan di sinilah rekursi
sebenarnya akan berlaku.

87
00:03:59,195 --> 00:04:02,200
Ini adalah di mana
fungsi akan memanggil sendiri.

88
00:04:02,200 --> 00:04:05,940
>> Ia tidak menghukum dirinya betul-betul
cara yang sama ia dipanggil.

89
00:04:05,940 --> 00:04:08,880
Ia akan menjadi sedikit perbezaan
yang membuat masalah itu

90
00:04:08,880 --> 00:04:11,497
cuba untuk menyelesaikan sedikit pemudi yang lebih kecil.

91
00:04:11,497 --> 00:04:14,330
Tetapi ia secara amnya pas tanggungjawab itu
menyelesaikan sebahagian besar daripada penyelesaian

92
00:04:14,330 --> 00:04:17,450
panggilan yang berbeza ke bawah baris.

93
00:04:17,450 --> 00:04:20,290
>> Yang kelihatan ini
seperti kes asas di sini?

94
00:04:20,290 --> 00:04:25,384
Yang mana satu kelihatan seperti ini
penyelesaian paling mudah untuk masalah?

95
00:04:25,384 --> 00:04:27,550
Kami mempunyai sekumpulan faktorial,
dan kita boleh terus

96
00:04:27,550 --> 00:04:30,470
akan pada-- 6, 7, 8, 9, 10, dan sebagainya.

97
00:04:30,470 --> 00:04:34,130
>> Tetapi salah satu kelihatan seperti ini
kes baik untuk menjadi kes asas.

98
00:04:34,130 --> 00:04:35,310
Ia adalah penyelesaian yang sangat mudah.

99
00:04:35,310 --> 00:04:37,810
Kami tidak mempunyai berbuat apa-apa yang istimewa.

100
00:04:37,810 --> 00:04:40,560
>> Faktorial 1 hanya 1.

101
00:04:40,560 --> 00:04:42,790
Kami tidak mempunyai melakukan apa-apa
pendaraban sama sekali.

102
00:04:42,790 --> 00:04:45,248
Ia seolah-olah seperti jika kita akan
untuk mencuba dan menyelesaikan masalah ini,

103
00:04:45,248 --> 00:04:47,600
dan kita perlu untuk menghentikan
jadi semula di suatu tempat,

104
00:04:47,600 --> 00:04:50,610
kita mungkin mahu berhenti
apabila kita dapat 1.

105
00:04:50,610 --> 00:04:54,580
Kami tidak mahu berhenti sebelum itu.

106
00:04:54,580 --> 00:04:56,660
>> Jadi, jika kita menentukan
fungsi faktorial kami,

107
00:04:56,660 --> 00:04:58,690
di sini adalah rangka untuk
bagaimana kita boleh berbuat demikian.

108
00:04:58,690 --> 00:05:03,110
Kita perlu pasangkan kedua-dua things--
kes asas dan kes rekursi.

109
00:05:03,110 --> 00:05:04,990
Apakah kes asas?

110
00:05:04,990 --> 00:05:10,150
Jika n adalah sama dengan 1, kembali 1-- itulah
masalah benar-benar mudah untuk menyelesaikan.

111
00:05:10,150 --> 00:05:11,890
>> Faktorial 1 adalah 1.

112
00:05:11,890 --> 00:05:13,860
Ia bukan 1 kali apa-apa.

113
00:05:13,860 --> 00:05:15,020
Ia hanya 1.

114
00:05:15,020 --> 00:05:17,170
Ia adalah satu fakta yang sangat mudah.

115
00:05:17,170 --> 00:05:19,620
Dan sebagainya yang boleh menjadi kes asas kami.

116
00:05:19,620 --> 00:05:24,730
Jika kita mendapat lulus 1 ke dalam ini
fungsi, kita hanya akan kembali 1.

117
00:05:24,730 --> 00:05:27,320
>> Apa yang rekursi yang
kes mungkin kelihatan seperti?

118
00:05:27,320 --> 00:05:32,445
Bagi setiap nombor lain
selain 1, apa corak?

119
00:05:32,445 --> 00:05:35,780
Nah, jika kami mengambil
faktorial n,

120
00:05:35,780 --> 00:05:38,160
ia n kali faktorial n tolak 1.

121
00:05:38,160 --> 00:05:42,130
>> Jika kita mengambil faktorial sebanyak 3,
ia 3 kali faktorial 3 tolak 1,

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

123
00:05:43,070 --> 00:05:47,330
Dan jadi jika kita tidak
melihat 1, jika tidak,

124
00:05:47,330 --> 00:05:51,710
pulangan n kali
faktorial n tolak 1.

125
00:05:51,710 --> 00:05:53,210
Ia agak mudah.

126
00:05:53,210 --> 00:05:57,360
>> Dan demi yang mempunyai sedikit
lebih bersih dan lebih elegan kod,

127
00:05:57,360 --> 00:06:01,440
tahu bahawa jika kita mempunyai gelung tunggal talian
atau tunggal talian cawangan bersyarat,

128
00:06:01,440 --> 00:06:04,490
kita boleh menghilangkan semua daripada
pendakap kerinting di sekeliling mereka.

129
00:06:04,490 --> 00:06:06,850
Oleh itu, kita boleh menggabungkan ini dengan ini.

130
00:06:06,850 --> 00:06:09,640
Ini mempunyai sama
fungsi seperti ini.

131
00:06:09,640 --> 00:06:13,850
>> Saya hanya mengambil dari kerinting
kawat gigi, kerana ada hanya satu baris

132
00:06:13,850 --> 00:06:18,500
dalam orang-orang cawangan bersyarat.

133
00:06:18,500 --> 00:06:21,160
Jadi ini berkelakuan sepercaman.

134
00:06:21,160 --> 00:06:23,800
Jika n adalah sama dengan 1, kembali 1.

135
00:06:23,800 --> 00:06:28,351
Jika tidak kembali n kali
faktorial n tolak 1.

136
00:06:28,351 --> 00:06:29,850
Jadi, kita membuat masalah yang lebih kecil.

137
00:06:29,850 --> 00:06:33,850
Jika n bermula sebagai 5, kita akan
kembali 5 kali faktorial 4.

138
00:06:33,850 --> 00:06:37,100
Dan kita akan melihat dalam satu minit apabila kita bercakap
tentang stack-- panggilan dalam video lain

139
00:06:37,100 --> 00:06:39,390
di mana kita bercakap mengenai
memanggil stack-- kita akan belajar

140
00:06:39,390 --> 00:06:41,630
tentang mengapa sebenarnya proses ini berfungsi.

141
00:06:41,630 --> 00:06:46,970
>> Tetapi manakala faktorial 5 mengatakan
kembali 5 kali faktorial 4, dan 4

142
00:06:46,970 --> 00:06:49,710
akan berkata, OK, baik, pulangan
4 kali faktorial 3.

143
00:06:49,710 --> 00:06:51,737
Dan seperti yang anda boleh lihat, kami
semacam menghampiri 1.

144
00:06:51,737 --> 00:06:53,820
Kami mendapat lebih dekat dan
lebih dekat dengan kes asas.

145
00:06:53,820 --> 00:06:58,180
>> Dan apabila kita mencapai kes asas,
semua fungsi sebelum

146
00:06:58,180 --> 00:07:00,540
mempunyai jawapan yang mereka cari.

147
00:07:00,540 --> 00:07:03,900
Faktorial 2 telah berkata pulangan
2 kali faktorial 1.

148
00:07:03,900 --> 00:07:06,760
Nah, faktorial 1 mengembalikan 1.

149
00:07:06,760 --> 00:07:10,090
Jadi panggilan untuk faktorial
2 boleh kembali 2 kali 1,

150
00:07:10,090 --> 00:07:13,980
dan memberikan yang kembali ke faktorial
3, yang sedang menunggu untuk keputusan itu.

151
00:07:13,980 --> 00:07:17,110
>> Dan kemudian ia boleh mengira
hasilnya, 3 kali 2 ialah 6,

152
00:07:17,110 --> 00:07:18,907
dan memberikan kembali kepada faktorial 4.

153
00:07:18,907 --> 00:07:20,740
Dan sekali lagi, kita mempunyai
video pada timbunan panggilan

154
00:07:20,740 --> 00:07:23,810
di mana ini digambarkan sedikit
lebih daripada apa yang saya katakan sekarang.

155
00:07:23,810 --> 00:07:25,300
Tetapi ini adalah ia.

156
00:07:25,300 --> 00:07:29,300
Ini sahaja adalah penyelesaian untuk
mengira faktorial bagi nombor.

157
00:07:29,300 --> 00:07:31,527
>> Ia hanya empat baris kod.

158
00:07:31,527 --> 00:07:32,610
Yang agak sejuk, bukan?

159
00:07:32,610 --> 00:07:35,480
Ia adalah jenis seksi.

160
00:07:35,480 --> 00:07:38,580
>> Jadi secara umum, tetapi tidak
biasa, fungsi rekursi

161
00:07:38,580 --> 00:07:41,190
boleh menggantikan gelung dalam
fungsi bukan rekursi.

162
00:07:41,190 --> 00:07:46,100
Jadi di sini, sebelah menyebelah, adalah lelaran
versi fungsi faktorial.

163
00:07:46,100 --> 00:07:49,650
Kedua-dua mengira ini
perkara yang sama.

164
00:07:49,650 --> 00:07:52,170
>> Mereka berdua mengira faktorial n.

165
00:07:52,170 --> 00:07:54,990
Versi di sebelah kiri
menggunakan rekursi untuk melakukannya.

166
00:07:54,990 --> 00:07:58,320
Versi di sebelah kanan
menggunakan lelaran untuk melakukannya.

167
00:07:58,320 --> 00:08:02,050
>> Dan notis, kita perlu mengisytiharkan
pembolehubah produk integer.

168
00:08:02,050 --> 00:08:02,940
Dan kemudian kita gelung.

169
00:08:02,940 --> 00:08:06,790
Selagi n lebih besar daripada 0, kita
menyimpan mendarabkan produk dengan n

170
00:08:06,790 --> 00:08:09,890
dan decrementing n sehingga
kita mengira produk.

171
00:08:09,890 --> 00:08:14,600
Jadi kedua-dua fungsi, sekali lagi,
melakukan perkara yang sama.

172
00:08:14,600 --> 00:08:19,980
Tetapi mereka tidak melakukannya dalam
betul-betul cara sama.

173
00:08:19,980 --> 00:08:22,430
>> Kini, ia adalah mungkin untuk
mempunyai lebih daripada satu asas

174
00:08:22,430 --> 00:08:25,770
kes atau lebih daripada satu
kes rekursi, bergantung

175
00:08:25,770 --> 00:08:27,670
kepada apa fungsi anda cuba lakukan.

176
00:08:27,670 --> 00:08:31,650
Anda tidak semestinya hanya terhad kepada
kes asas tunggal atau rekursi tunggal

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

178
00:08:32,370 --> 00:08:35,320
Jadi contoh sesuatu
dengan kes-kes asas pelbagai

179
00:08:35,320 --> 00:08:37,830
mungkin this-- yang
Fibonacci urutan nombor.

180
00:08:37,830 --> 00:08:41,549
>> Anda mungkin ingat dari
hari sekolah rendah

181
00:08:41,549 --> 00:08:45,740
urutan Fibonacci ditakrifkan
seperti this-- elemen pertama adalah 0.

182
00:08:45,740 --> 00:08:46,890
Elemen kedua ialah 1.

183
00:08:46,890 --> 00:08:49,230
Kedua-dua mereka adalah hanya dengan definisi.

184
00:08:49,230 --> 00:08:55,920
>> Maka setiap elemen lain ditakrifkan
sebagai jumlah n tolak 1 dan n tolak 2.

185
00:08:55,920 --> 00:09:00,330
Jadi elemen yang ketiga
akan menjadi 0 tambah 1 adalah 1.

186
00:09:00,330 --> 00:09:03,280
Dan kemudian elemen keempat
akan menjadi elemen kedua, 1,

187
00:09:03,280 --> 00:09:06,550
ditambah elemen yang ketiga, 1.

188
00:09:06,550 --> 00:09:08,507
Dan yang akan menjadi 2.

189
00:09:08,507 --> 00:09:09,340
Dan sebagainya dan sebagainya.

190
00:09:09,340 --> 00:09:11,680
>> Jadi dalam kes ini, kami mempunyai dua kes asas.

191
00:09:11,680 --> 00:09:14,850
Jika n adalah sama dengan 1, kembali 0.

192
00:09:14,850 --> 00:09:18,560
Jika n adalah sama dengan 2, kembali 1.

193
00:09:18,560 --> 00:09:25,930
Jika tidak, kembali Fibonacci n
tolak 1 tambah Fibonacci n tolak 2.

194
00:09:25,930 --> 00:09:27,180
>> Jadi itulah kes pangkalan berbilang.

195
00:09:27,180 --> 00:09:29,271
Bagaimana pula dengan pelbagai kes rekursi?

196
00:09:29,271 --> 00:09:31,520
Well, ada sesuatu
dipanggil dugaan Collatz itu.

197
00:09:31,520 --> 00:09:34,630
Saya tidak akan berkata,
anda tahu apa itu,

198
00:09:34,630 --> 00:09:38,170
kerana ia sebenarnya akhir kami
masalah untuk video ini tertentu.

199
00:09:38,170 --> 00:09:43,220
Dan ia adalah senaman kami
untuk bekerja bersama-sama.

200
00:09:43,220 --> 00:09:46,760
>> Jadi di sini adalah apa yang
Collatz tekaan is--

201
00:09:46,760 --> 00:09:48,820
ia terpakai kepada setiap integer positif.

202
00:09:48,820 --> 00:09:51,500
Dan ia membuat spekulasi bahawa itu
selalu mungkin untuk kembali

203
00:09:51,500 --> 00:09:55,060
1 jika anda mengikuti langkah-langkah ini.

204
00:09:55,060 --> 00:09:57,560
Jika n adalah 1, berhenti.

205
00:09:57,560 --> 00:10:00,070
Kami telah mendapat kembali ke 1 jika n 1.

206
00:10:00,070 --> 00:10:05,670
>> Jika tidak, melalui ini
proses sekali lagi pada n dibahagikan dengan 2.

207
00:10:05,670 --> 00:10:08,200
Dan lihat jika anda boleh kembali kepada 1.

208
00:10:08,200 --> 00:10:13,260
Jika tidak, jika n ganjil, melalui
proses ini sekali lagi pada 3n campur 1,

209
00:10:13,260 --> 00:10:15,552
atau 3 kali n campur 1.

210
00:10:15,552 --> 00:10:17,010
Jadi di sini kita mempunyai kes asas tunggal.

211
00:10:17,010 --> 00:10:18,430
Jika n adalah sama dengan 1, berhenti.

212
00:10:18,430 --> 00:10:20,230
Kami tidak melakukan apa-apa rekursi lagi.

213
00:10:20,230 --> 00:10:23,730
>> Tetapi kita mempunyai dua kes rekursi.

214
00:10:23,730 --> 00:10:28,750
Jika n adalah lebih, kita melakukan satu rekursi
kes, laungan n dibahagikan dengan 2.

215
00:10:28,750 --> 00:10:33,950
Jika n ganjil, yang kita lakukan yang berbeza
kes rekursi 3 kali n campur 1.

216
00:10:33,950 --> 00:10:39,120
>> Dan supaya matlamat untuk video ini adalah
untuk mengambil kedua, jeda video,

217
00:10:39,120 --> 00:10:42,440
dan cuba menulis ini
fungsi rekursi Collatz

218
00:10:42,440 --> 00:10:47,640
di mana anda lulus dalam nilai n, dan
ia mengira berapa banyak langkah-langkah yang

219
00:10:47,640 --> 00:10:52,430
mengambil masa untuk sampai ke 1 jika anda bermula dari n
dan anda mengikuti langkah-langkah ke atas.

220
00:10:52,430 --> 00:10:56,660
Jika n adalah 1, ia mengambil masa 0 langkah.

221
00:10:56,660 --> 00:11:00,190
Jika tidak, ia akan
mengambil satu langkah plus bagaimanapun

222
00:11:00,190 --> 00:11:06,200
banyak langkah-langkah yang diperlukan sama ada di n
dibahagikan dengan 2 jika n walaupun, atau 3n campur 1

223
00:11:06,200 --> 00:11:08,100
jika n ganjil.

224
00:11:08,100 --> 00:11:11,190
>> Sekarang, saya telah meletakkan pada skrin di sini
beberapa perkara ujian untuk anda,

225
00:11:11,190 --> 00:11:15,690
beberapa ujian kes untuk anda, untuk melihat
apa ini pelbagai nombor Collatz berada,

226
00:11:15,690 --> 00:11:17,440
dan juga ilustrasi
daripada langkah-langkah yang

227
00:11:17,440 --> 00:11:20,390
perlu melalui supaya anda boleh
semacam melihat proses ini dalam tindakan.

228
00:11:20,390 --> 00:11:24,222
Jadi, jika n adalah sama dengan
1, Collatz n adalah 0.

229
00:11:24,222 --> 00:11:26,180
Anda tidak perlu berbuat
apa sahaja untuk mendapatkan kembali ke 1.

230
00:11:26,180 --> 00:11:27,600
Anda sudah ada.

231
00:11:27,600 --> 00:11:30,550
>> Jika n adalah 2, ia mengambil masa
satu langkah untuk sampai ke 1.

232
00:11:30,550 --> 00:11:31,810
Anda bermula dengan 2.

233
00:11:31,810 --> 00:11:33,100
Nah, 2 tidak sama dengan 1.

234
00:11:33,100 --> 00:11:36,580
Oleh itu, ia akan menjadi satu langkah
plus bagaimanapun banyak langkah-langkah yang

235
00:11:36,580 --> 00:11:38,015
mengambil n dibahagikan dengan 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 dibahagikan dengan 2 adalah 1.

238
00:11:42,910 --> 00:11:47,200
Jadi ia mengambil satu langkah plus bagaimanapun
banyak langkah-langkah yang diambil untuk 1.

239
00:11:47,200 --> 00:11:49,720
1 mengambil langkah sifar.

240
00:11:49,720 --> 00:11:52,370
>> Untuk 3, seperti yang anda lihat, ada
agak beberapa langkah yang terlibat.

241
00:11:52,370 --> 00:11:53,590
Anda pergi dari 3.

242
00:11:53,590 --> 00:11:56,710
Dan kemudian anda pergi ke
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Ia mengambil masa tujuh langkah untuk kembali kepada 1.

244
00:11:58,804 --> 00:12:01,220
Dan seperti yang anda boleh lihat, terdapat
beberapa kes-kes ujian lain di sini

245
00:12:01,220 --> 00:12:02,470
untuk menguji program anda.

246
00:12:02,470 --> 00:12:03,970
Jadi sekali lagi, jeda video.

247
00:12:03,970 --> 00:12:09,210
Dan saya akan pergi melompat kembali sekarang untuk
apa proses sebenar di sini,

248
00:12:09,210 --> 00:12:11,390
apa andaian ini boleh.

249
00:12:11,390 --> 00:12:14,140
>> Lihat jika anda boleh memikirkan
bagaimana untuk menentukan Collatz n

250
00:12:14,140 --> 00:12:19,967
supaya ia mengira berapa banyak
beberapa langkah yang diperlukan untuk mendapatkan ke 1.

251
00:12:19,967 --> 00:12:23,050
Jadi mudah-mudahan, anda telah dihentikan sementara video
dan anda tidak hanya menunggu saya

252
00:12:23,050 --> 00:12:25,820
memberikan jawapan di sini.

253
00:12:25,820 --> 00:12:29,120
Tetapi jika anda adalah, baik,
inilah jawapan pula.

254
00:12:29,120 --> 00:12:33,070
>> Jadi di sini adalah definisi mungkin
fungsi Collatz itu.

255
00:12:33,070 --> 00:12:35,610
Pangkalan kami case-- jika n
sama dengan 1, kita kembali 0.

256
00:12:35,610 --> 00:12:38,250
Ia tidak mengambil apa-apa
langkah-langkah untuk kembali kepada 1.

257
00:12:38,250 --> 00:12:42,710
>> Jika tidak, kita mempunyai dua cases-- rekursi
satu untuk nombor genap dan satu untuk ganjil.

258
00:12:42,710 --> 00:12:47,164
Cara yang saya menguji nombor genap
adalah untuk memeriksa jika n mod 2 sama dengan 0.

259
00:12:47,164 --> 00:12:49,080
Ini adalah pada dasarnya, sekali lagi,
bertanya soalan,

260
00:12:49,080 --> 00:12:54,050
jika anda masih ingat apa mod is-- jika saya
jurang n dengan 2 adalah tidak ada baki?

261
00:12:54,050 --> 00:12:55,470
Yang akan menjadi nombor genap.

262
00:12:55,470 --> 00:13:01,370
>> Dan jadi jika n mod 2 sama dengan 0 adalah
ujian ini satu nombor genap.

263
00:13:01,370 --> 00:13:04,250
Jika ya, saya mahu kembali 1,
kerana ini adalah pasti

264
00:13:04,250 --> 00:13:09,270
mengambil satu langkah plus Collatz daripada
apa nombor adalah separuh daripada saya.

265
00:13:09,270 --> 00:13:13,910
Jika tidak, saya mahu kembali 1
ditambah Collatz 3 kali n campur 1.

266
00:13:13,910 --> 00:13:16,060
Itulah yang lain
langkah rekursi yang kita

267
00:13:16,060 --> 00:13:19,470
boleh mengambil untuk mengira
Collatz-- bilangan langkah

268
00:13:19,470 --> 00:13:22,610
ia mengambil masa untuk kembali
1 diberi nombor.

269
00:13:22,610 --> 00:13:24,610
Jadi diharapkan, contoh ini
memberikan anda sedikit

270
00:13:24,610 --> 00:13:26,620
satu rasa yang prosedur rekursi.

271
00:13:26,620 --> 00:13:30,220
Mudah-mudahan, anda berfikir kod adalah
sedikit lebih cantik jika dilaksanakan

272
00:13:30,220 --> 00:13:32,760
dengan cara yang elegan, rekursi.

273
00:13:32,760 --> 00:13:35,955
Tetapi, jika tidak, rekursi adalah
alat yang benar-benar kuat tetap.

274
00:13:35,955 --> 00:13:38,330
Dan maka ia pasti sesuatu
untuk mendapatkan kepala anda sekitar,

275
00:13:38,330 --> 00:13:41,360
kerana anda akan dapat mewujudkan
program cukup sejuk menggunakan rekursi

276
00:13:41,360 --> 00:13:45,930
yang sebaliknya mungkin menjadi rumit untuk menulis
jika anda menggunakan gelung dan lelaran.

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

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

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