1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Untuk memahami
rekursi, anda mesti

3
00:00:10,190 --> 00:00:13,820
memahami rekursi.

4
00:00:13,820 --> 00:00:17,280
Mempunyai rekursi dalam program reka bentuk cara
bahawa anda mempunyai diri rujukan-

5
00:00:17,280 --> 00:00:18,570
definisi.

6
00:00:18,570 --> 00:00:21,520
Struktur data rekursif, misalnya,
adalah struktur data yang

7
00:00:21,520 --> 00:00:23,990
termasuk diri mereka dalam
definisi mereka.

8
00:00:23,990 --> 00:00:27,160
Tetapi hari ini, kita akan memberi tumpuan
kepada fungsi rekursif.

9
00:00:27,160 --> 00:00:31,160
>> Ingat bahawa fungsi mengambil input,
hujah-hujah, dan mengembalikan nilai seperti mereka

10
00:00:31,160 --> 00:00:34,480
output diwakili oleh
gambar rajah ini di sini.

11
00:00:34,480 --> 00:00:38,060
Kami akan berfikir dari kotak sebagai badan
majlis itu, yang mengandungi set

12
00:00:38,060 --> 00:00:42,340
arahan yang mentafsirkan
input dan memberikan output.

13
00:00:42,340 --> 00:00:45,660
Mengambil melihat dengan lebih dekat di dalam badan
fungsi boleh mendedahkan panggilan ke

14
00:00:45,660 --> 00:00:47,430
fungsi lain juga.

15
00:00:47,430 --> 00:00:51,300
Ambil fungsi ini mudah, foo, yang
mengambil rentetan tunggal sebagai input dan

16
00:00:51,300 --> 00:00:54,630
cetakan bagaimana banyak surat
tali yang mempunyai.

17
00:00:54,630 --> 00:00:58,490
Fungsi strlen, untuk panjang tali,
dipanggil, yang keluaran adalah

18
00:00:58,490 --> 00:01:01,890
diperlukan untuk panggilan kepada printf.

19
00:01:01,890 --> 00:01:05,770
>> Sekarang, apa yang membuatkan fungsi rekursi
istimewa ialah ia panggilan sendiri.

20
00:01:05,770 --> 00:01:09,610
Kami boleh mewakili rekursi ini
panggilan dengan oren anak panah ini

21
00:01:09,610 --> 00:01:11,360
menggelung kembali kepada dirinya sendiri.

22
00:01:11,360 --> 00:01:15,630
Tetapi melaksanakan sendiri lagi hanya akan
membuat satu lagi panggilan rekursif, dan

23
00:01:15,630 --> 00:01:17,150
yang lain dan yang lain.

24
00:01:17,150 --> 00:01:19,100
Tetapi fungsi rekursi
tidak boleh tidak terbatas.

25
00:01:19,100 --> 00:01:23,490
Mereka perlu berakhir entah bagaimana, atau anda
program akan berjalan selama-lamanya.

26
00:01:23,490 --> 00:01:27,680
>> Oleh itu, kita perlu mencari jalan untuk memecahkan
daripada panggilan rekursif.

27
00:01:27,680 --> 00:01:29,900
Kami menyeru ini kes asas.

28
00:01:29,900 --> 00:01:33,570
Apabila keadaan kes asas dipenuhi,
fungsi mengembalikan tanpa membuat

29
00:01:33,570 --> 00:01:34,950
satu lagi panggilan rekursif.

30
00:01:34,950 --> 00:01:39,610
Ambil fungsi ini, hi, fungsi tidak sah
yang mengambil int n sebagai input.

31
00:01:39,610 --> 00:01:41,260
Kes asas diutamakan.

32
00:01:41,260 --> 00:01:46,220
Jika n adalah kurang daripada sifar, bye cetak dan
kembali Untuk semua kes lain,

33
00:01:46,220 --> 00:01:49,400
fungsi akan mencetak hi dan melaksanakan
panggilan rekursif.

34
00:01:49,400 --> 00:01:53,600
Satu lagi panggilan kepada fungsi hi dengan
nilai input decremented.

35
00:01:53,600 --> 00:01:56,790
>> Sekarang, walaupun kita mencetak hi, yang
fungsi tidak akan menamatkan sehingga kita

