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.