[MUSIC PLAYING] 

Doug LLOYD: Anda mungkin berpikir bahwa Kode hanya digunakan untuk menyelesaikan tugas. Anda menulis itu. Itu melakukan sesuatu. Itu cukup banyak itu. 

Anda compile. Anda menjalankan program. Anda baik untuk pergi. 

Tapi percaya atau tidak, jika Anda kode untuk waktu yang lama, Anda benar-benar mungkin datang untuk melihat kode sebagai sesuatu yang indah. Ini memecahkan masalah di cara yang sangat menarik, atau ada sesuatu yang benar-benar rapi tentang cara terlihat. Anda mungkin akan tertawa pada saya, tapi itu benar. Dan rekursi adalah salah satu cara untuk semacam mendapatkan ide ini indah, elegan tampak kode. Ini memecahkan masalah dengan cara yang menarik, mudah untuk memvisualisasikan, dan sangat singkat. 

Karya-karya cara rekursi adalah, fungsi rekursif didefinisikan sebagai fungsi yang memanggil dirinya sebagai bagian dari pelaksanaannya. Yang mungkin tampak sedikit aneh, dan kita akan melihat sedikit tentang bagaimana ini bekerja dalam sekejap. Tapi sekali lagi, ini prosedur rekursif adalah akan menjadi begitu elegan karena mereka akan untuk memecahkan masalah ini tanpa memiliki semua fungsi lainnya atau ini loop panjang. Anda akan melihat bahwa ini rekursif prosedur akan terlihat begitu singkat. Dan mereka benar-benar akan membuat kode Anda terlihat jauh lebih indah. 

Saya akan memberikan contoh ini untuk melihat bagaimana prosedur rekursif dapat didefinisikan. Jadi jika Anda terbiasa dengan ini dari kelas matematika bertahun-tahun yang lalu, ada yang sesuatu yang disebut fungsi faktorial, yang biasanya dilambangkan sebagai tanda seru, yang didefinisikan atas semua bilangan bulat positif. Dan cara yang n faktorial dihitung adalah Anda kalikan semua angka kurang dari atau sama dengan n together-- semua bilangan bulat kurang dari atau sama dengan n bersama-sama. 

Jadi 5 faktorial adalah 5 kali 4 kali 3 kali 2 kali 1. Dan 4 faktorial adalah 4 kali 3 kali 2 kali 1 dan seterusnya. Anda mendapatkan ide. 

Sebagai programmer, kita tidak menggunakan n, tanda seru. Jadi kita akan menentukan faktorial berfungsi sebagai fakta n. Dan kita akan menggunakan faktorial untuk membuat solusi rekursif untuk masalah. Dan saya pikir Anda mungkin menemukan bahwa itu jauh lebih visual menarik daripada berulang versi ini, yang kami juga akan melihat pada suatu saat. 

Jadi di sini adalah beberapa pun facts-- intended-- tentang factorial-- yang fungsi faktorial. Faktorial dari 1, seperti yang saya katakan, adalah 1. Faktorial dari 2 adalah 2 kali 1. Faktorial dari 3 adalah 3 kali 2 kali 1, dan sebagainya. Kami berbicara tentang 4 dan 5 sudah. 

Tapi melihat ini, bukan ini benar? Bukankah faktorial dari 2 hanya 2 kali faktorial dari 1? Maksudku, faktorial dari 1 adalah 1. Jadi mengapa kita tidak bisa hanya mengatakan bahwa, sejak faktorial 2 adalah 2 kali 1, itu benar-benar hanya 2 kali faktorial dari 1? 

Dan kemudian memperluas gagasan itu, tidak faktorial dari 3 hanya 3 kali faktorial dari 2? Dan faktorial dari 4 adalah 4 kali faktorial dari 3, dan seterusnya? Bahkan, faktorial yang dari sejumlah bisa hanya dinyatakan jika kita jenis dari melakukan hal ini selamanya. Kita bisa semacam generalisasi masalah faktorial seperti itu n kali faktorial dari n minus 1. Ini n kali produk semua angka kurang dari saya. 

Ide ini, ini generalisasi dari masalah, memungkinkan kita untuk secara rekursif mendefinisikan fungsi faktorial. Ketika anda mendefinisikan suatu fungsi rekursif, ada dua hal yang perlu menjadi bagian dari itu. Anda harus memiliki sesuatu yang disebut kasus dasar, yang, ketika Anda memicu itu, akan menghentikan proses rekursif. 