36
00:01:56,790 --> 00:02:00,370
kembali jenis pulangan,
dalam kes ini tidak sah.

37
00:02:00,370 --> 00:02:04,830
Jadi bagi setiap n selain daripada kes asas,
fungsi hi ini akan kembali hi

38
00:02:04,830 --> 00:02:06,890
n tolak 1.

39
00:02:06,890 --> 00:02:10,050
Kerana fungsi ini adalah tidak sah walaupun, kita
tidak akan jelas menaip kembali di sini.

40
00:02:10,050 --> 00:02:12,000
Kami hanya akan melaksanakan fungsi tersebut.

41
00:02:12,000 --> 00:02:16,960
Jadi memanggil hi (3) akan mencetak dan hi
melaksanakan hi (2) yang melaksanakan hi (1) satu

42
00:02:16,960 --> 00:02:20,560
yang melaksanakan hi (0), di mana
keadaan kes asas dipenuhi.

43
00:02:20,560 --> 00:02:24,100
Jadi hi (0) mencetak bye dan pulangan.

44
00:02:24,100 --> 00:02:24,990
>> OK.

45
00:02:24,990 --> 00:02:28,690
Jadi sekarang kita memahami asas-asas
fungsi rekursif, bahawa mereka perlu

46
00:02:28,690 --> 00:02:32,730
sekurang-kurangnya satu kes asas serta
panggilan rekursif, mari kita beralih kepada

47
00:02:32,730 --> 00:02:34,120
contoh lebih bermakna.

48
00:02:34,120 --> 00:02:37,830
Satu yang tidak hanya kembali
tidak sah tidak kira apa.

49
00:02:37,830 --> 00:02:41,340
>> Mari kita lihat faktoran
operasi yang paling biasa digunakan dalam

50
00:02:41,340 --> 00:02:43,660
pengiraan kebarangkalian.

51
00:02:43,660 --> 00:02:48,120
Faktorial n adalah hasil dari setiap
integer positif kurang daripada

52
00:02:48,120 --> 00:02:49,400
dan sama dengan n.

53
00:02:49,400 --> 00:02:56,731
Lima Jadi faktorial adalah 5 kali 4 kali
3 kali 2 kali 1 bagi memberikan 120.

54
00:02:56,731 --> 00:03:01,400
Empat faktorial adalah 4 kali 3 kali
2 kali 1 untuk memberi 24.

55
00:03:01,400 --> 00:03:04,910
Dan peraturan yang sama terpakai
kepada mana-mana integer positif.

56
00:03:04,910 --> 00:03:08,670
>> Jadi bagaimana kita boleh menulis rekursif yang
fungsi yang mengira faktorial yang

57
00:03:08,670 --> 00:03:09,960
sebilangan?

58
00:03:09,960 --> 00:03:14,700
Nah, kita perlu mengenal pasti kedua-dua
kes asas dan panggilan rekursif.

59
00:03:14,700 --> 00:03:18,250
Panggilan rekursif akan sama
untuk semua hal melainkan asas

60
00:03:18,250 --> 00:03:21,420
kes, yang bermakna bahawa kita akan perlu
mencari corak yang akan memberikan kita kita

61
00:03:21,420 --> 00:03:23,350
keputusan yang dikehendaki.

62
00:03:23,350 --> 00:03:30,270
>> Sebagai contoh ini, lihat bagaimana 5 faktorial
melibatkan mendarabkan 4 dengan 3 oleh 2 dengan 1

63
00:03:30,270 --> 00:03:33,010
Dan pendaraban yang sama
didapati di sini,

64
00:03:33,010 --> 00:03:35,430
definisi 4 faktor.

65
00:03:35,430 --> 00:03:39,810
Jadi kita lihat bahawa 5 faktorial
hanya 5 kali 4 faktor.

66
00:03:39,810 --> 00:03:43,360
Sekarang tidak corak ini memohon
4 faktorial juga?

67
00:03:43,360 --> 00:03:44,280
Ya.

68
00:03:44,280 --> 00:03:49,120
Kita lihat bahawa 4 faktorial mengandungi
pendaraban 3 kali 2 kali 1,

