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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Dalam rangka untuk memahami
rekursi, Anda harus

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

4
00:00:13,820 --> 00:00:17,280
Memiliki rekursi dalam program desain berarti
bahwa Anda memiliki self-referensial

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
definisi mereka.

8
00:00:23,990 --> 00:00:27,160
Tapi hari ini, kita akan fokus
pada fungsi rekursif.

9
00:00:27,160 --> 00:00:31,160
>> Ingat bahwa fungsi mengambil input,
argumen, dan mengembalikan nilai sebagai mereka

10
00:00:31,160 --> 00:00:34,480
Output diwakili oleh
diagram ini di sini.

11
00:00:34,480 --> 00:00:38,060
Kami akan memikirkan kotak sebagai tubuh
fungsi, yang berisi set

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

13
00:00:42,340 --> 00:00:45,660
Mengambil melihat lebih dekat di dalam tubuh
fungsi bisa mengungkapkan 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 sederhana, foo, bahwa
mengambil string tunggal sebagai masukan dan

16
00:00:51,300 --> 00:00:54,630
cetakan berapa banyak surat
string yang memiliki.

17
00:00:54,630 --> 00:00:58,490
Fungsi strlen, untuk panjang string,
disebut, yang output

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

19
00:01:01,890 --> 00:01:05,770
>> Sekarang, apa yang membuat fungsi rekursif
istimewa adalah bahwa ia menyebut dirinya.

20
00:01:05,770 --> 00:01:09,610
Kita bisa mewakili rekursif ini
menyebutnya dengan jeruk ini panah

21
00:01:09,610 --> 00:01:11,360
looping kembali ke dirinya sendiri.

22
00:01:11,360 --> 00:01:15,630
Tapi mengeksekusi sendiri lagi hanya akan
membuat panggilan rekursif lain, dan

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

24
00:01:17,150 --> 00:01:19,100
Tapi fungsi rekursif
tidak dapat tak terbatas.

25
00:01:19,100 --> 00:01:23,490
Mereka harus berakhir entah bagaimana, atau Anda
Program akan berjalan selamanya.

26
00:01:23,490 --> 00:01:27,680
>> Jadi kita perlu menemukan cara untuk memecahkan
dari panggilan rekursif.

27
00:01:27,680 --> 00:01:29,900
Kami menyebutnya kasus dasar.

28
00:01:29,900 --> 00:01:33,570
Ketika kondisi dasar terpenuhi,
kembali fungsi tanpa membuat

29
00:01:33,570 --> 00:01:34,950
rekursif lain.

30
00:01:34,950 --> 00:01:39,610
Ambil fungsi ini, hai, fungsi void
yang mengambil int n sebagai masukan.

31
00:01:39,610 --> 00:01:41,260
Kasus dasar datang pertama.

32
00:01:41,260 --> 00:01:46,220
Jika n adalah kurang dari nol, bye cetak dan
kembali Untuk semua kasus lain,

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

34
00:01:49,400 --> 00:01:53,600
Panggilan lain untuk fungsi hi dengan
nilai masukan dikurangi.

35
00:01:53,600 --> 00:01:56,790
>> Sekarang, meskipun kami mencetak hi, yang
Fungsi tidak akan mengakhiri sampai kita

36
00:01:56,790 --> 00:02:00,370
kembali tipe kembali nya,
dalam hal ini tidak berlaku.

37
00:02:00,370 --> 00:02:04,830
Jadi untuk setiap n selain kasus dasar,
fungsi hi hi ini akan kembali

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

39
00:02:06,890 --> 00:02:10,050
Karena fungsi ini tidak berlaku meskipun, kita
tidak akan secara eksplisit ketik kembali di sini.

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

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

42
00:02:16,960 --> 00:02:20,560
yang mengeksekusi hi (0), dimana
kondisi dasar terpenuhi.

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

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

45
00:02:24,990 --> 00:02:28,690
Jadi sekarang kita memahami dasar-dasar dari
fungsi rekursif, bahwa mereka perlu

46
00:02:28,690 --> 00:02:32,730
setidaknya satu kasus dasar serta
panggilan rekursif, mari kita lanjutkan ke

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

48
00:02:34,120 --> 00:02:37,830
Salah satu yang tidak hanya kembali
membatalkan apa pun.

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

50
00:02:41,340 --> 00:02:43,660
perhitungan probabilitas.

51
00:02:43,660 --> 00:02:48,120
Faktorial n adalah produk dari setiap
bilangan bulat positif kurang dari

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

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

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

55
00:03:01,400 --> 00:03:04,910
Dan aturan yang sama berlaku
untuk setiap bilangan bulat positif.

56
00:03:04,910 --> 00:03:08,670
>> Jadi bagaimana mungkin kita menulis sebuah rekursif
fungsi yang menghitung faktorial tersebut

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