Jika tidak, fungsi yang memanggil itself-- karena Anda mungkin imagine-- bisa berlangsung selamanya. Fungsi panggilan fungsi memanggil fungsi panggilan fungsi panggilan fungsi. Jika Anda tidak memiliki cara untuk menghentikannya, program Anda akan efektif terjebak di loop tak terbatas. Ini akan crash pada akhirnya, karena akan kehabisan memori. Tapi bukan itu intinya. 

Kita perlu memiliki beberapa cara lain untuk menghentikan hal selain menerjang program kami, karena program yang crash adalah mungkin tidak indah atau elegan. Dan jadi kita menyebutnya kasus dasar. Ini adalah solusi sederhana untuk masalah yang berhenti proses rekursif dari terjadi. Jadi itu salah satu bagian dari fungsi rekursif. 

Bagian kedua adalah kasus rekursif. Dan ini adalah di mana rekursi benar-benar akan terjadi. Di sinilah Fungsi akan memanggil dirinya sendiri. 

Ini tidak akan menyebut dirinya persis dengan cara yang sama itu disebut. Ini akan menjadi sedikit variasi yang membuat masalah itu mencoba untuk memecahkan mungil sedikit lebih kecil. Tetapi umumnya melewati buck memecahkan sebagian dari solusi untuk panggilan yang berbeda di telepon. 

Yang terlihat ini seperti kasus dasar di sini? Yang satu terlihat seperti ini Solusi paling sederhana untuk masalah? Kami memiliki banyak factorials, dan kami bisa terus akan on-- 6, 7, 8, 9, 10, dan seterusnya. 

Tapi salah satu penampilan ini seperti kasus yang baik untuk menjadi kasus dasar. Ini adalah solusi yang sangat sederhana. Kami tidak perlu melakukan sesuatu yang istimewa. 

Faktorial dari 1 hanya 1. Kami tidak perlu melakukan perkalian sama sekali. Sepertinya jika kita akan untuk mencoba dan memecahkan masalah ini, dan kita perlu menghentikan rekursi suatu tempat, kita mungkin ingin berhenti ketika kita sampai 1. Kami tidak ingin berhenti sebelum itu. 

Jadi jika kita mendefinisikan fungsi faktorial kami, inilah kerangka untuk bagaimana kita bisa melakukan itu. Kita perlu pasang di dua things-- kasus dasar dan kasus rekursif. Apa kasus dasar? Jika n adalah sama dengan 1, kembali 1-- itu masalah yang sangat sederhana untuk memecahkan. 

Faktorial dari 1 adalah 1. Ini bukan kali 1 apa-apa. Ini hanya 1. Ini adalah fakta yang sangat mudah. Dan sehingga dapat menjadi kasus basis kami. Jika kita bisa melewati 1 ke ini fungsi, kami hanya akan kembali 1. 

Apa yang rekursif kasus mungkin terlihat seperti? Untuk setiap nomor lain selain 1, apa pola? Nah, jika kita mengambil faktorial dari n, itu n kali faktorial dari n minus 1. 

Jika kita mengambil faktorial dengan 3, itu 3 kali faktorial dari 3 minus 1, atau 2. Dan jika kita tidak melihat 1, jika tidak kembali n kali faktorial dari n minus 1. Ini cukup sederhana. 

Dan demi memiliki sedikit bersih dan kode lebih elegan, tahu bahwa jika kita memiliki loop single-line atau single-line cabang bersyarat, kita bisa menyingkirkan semua kurung kurawal sekitar mereka. Jadi kita dapat mengkonsolidasikan ini untuk ini. Ini memiliki persis sama fungsi karena ini. 

Aku hanya mengambil pergi keriting yang kawat gigi, karena hanya ada satu baris dalam cabang-cabang bersyarat. Jadi ini berperilaku identik. Jika n adalah sama dengan 1, kembali 1. Jika tidak kembali n kali faktorial dari n minus 1. Jadi kita membuat masalah yang lebih kecil. Jika n mulai sebagai 5, kita akan kembali 5 kali faktorial dari 4. Dan kita akan melihat dalam satu menit ketika kita berbicara tentang stack-- panggilan di video lain di mana kita berbicara tentang memanggil stack-- kita akan belajar tentang mengapa persis proses ini bekerja. 

Tapi sementara faktorial 5 mengatakan kembali 5 kali faktorial 4, dan 4 akan mengatakan, OK, baik, pulang 4 kali faktorial dari 3. Dan seperti yang Anda lihat, kami semacam mendekati 1. Kami semakin dekat dan lebih dekat dengan kasus dasar. 