69
00:03:49,120 --> 00:03:51,590
definisi yang sama seperti 3 faktor.

70
00:03:51,590 --> 00:03:56,950
Jadi 4 faktorial adalah sama dengan 4 kali 3
faktorial, dan sebagainya dan sebagainya kami

71
00:03:56,950 --> 00:04:02,170
corak melekat sehingga 1 faktorial, yang
oleh definisi adalah sama dengan 1.

72
00:04:02,170 --> 00:04:04,950
>> Tidak ada positif lain
integer kiri.

73
00:04:04,950 --> 00:04:07,870
Jadi kita mempunyai corak untuk
panggilan rekursif kami.

74
00:04:07,870 --> 00:04:13,260
n faktorial adalah sama dengan n kali
faktorial n tolak 1.

75
00:04:13,260 --> 00:04:14,370
Dan kes asas kita?

76
00:04:14,370 --> 00:04:17,370
Itu hanya akan definisi kita
1 faktor.

77
00:04:17,370 --> 00:04:19,995
>> Jadi sekarang kita boleh bergerak ke bertulis
kod untuk majlis itu.

78
00:04:19,995 --> 00:04:24,110
Untuk kes asas, kita akan mempunyai
keadaan n sama setaraf 1, di mana

79
00:04:24,110 --> 00:04:25,780
kami akan kembali 1.

80
00:04:25,780 --> 00:04:29,280
Kemudian bergerak ke panggilan rekursif,
kami akan kembali n kali

81
00:04:29,280 --> 00:04:32,180
faktorial n tolak 1.

82
00:04:32,180 --> 00:04:33,590
>> Sekarang mari kita menguji kita ini.

83
00:04:33,590 --> 00:04:35,900
Mari kita cuba faktorial 4.

84
00:04:35,900 --> 00:04:39,420
Per fungsi kami itu sama
4 kali faktorial (3).

85
00:04:39,420 --> 00:04:43,040
Faktorial (3) adalah sama dengan
3 kali faktorial (2).

86
00:04:43,040 --> 00:04:48,700
Faktorial (2) adalah sama dengan 2 kali
faktorial (1), yang mengembalikan 1.

87
00:04:48,700 --> 00:04:52,490
Faktorial (2) kini kembali 2 kali 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktorial (3) kini boleh kembali
3 kali 2, 6.

89
00:04:55,960 --> 00:05:02,490
Dan akhirnya, faktorial (4)
kembali 4 kali 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Jika anda menghadapi apa-apa kesukaran
dengan seruan rekursif, berpura-pura bahawa

91
00:05:06,780 --> 00:05:09,660
fungsi kerja-kerja sudah.

92
00:05:09,660 --> 00:05:13,450
Apa yang saya maksudkan dengan ini adalah bahawa anda harus
mempercayai panggilan rekursif anda untuk kembali

93
00:05:13,450 --> 00:05:15,100
nilai-nilai yang betul.

94
00:05:15,100 --> 00:05:18,960
Sebagai contoh, jika saya tahu bahawa
faktorial (5) bersamaan 5 kali

95
00:05:18,960 --> 00:05:24,870
faktorial (4), saya akan percaya bahawa
faktorial (4) akan memberi saya 24.

96
00:05:24,870 --> 00:05:28,510
Anggapkannya sebagai satu pemboleh ubah, jika anda
akan, seperti jika anda sudah ditakrifkan

97
00:05:28,510 --> 00:05:30,070
faktorial (4).

98
00:05:30,070 --> 00:05:33,850
Jadi untuk apa-apa faktorial (n), ia adalah
produk n dan

99
00:05:33,850 --> 00:05:35,360
faktorial sebelumnya.

100
00:05:35,360 --> 00:05:38,130
Dan faktorial ini sebelumnya
diperolehi dengan menghubungi

101
00:05:38,130 --> 00:05:41,330
faktorial n tolak 1.

102
00:05:41,330 --> 00:05:45,130
>> Sekarang, lihat jika anda boleh melaksanakan
berfungsi diri rekursif.

103
00:05:45,130 --> 00:05:50,490
Muatkan terminal anda, atau run.cs50.net,
dan menulis sejumlah fungsi