58
00:03:09,960 --> 00:03:14,700
Nah, kita harus mengidentifikasi baik
kasus dasar dan panggilan rekursif.

59
00:03:14,700 --> 00:03:18,250
Panggilan rekursif akan sama
untuk semua kasus kecuali untuk dasar

60
00:03:18,250 --> 00:03:21,420
kasus, yang berarti bahwa kita harus
menemukan pola yang akan memberi kita kami

61
00:03:21,420 --> 00:03:23,350
hasil yang diinginkan.

62
00:03:23,350 --> 00:03:30,270
>> Untuk contoh ini, melihat bagaimana 5 faktorial
melibatkan mengalikan 4 dengan 3 dengan 2 1

63
00:03:30,270 --> 00:03:33,010
Dan bahwa perkalian yang sama
ditemukan di sini,

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

65
00:03:35,430 --> 00:03:39,810
Jadi kita melihat bahwa 5 faktorial adalah
hanya 5 kali 4 faktorial.

66
00:03:39,810 --> 00:03:43,360
Sekarang apakah pola ini berlaku
4 faktorial juga?

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

68
00:03:44,280 --> 00:03:49,120
Kita melihat bahwa 4 faktorial berisi
perkalian 3 kali 2 kali 1,

69
00:03:49,120 --> 00:03:51,590
definisi yang sangat sama dengan 3 faktorial.

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

71
00:03:56,950 --> 00:04:02,170
Pola tongkat sampai 1 faktorial, yang
menurut definisi adalah sama dengan 1.

72
00:04:02,170 --> 00:04:04,950
>> Tidak ada positif lainnya
bilangan bulat kiri.

73
00:04:04,950 --> 00:04:07,870
Jadi kita memiliki pola untuk
rekursif kami.

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

75
00:04:13,260 --> 00:04:14,370
Dan kasus dasar kami?

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

77
00:04:17,370 --> 00:04:19,995
>> Jadi sekarang kita bisa beralih ke menulis
kode untuk fungsi.

78
00:04:19,995 --> 00:04:24,110
Untuk kasus dasar, kita akan memiliki
Kondisi n sama equals 1, di mana

79
00:04:24,110 --> 00:04:25,780
kami akan mengembalikan 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 dikurangi 1.

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

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

84
00:04:35,900 --> 00:04:39,420
Per fungsi kita itu sama
sampai 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
Factorial (2) sama dengan 2 kali
faktorial (1), yang mengembalikan 1.

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

88
00:04:52,490 --> 00:04:55,960
Faktorial (3) sekarang dapat 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 hadapi kesulitan
dengan panggilan rekursif, berpura-pura bahwa

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

92
00:05:09,660 --> 00:05:13,450
Apa yang saya maksudkan dengan ini adalah bahwa Anda harus
percaya panggilan rekursif Anda untuk kembali

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

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

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

96
00:05:24,870 --> 00:05:28,510
Anggap saja sebagai variabel, jika Anda
akan, seolah-olah Anda sudah didefinisikan

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

98
00:05:30,070 --> 00:05:33,850
Jadi untuk setiap faktorial (n), itu
produk dari 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
diperoleh dengan menelepon

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

102
00:05:41,330 --> 00:05:45,130
>> Sekarang, lihat apakah Anda dapat menerapkan
recursive fungsi sendiri.

103
00:05:45,130 --> 00:05:50,490
Mengisi terminal Anda, atau run.cs50.net,
dan menulis fungsi sum

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
bilangan bulat dari n ke 1.

106
00:05:57,490 --> 00:06:01,000
Saya telah menulis keluar jumlah dari beberapa
nilai untuk membantu Anda kami.

107
00:06:01,000 --> 00:06:04,030
Pertama, mengetahui
kondisi dasar.

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

109
00:06:06,170 --> 00:06:09,270
Dapatkah Anda mengungkapkan hal itu dalam hal
dari jumlah yang lain?

110
00:06:09,270 --> 00:06:11,290
Sekarang, bagaimana dengan sum (4)?

111
00:06:11,290 --> 00:06:15,630
Bagaimana Anda bisa mengekspresikan sum (4)
dalam hal jumlah lain?

112
00:06:15,630 --> 00:06:19,655
>> Setelah Anda memiliki sum (5) dan sum (4)
dinyatakan dalam jumlah lain, lihat

113
00:06:19,655 --> 00:06:22,970
jika Anda dapat mengidentifikasi
pola untuk jumlah (n).

114
00:06:22,970 --> 00:06:26,190
Jika tidak, coba nomor lain beberapa
dan mengekspresikan jumlah mereka di

115
00:06:26,190 --> 00:06:28,410
hal jumlah lain.

116
00:06:28,410 --> 00:06:31,930
Dengan mengidentifikasi pola diskrit
angka, Anda baik pada cara untuk