Dan setelah kita memukul kasus dasar, semua fungsi sebelumnya memiliki jawaban yang mereka cari. Faktorial 2 berkata kembali 2 kali faktorial dari 1. Nah, faktorial 1 kembali 1. Jadi panggilan untuk faktorial dari 2 dapat kembali 2 kali 1, dan memberikan yang kembali ke faktorial 3, yang sedang menunggu hasil itu. 

Dan kemudian dapat menghitung hasilnya, 3 kali 2 adalah 6, dan mengembalikannya kepada faktorial dari 4. Dan lagi, kita memiliki video pada panggilan stack di mana ini diilustrasikan sedikit lebih dari apa yang saya katakan sekarang. Tapi ini itu. Ini saja adalah solusi untuk menghitung faktorial dari sebuah nomor. 

Ini hanya empat baris kode. Itu cukup keren, kan? Ini semacam seksi. 

Jadi secara umum, tetapi tidak selalu, fungsi rekursif dapat menggantikan loop dalam fungsi non-rekursif. Jadi di sini, berdampingan, adalah berulang versi fungsi faktorial. Kedua menghitung ini hal yang sama. 

Mereka berdua menghitung faktorial dari n. Versi di sebelah kiri menggunakan rekursi untuk melakukannya. Versi di sebelah kanan menggunakan iterasi untuk melakukannya. 

Dan pemberitahuan, kita harus mendeklarasikan sebuah produk variabel integer. Dan kemudian kita loop. Selama n lebih besar dari 0, kita menjaga mengalikan bahwa produk oleh n dan decrementing n sampai kita menghitung produk. Jadi dua fungsi ini, sekali lagi, melakukan hal yang sama. Tapi mereka tidak melakukannya di cara yang persis sama. 

Sekarang, adalah mungkin untuk memiliki lebih dari satu basis kasus atau lebih dari satu kasus rekursif, tergantung apa fungsi Anda sedang mencoba untuk melakukan. Anda tidak harus hanya terbatas kasus dasar tunggal atau rekursif tunggal kasus. Jadi contoh dari sesuatu dengan beberapa kasus basis mungkin this-- yang Urutan nomor Fibonacci. 

Anda mungkin ingat dari hari SD bahwa urutan Fibonacci didefinisikan seperti this-- elemen pertama adalah 0. Elemen kedua adalah 1. Kedua mereka adalah hanya dengan definisi. 

Kemudian setiap elemen lain didefinisikan sebagai jumlah dari n minus 1 dan n minus 2. Jadi elemen ketiga akan 0 ditambah 1 adalah 1. Dan kemudian elemen keempat akan menjadi elemen kedua, 1, ditambah elemen ketiga, 1. Dan itu akan menjadi 2. Dan seterusnya dan seterusnya. 

Jadi dalam hal ini, kita memiliki dua kasus dasar. Jika n adalah sama dengan 1, kembali 0. Jika n adalah sama dengan 2, kembali 1. Jika tidak, kembali Fibonacci dari n minus 1 ditambah Fibonacci dari n minus 2. 

Jadi itulah beberapa kasus dasar. Bagaimana beberapa kasus rekursif? Nah, ada sesuatu disebut dugaan Collatz. Saya tidak akan mengatakan, Anda tahu apa itu, karena itu sebenarnya akhir kita masalah untuk video tertentu. Dan itu latihan kami untuk bekerja bersama-sama. 

Jadi, inilah apa Collatz dugaan is-- itu berlaku untuk setiap bilangan bulat positif. Dan berspekulasi bahwa itu selalu mungkin untuk mendapatkan kembali 1 jika Anda mengikuti langkah-langkah ini. Jika n adalah 1, berhenti. Kita harus kembali ke 1 jika n adalah 1. 

Jika tidak, melalui ini Proses lagi pada n dibagi 2. Dan lihat apakah Anda bisa mendapatkan kembali ke 1. Jika tidak, jika n ganjil, melalui Proses ini lagi pada 3n ditambah 1, atau 3 kali n ditambah 1. Jadi di sini kita memiliki kasus basa tunggal. Jika n adalah sama dengan 1, berhenti. Kami tidak melakukan rekursi lagi. 

Tapi kami memiliki dua kasus rekursif. Jika n genap, kami melakukan satu rekursif kasus, memanggil n dibagi 2. Jika n ganjil, kita melakukan yang berbeda rekursif kasus pada 3 kali n ditambah 1. 

