>> ZAMYLA: Dalam rangka untuk memahami rekursi, Anda harus
pertama memahami rekursi.
Memiliki rekursi dalam program desain berarti bahwa Anda memiliki self-referensial
definisi.
Struktur data rekursif, misalnya, adalah struktur data yang
termasuk diri definisi mereka.
Tapi hari ini, kita akan fokus pada fungsi rekursif.
>> Ingat bahwa fungsi mengambil input, argumen, dan mengembalikan nilai sebagai mereka
Output diwakili oleh diagram ini di sini.
Kami akan memikirkan kotak sebagai tubuh fungsi, yang berisi set
instruksi yang menafsirkan input dan memberikan output.
Mengambil melihat lebih dekat di dalam tubuh fungsi bisa mengungkapkan panggilan ke
fungsi lain juga.
Ambil fungsi ini sederhana, foo, bahwa mengambil string tunggal sebagai masukan dan
cetakan berapa banyak surat string yang memiliki.
Fungsi strlen, untuk panjang string, disebut, yang output
diperlukan untuk panggilan ke printf.
>> Sekarang, apa yang membuat fungsi rekursif istimewa adalah bahwa ia menyebut dirinya.
Kita bisa mewakili rekursif ini menyebutnya dengan jeruk ini panah
looping kembali ke dirinya sendiri.
Tapi mengeksekusi sendiri lagi hanya akan membuat panggilan rekursif lain, dan
dan lain lain.
Tapi fungsi rekursif tidak dapat tak terbatas.
Mereka harus berakhir entah bagaimana, atau Anda Program akan berjalan selamanya.
>> Jadi kita perlu menemukan cara untuk memecahkan dari panggilan rekursif.
Kami menyebutnya kasus dasar.
Ketika kondisi dasar terpenuhi, kembali fungsi tanpa membuat
rekursif lain.
Ambil fungsi ini, hai, fungsi void yang mengambil int n sebagai masukan.
Kasus dasar datang pertama.
Jika n adalah kurang dari nol, bye cetak dan kembali Untuk semua kasus lain,
fungsi akan mencetak hi dan mengeksekusi panggilan rekursif.
Panggilan lain untuk fungsi hi dengan nilai masukan dikurangi.
>> Sekarang, meskipun kami mencetak hi, yang Fungsi tidak akan mengakhiri sampai kita
kembali tipe kembali nya, dalam hal ini tidak berlaku.
Jadi untuk setiap n selain kasus dasar, fungsi hi hi ini akan kembali
dari n dikurangi 1.
Karena fungsi ini tidak berlaku meskipun, kita tidak akan secara eksplisit ketik kembali di sini.
Kami hanya akan menjalankan fungsi.
Jadi memanggil hi (3) akan mencetak hi dan mengeksekusi hi (2) yang mengeksekusi hi (1) satu
yang mengeksekusi hi (0), dimana kondisi dasar terpenuhi.
Jadi hi (0) mencetak bye dan kembali.
>> OK.
Jadi sekarang kita memahami dasar-dasar dari fungsi rekursif, bahwa mereka perlu
setidaknya satu kasus dasar serta panggilan rekursif, mari kita lanjutkan ke
contoh yang lebih bermakna.
Salah satu yang tidak hanya kembali membatalkan apa pun.
>> Mari kita lihat faktorial yang operasi yang digunakan paling umum dalam
perhitungan probabilitas.
Faktorial n adalah produk dari setiap bilangan bulat positif kurang dari
dan sama dengan n.
Jadi lima faktorial adalah 5 kali 4 kali 3 kali 2 kali 1 untuk memberikan 120.
Empat faktorial adalah 4 kali 3 kali 2 kali 1 untuk memberikan 24.
Dan aturan yang sama berlaku untuk setiap bilangan bulat positif.
>> Jadi bagaimana mungkin kita menulis sebuah rekursif fungsi yang menghitung faktorial tersebut
dari nomor?
Nah, kita harus mengidentifikasi baik kasus dasar dan panggilan rekursif.
Panggilan rekursif akan sama untuk semua kasus kecuali untuk dasar
kasus, yang berarti bahwa kita harus menemukan pola yang akan memberi kita kami
hasil yang diinginkan.
>> Untuk contoh ini, melihat bagaimana 5 faktorial melibatkan mengalikan 4 dengan 3 dengan 2 1
Dan bahwa perkalian yang sama ditemukan di sini,
definisi 4 faktorial.
Jadi kita melihat bahwa 5 faktorial adalah hanya 5 kali 4 faktorial.
Sekarang apakah pola ini berlaku 4 faktorial juga?
Ya.
Kita melihat bahwa 4 faktorial berisi perkalian 3 kali 2 kali 1,
definisi yang sangat sama dengan 3 faktorial.
Jadi 4 faktorial sama dengan 4 kali 3 faktorial, dan seterusnya dan sebagainya kami
Pola tongkat sampai 1 faktorial, yang menurut definisi adalah sama dengan 1.
>> Tidak ada positif lainnya bilangan bulat kiri.
Jadi kita memiliki pola untuk rekursif kami.
n faktorial adalah sama dengan n kali faktorial dari n dikurangi 1.
Dan kasus dasar kami?
Itu hanya akan menjadi definisi kita dari 1 faktorial.
>> Jadi sekarang kita bisa beralih ke menulis kode untuk fungsi.
Untuk kasus dasar, kita akan memiliki Kondisi n sama equals 1, di mana
kami akan mengembalikan 1.
Kemudian bergerak ke panggilan rekursif, kami akan kembali n kali
faktorial n dikurangi 1.
>> Sekarang mari kita coba kami ini.
Mari kita coba faktorial 4.
Per fungsi kita itu sama sampai 4 kali faktorial (3).
Faktorial (3) adalah sama dengan 3 kali faktorial (2).
Factorial (2) sama dengan 2 kali faktorial (1), yang mengembalikan 1.
Factorial (2) sekarang kembali 2 kali 1, 2.
Faktorial (3) sekarang dapat kembali 3 kali 2, 6.
Dan akhirnya, faktorial (4) kembali 4 kali 6, 24.
>> Jika Anda hadapi kesulitan dengan panggilan rekursif, berpura-pura bahwa
fungsi bekerja sudah.
Apa yang saya maksudkan dengan ini adalah bahwa Anda harus percaya panggilan rekursif Anda untuk kembali
nilai-nilai yang tepat.
Sebagai contoh, jika saya tahu bahwa faktorial (5) sama dengan 5 kali
faktorial (4), aku akan percaya bahwa faktorial (4) akan memberi saya 24.
Anggap saja sebagai variabel, jika Anda akan, seolah-olah Anda sudah didefinisikan
faktorial (4).
Jadi untuk setiap faktorial (n), itu produk dari n dan
faktorial sebelumnya.
Dan faktorial ini sebelumnya diperoleh dengan menelepon
faktorial n dikurangi 1.
>> Sekarang, lihat apakah Anda dapat menerapkan recursive fungsi sendiri.
Mengisi terminal Anda, atau run.cs50.net, dan menulis fungsi sum
yang mengambil integer n dan mengembalikan jumlah semua positif berturut-turut
bilangan bulat dari n ke 1.
Saya telah menulis keluar jumlah dari beberapa nilai untuk membantu Anda kami.
Pertama, mengetahui kondisi dasar.
Kemudian, melihat jumlah (5).
Dapatkah Anda mengungkapkan hal itu dalam hal dari jumlah yang lain?
Sekarang, bagaimana dengan sum (4)?
Bagaimana Anda bisa mengekspresikan sum (4) dalam hal jumlah lain?
>> Setelah Anda memiliki sum (5) dan sum (4) dinyatakan dalam jumlah lain, lihat
jika Anda dapat mengidentifikasi pola untuk jumlah (n).
Jika tidak, coba nomor lain beberapa dan mengekspresikan jumlah mereka di
hal jumlah lain.
Dengan mengidentifikasi pola diskrit angka, Anda baik pada cara untuk
mengidentifikasi pola untuk setiap n.
>> Rekursi adalah alat yang benar-benar kuat, jadi tentu saja itu tidak terbatas pada
fungsi matematika.
Rekursi dapat digunakan dengan sangat efektif ketika berhadapan dengan pohon-pohon misalnya.
Check out pendek pada pohon untuk lebih tinjauan menyeluruh, tapi untuk saat ini
ingat bahwa pohon pencarian biner, di tertentu, yang terdiri dari node, masing-masing
dengan nilai dan dua pointer simpul.
Biasanya, ini diwakili oleh simpul orangtua memiliki satu baris menunjuk
ke node anak kiri dan satu ke node anak kanan.
Struktur pencarian biner Pohon cocok dengan baik
untuk pencarian rekursif.
Panggilan rekursif baik lewat di kiri atau node yang tepat, tetapi lebih
itu dalam jangka pendek pohon.
>> Katakanlah Anda ingin melakukan operasi pada setiap node dalam sebuah pohon biner.
Bagaimana Anda bisa pergi tentang itu?
Nah, Anda bisa menulis sebuah rekursif fungsi yang melakukan operasi
pada node induk dan membuat sebuah rekursif panggilan ke fungsi yang sama,
lewat di sebelah kiri dan node anak kanan.
Sebagai contoh, fungsi ini, foo, bahwa mengubah nilai dari node yang diberikan dan
semua anak-anak untuk 1.
Kasus dasar dari penyebab simpul nol fungsi untuk kembali, menunjukkan
bahwa tidak ada node kiri dalam sub-pohon.
>> Mari kita berjalan melewatinya.
Orang tua pertama adalah 13.
Kami mengubah nilai ke 1, dan kemudian memanggil Fungsi kami di sebelah kiri juga
sebagai hak.
Fungsi, foo, disebut di sebelah kiri sub-pohon pertama, sehingga node kiri
akan dipindahkan ke 1 dan foo akan disebut pada anak-anak bahwa node,
pertama kiri dan kemudian kanan, dan seterusnya dan sebagainya.
Dan memberitahu mereka bahwa cabang tidak memiliki anak-anak lagi sehingga proses yang sama
akan terus untuk anak-anak yang tepat sampai node seluruh pohon yang
dipindahkan ke 1.
>> Seperti yang Anda lihat, Anda tidak terbatas hanya satu panggilan rekursif.
Sama seperti banyak seperti yang akan mendapatkan pekerjaan yang dilakukan.
Bagaimana jika Anda memiliki pohon di mana masing-masing simpul memiliki tiga anak,
Kiri, tengah, dan kanan?
Bagaimana Anda akan mengedit foo?
Nah, sederhana.
Cukup tambahkan panggilan rekursif lain dan lulus dalam node tengah pointer.
>> Rekursi sangat kuat dan tidak menyebutkan elegan, tetapi bisa menjadi
konsep yang sulit pada awalnya, jadi pasien dan mengambil waktu Anda.
Mulailah dengan kasus dasar.
Ini biasanya yang paling mudah untuk mengidentifikasi, dan kemudian Anda dapat bekerja
mundur dari sana.
Anda tahu bahwa Anda perlu untuk mencapai Anda kasus dasar, sehingga kekuatan yang
memberikan beberapa petunjuk.
Cobalah untuk mengekspresikan satu kasus tertentu dalam hal kasus-kasus lain, atau dalam sub-set.
>> Terima kasih untuk menonton ini singkat.
Paling tidak, sekarang Anda bisa memahami lelucon seperti ini.
Nama saya adalah Zamyla, dan ini adalah CS50.
>> Ambil fungsi ini, hi, a void function yang mengambil
int, n, sebagai masukan.
Kasus dasar datang pertama.
Jika n adalah kurang dari 0, cetak "Bye" dan kembali.