117
00:06:31,930 --> 00:06:34,320
mengidentifikasi pola untuk setiap n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursi adalah alat yang benar-benar kuat,
jadi tentu saja itu tidak terbatas pada

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

120
00:06:39,820 --> 00:06:44,040
Rekursi dapat digunakan dengan sangat efektif
ketika berhadapan dengan pohon-pohon misalnya.

121
00:06:44,040 --> 00:06:47,210
Check out pendek pada pohon untuk
lebih tinjauan menyeluruh, tapi untuk saat ini

122
00:06:47,210 --> 00:06:51,140
ingat bahwa pohon pencarian biner, di
tertentu, yang terdiri dari node, masing-masing

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

124
00:06:53,820 --> 00:06:57,270
Biasanya, ini diwakili oleh
simpul orangtua memiliki satu baris menunjuk

125
00:06:57,270 --> 00:07:01,870
ke node anak kiri dan satu
ke node anak kanan.

126
00:07:01,870 --> 00:07:04,510
Struktur pencarian biner
Pohon cocok dengan baik

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

128
00:07:05,940 --> 00:07:09,730
Panggilan rekursif baik lewat di
kiri atau node yang tepat, tetapi lebih

129
00:07:09,730 --> 00:07:10,950
itu dalam jangka pendek pohon.

130
00:07:10,950 --> 00:07:15,690
>> Katakanlah Anda ingin melakukan operasi pada
setiap node dalam sebuah pohon biner.

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

132
00:07:17,410 --> 00:07:20,600
Nah, Anda bisa menulis sebuah rekursif
fungsi yang melakukan operasi

133
00:07:20,600 --> 00:07:24,450
pada node induk dan membuat sebuah rekursif
panggilan ke fungsi yang sama,

134
00:07:24,450 --> 00:07:27,630
lewat di sebelah kiri dan
node anak kanan.

135
00:07:27,630 --> 00:07:31,650
Sebagai contoh, fungsi ini, foo, bahwa
mengubah nilai dari node yang diberikan dan

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

137
00:07:33,830 --> 00:07:37,400
Kasus dasar dari penyebab simpul nol
fungsi untuk kembali, menunjukkan

138
00:07:37,400 --> 00:07:41,290
bahwa tidak ada node
kiri dalam sub-pohon.

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

140
00:07:42,620 --> 00:07:44,340
Orang tua pertama adalah 13.

141
00:07:44,340 --> 00:07:47,930
Kami mengubah nilai ke 1, dan kemudian memanggil
Fungsi kami di sebelah kiri juga

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

143
00:07:49,600 --> 00:07:53,910
Fungsi, foo, disebut di sebelah kiri
sub-pohon pertama, sehingga node kiri

144
00:07:53,910 --> 00:07:57,730
akan dipindahkan ke 1 dan foo akan
disebut pada anak-anak bahwa node,

145
00:07:57,730 --> 00:08:01,900
pertama kiri dan kemudian kanan,
dan seterusnya dan sebagainya.

146
00:08:01,900 --> 00:08:05,630
Dan memberitahu mereka bahwa cabang tidak memiliki
anak-anak lagi sehingga proses yang sama

147
00:08:05,630 --> 00:08:09,700
akan terus untuk anak-anak yang tepat
sampai node seluruh pohon yang

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

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

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

151
00:08:17,930 --> 00:08:21,200
Bagaimana jika Anda memiliki pohon di mana masing-masing
simpul memiliki tiga 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 akan mengedit foo?

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

155
00:08:25,860 --> 00:08:30,250
Cukup tambahkan panggilan rekursif lain dan
lulus dalam node tengah pointer.

156
00:08:30,250 --> 00:08:34,549
>> Rekursi sangat kuat dan tidak
menyebutkan elegan, tetapi bisa menjadi

157
00:08:34,549 --> 00:08:38,010
konsep yang sulit pada awalnya, jadi
pasien dan mengambil waktu Anda.

158
00:08:38,010 --> 00:08:39,370
Mulailah dengan kasus dasar.

159
00:08:39,370 --> 00:08:42,650
Ini biasanya yang paling mudah untuk mengidentifikasi,
dan kemudian Anda dapat bekerja

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

161
00:08:43,830 --> 00:08:46,190
Anda tahu bahwa Anda perlu untuk mencapai Anda
kasus dasar, sehingga kekuatan yang

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

163
00:08:47,760 --> 00:08:53,120
Cobalah untuk mengekspresikan satu kasus tertentu dalam
hal kasus-kasus lain, atau dalam sub-set.

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

165
00:08:54,700 --> 00:08:58,920
Paling tidak, sekarang Anda bisa
memahami lelucon seperti ini.

166
00:08:58,920 --> 00:09:01,250
Nama saya adalah 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
void function yang mengambil

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

170
00:09:09,212 --> 00:09:11,020
Kasus dasar datang pertama.

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

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