Dan tujuan untuk video ini untuk mengambil kedua, jeda video, dan mencoba dan menulis ini fungsi rekursif Collatz di mana Anda lulus dalam nilai n, dan menghitung berapa banyak langkah itu dibutuhkan untuk sampai ke 1 jika Anda mulai dari n dan Anda mengikuti langkah-langkah di atas. Jika n adalah 1, dibutuhkan 0 langkah. Jika tidak, itu akan mengambil satu langkah ditambah namun banyak langkah yang diperlukan di kedua n dibagi 2 jika n genap, atau 3n ditambah 1 jika n ganjil. 

Sekarang, saya sudah memasang di layar sini beberapa hal tes untuk Anda, beberapa kasus tes untuk Anda, untuk melihat apa berbagai nomor Collatz ini, dan juga ilustrasi dari langkah-langkah yang perlu ditempuh sehingga Anda dapat semacam melihat proses ini dalam tindakan. Jadi jika n adalah sama dengan 1, Collatz dari n adalah 0. Anda tidak perlu melakukan apa saja untuk mendapatkan kembali ke 1. Anda sudah ada. 

Jika n adalah 2, dibutuhkan satu langkah untuk sampai ke 1. Anda mulai dengan 2. Nah, 2 tidak sama dengan 1. Jadi itu akan menjadi salah satu langkah ditambah namun banyak langkah itu mengambil n dibagi 2. 

2 dibagi dengan 2 adalah 1. Sehingga dibutuhkan satu langkah ditambah namun banyak langkah yang diperlukan untuk 1. 1 mengambil langkah nol. 

Untuk 3, seperti yang Anda lihat, ada beberapa langkah yang terlibat. Anda pergi dari 3. Dan kemudian Anda pergi ke 10, 5, 16, 8, 4, 2, 1. Dibutuhkan tujuh langkah untuk kembali ke 1. Dan seperti yang Anda lihat, ada beberapa uji kasus lain di sini untuk menguji program anda. Jadi sekali lagi, menghentikan video sementara. Dan aku akan pergi melompat kembali sekarang untuk apa sebenarnya proses di sini, apa dugaan ini. 

Lihat apakah Anda dapat mengetahui bagaimana mendefinisikan Collatz dari n sehingga menghitung berapa banyak langkah yang diperlukan untuk mendapatkan 1. Jadi mudah-mudahan, Anda telah berhenti video dan Anda tidak hanya menunggu saya untuk memberikan jawabannya di sini. Tapi jika Anda, baik, inilah jawabannya pula. 

Jadi, inilah definisi mungkin dari fungsi Collatz. Basis kami case-- jika n adalah sama dengan 1, kita kembali 0. Tidak mengambil langkah-langkah untuk kembali ke 1. 

Jika tidak, kita memiliki dua cases-- rekursif satu untuk nomor genap dan satu untuk ganjil. Cara saya menguji nomor bahkan adalah untuk memeriksa apakah n mod 2 sama dengan 0. Ini pada dasarnya adalah, sekali lagi, mengajukan pertanyaan, jika Anda ingat is-- apa mod jika saya membagi n oleh 2 adalah tidak ada sisa? Itu akan menjadi genap. 

Dan jadi jika n mod 2 sama dengan 0 adalah pengujian ini genap. Jika demikian, saya ingin kembali 1, karena ini jelas mengambil satu langkah ditambah Collatz dari apapun jumlah setengah dari saya. Jika tidak, saya ingin kembali 1 ditambah Collatz dari 3 kali n ditambah 1. Itu yang lain Langkah rekursif yang kita bisa mengambil untuk menghitung Collatz-- jumlah langkah dibutuhkan untuk mendapatkan kembali 1 diberi nomor. Jadi mudah-mudahan, contoh ini memberi Anda sedikit dari rasa prosedur rekursif. Mudah-mudahan, Anda berpikir kode adalah sedikit lebih indah jika diterapkan dalam cara rekursif elegan. Tetapi bahkan jika tidak, rekursi adalah alat yang sangat kuat tetap. Dan jadi pasti sesuatu untuk mendapatkan kepala Anda sekitar, karena Anda akan dapat membuat program keren menggunakan rekursi yang mungkin menjadi kompleks untuk menulis jika Anda menggunakan loop dan iterasi. Aku Doug Lloyd. Ini adalah CS50.