104
00:05:50,490 --> 00:05:54,770
yang mengambil integer n dan mengembalikan
jumlah semua positif berturut-turut

105
00:05:54,770 --> 00:05:57,490
integer dari n kepada 1.

106
00:05:57,490 --> 00:06:01,000
Saya telah menulis daripada jumlah wang yang beberapa
Nilai untuk membantu anda kami.

107
00:06:01,000 --> 00:06:04,030
Pertama, memikirkan
keadaan kes asas.

108
00:06:04,030 --> 00:06:06,170
Kemudian, melihat jumlah (5).

109
00:06:06,170 --> 00:06:09,270
Bolehkah anda menyatakan ia dari segi
jumlah wang yang lain?

110
00:06:09,270 --> 00:06:11,290
Kini, apa kira-kira jumlah (4)?

111
00:06:11,290 --> 00:06:15,630
Bagaimana anda boleh meluahkan jumlah (4)
dari segi jumlah yang lain?

112
00:06:15,630 --> 00:06:19,655
>> Sebaik sahaja anda mempunyai jumlah (5) dan jumlah (4)
dinyatakan dari segi jumlah wang yang lain, lihat

113
00:06:19,655 --> 00:06:22,970
jika anda boleh mengenal pasti
corak untuk jumlah (n).

114
00:06:22,970 --> 00:06:26,190
Jika tidak, cuba beberapa nombor lain
dan menyatakan jumlah wang mereka dalam

115
00:06:26,190 --> 00:06:28,410
segi lain nombor.

116
00:06:28,410 --> 00:06:31,930
Dengan mengenal pasti corak untuk diskret
nombor, anda juga pada cara anda untuk

117
00:06:31,930 --> 00:06:34,320
mengenal pasti corak untuk mana-mana n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursi adalah alat yang benar-benar kuat,
jadi sudah tentu ia tidak terhad kepada

119
00:06:38,040 --> 00:06:39,820
fungsi matematik.

120
00:06:39,820 --> 00:06:44,040
Jadi semula boleh digunakan dengan amat berkesan
apabila berurusan dengan pokok-pokok misalnya.

121
00:06:44,040 --> 00:06:47,210
Semak pendek di atas pokok untuk
lebih kajian menyeluruh, tetapi untuk sekarang

122
00:06:47,210 --> 00:06:51,140
ingat bahawa pokok-pokok carian binari, dalam
tertentu, terdiri daripada nod, setiap

123
00:06:51,140 --> 00:06:53,820
dengan nilai dan dua petunjuk nod.

124
00:06:53,820 --> 00:06:57,270
Biasanya, ini diwakili oleh
nod ibu bapa mempunyai satu baris menunjuk

125
00:06:57,270 --> 00:07:01,870
kepada nod anak kiri dan satu
ke nod anak yang betul.

126
00:07:01,870 --> 00:07:04,510
Struktur carian binari
pokok meminjam dirinya dengan baik

127
00:07:04,510 --> 00:07:05,940
untuk carian rekursif.

128
00:07:05,940 --> 00:07:09,730
Panggilan rekursif sama ada pas dalam
kiri atau nod yang betul, tetapi lebih

129
00:07:09,730 --> 00:07:10,950
itu ringkasnya pokok.

130
00:07:10,950 --> 00:07:15,690
>> Katakanlah anda mahu untuk melakukan pembedahan ke atas
setiap nod tunggal dalam pokok binari.

131
00:07:15,690 --> 00:07:17,410
Bagaimana anda boleh pergi tentang itu?

132
00:07:17,410 --> 00:07:20,600
Nah, anda boleh menulis rekursif yang
fungsi yang melaksanakan operasi

133
00:07:20,600 --> 00:07:24,450
pada nod induk dan membuat rekursif yang
panggilan untuk majlis yang sama,

134
00:07:24,450 --> 00:07:27,630
lulus dalam kiri dan
nod anak betul.

135
00:07:27,630 --> 00:07:31,650
Sebagai contoh, fungsi ini, foo, yang
menukar nilai nod yang diberikan dan

136
00:07:31,650 --> 00:07:33,830
semua kanak-kanak untuk 1.

137
00:07:33,830 --> 00:07:37,400
Kes asas yang punca nod null
fungsi untuk kembali, menunjukkan

138
00:07:37,400 --> 00:07:41,290
bahawa tidak ada apa-apa nod
kiri dalam yang sub-pokok.

139
00:07:41,290 --> 00:07:42,620
>> Mari kita berjalan melaluinya.

140
00:07:42,620 --> 00:07:44,340
Ibu bapa pertama adalah 13.

141
00:07:44,340 --> 00:07:47,930
Kami menukar nilai kepada 1, dan kemudian memanggil
fungsi kami di sebelah kiri dan juga

142
00:07:47,930 --> 00:07:49,600
sebagai betul.

143
00:07:49,600 --> 00:07:53,910
Fungsi, foo, dipanggil di sebelah kiri
sub-pokok pertama, jadi nod kiri

144
00:07:53,910 --> 00:07:57,730
akan ditukarkan ke 1 dan foo akan
dipanggil pada kanak-kanak yang nod ini,

145
00:07:57,730 --> 00:08:01,900
yang pertama di sebelah kiri dan kemudian yang betul,
dan sebagainya dan sebagainya.

146
00:08:01,900 --> 00:08:05,630
Dan memberitahu mereka bahawa cawangan tidak mempunyai
lagi anak-anak supaya proses yang sama

147
00:08:05,630 --> 00:08:09,700
akan terus untuk kanak-kanak yang betul
sehingga nod keseluruhan pokok adalah

148
00:08:09,700 --> 00:08:11,430
ditukarkan ke 1.

149
00:08:11,430 --> 00:08:15,390
>> Seperti yang anda lihat, anda tidak terhad
dengan hanya satu panggilan rekursif.

150
00:08:15,390 --> 00:08:17,930
Sama seperti ramai seperti yang akan mendapatkan pekerjaan yang dilakukan.

151
00:08:17,930 --> 00:08:21,200
Bagaimana jika anda mempunyai pokok di mana setiap
nod mempunyai tiga orang anak,

152
00:08:21,200 --> 00:08:23,100
Kiri, tengah, dan kanan?

153
00:08:23,100 --> 00:08:24,886
Bagaimana anda mengedit foo?

154
00:08:24,886 --> 00:08:25,860
Nah, mudah.

155
00:08:25,860 --> 00:08:30,250
Hanya menambah satu lagi panggilan rekursif dan
lulus dalam penunjuk nod tengah.

156
00:08:30,250 --> 00:08:34,549
>> Jadi semula adalah sangat kuat dan tidak
lagi elegan, tetapi ia boleh menjadi satu

157
00:08:34,549 --> 00:08:38,010
konsep yang sukar pada mulanya, jadi
pesakit dan mengambil masa anda.

158
00:08:38,010 --> 00:08:39,370
Bermula dengan kes asas.

159
00:08:39,370 --> 00:08:42,650
Ia biasanya yang paling mudah untuk mengenal pasti,
dan kemudian anda boleh bekerja

160
00:08:42,650 --> 00:08:43,830
ke belakang dari sana.

161
00:08:43,830 --> 00:08:46,190
Anda tahu anda perlukan untuk mencapai anda
kes asas, jadi kekuatan yang

162
00:08:46,190 --> 00:08:47,760
memberi anda beberapa petunjuk.

163
00:08:47,760 --> 00:08:53,120
Cuba untuk menyatakan satu kes tertentu dalam
segi kes-kes lain, atau sub-set.

164
00:08:53,120 --> 00:08:54,700
>> Terima kasih kerana menonton ini pendek.

165
00:08:54,700 --> 00:08:58,920
Sekurang-kurangnya, sekarang anda boleh
memahami jenaka seperti ini.

166
00:08:58,920 --> 00:09:01,250
Nama saya Zamyla, dan ini adalah cs50.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> Ambil fungsi ini, hi, a
fungsi tidak sah yang mengambil

169
00:09:07,170 --> 00:09:09,212
int satu, n, sebagai input.

170
00:09:09,212 --> 00:09:11,020
Kes asas diutamakan.

171
00:09:11,020 --> 00:09:14,240
Jika n adalah kurang daripada 0, cetak
"Bye" dan kembali.

172
00:09:14,240 --> 00:09:15,490