>> [Bermain muzik]
>> DOUG LLOYD: Anda mungkin berfikir bahawa kod hanya digunakan untuk menyelesaikan sesuatu tugas.
Anda menulis keluar.
Ia melakukan sesuatu.
Yang cukup banyak ia.
>> Anda menyusun ia.
Anda menjalankan program ini.
Anda baik untuk pergi.
>> Tetapi percaya atau tidak, jika anda kod untuk masa yang lama,
anda sebenarnya mungkin datang untuk melihat kod sebagai sesuatu yang indah.
Ia menyelesaikan masalah di cara yang sangat menarik,
atau ada hanya sesuatu yang benar-benar kemas tentang cara ia kelihatan.
Anda mungkin ketawa pada saya, tetapi ia adalah benar.
Dan rekursi adalah salah satu cara untuk menyusun mendapat idea ini
cantik, anggun-cari kod.
Ia menyelesaikan masalah dengan cara yang yang menarik, mudah untuk menggambarkan,
dan menghairankan pendek.
>> Kerja-kerja cara rekursi adalah, fungsi rekursi
ditakrifkan sebagai fungsi yang menyeru sendiri sebagai sebahagian daripada pelaksanaannya.
Yang mungkin kelihatan sedikit pelik, dan kita akan melihat sedikit
tentang bagaimana kerja-kerja ini dalam seketika.
Tetapi sekali lagi, ini prosedur rekursi adalah
akan menjadi begitu elegan kerana mereka akan
untuk menyelesaikan masalah ini tanpa yang mempunyai semua fungsi-fungsi lain
atau ini gelung panjang.
Anda akan melihat bahawa ini rekursi prosedur akan kelihatan begitu pendek.
Dan mereka benar-benar akan membuat kod anda kelihatan lebih lebih cantik.
>> Saya akan memberikan contoh ini untuk melihat bagaimana
prosedur rekursi mungkin ditakrifkan.
Jadi, jika anda sudah biasa dengan ini dari kelas matematik tahun yang lalu,
ada yang sesuatu yang dinamakan fungsi faktorial, yang biasanya
ditandakan sebagai tanda seru, yang ditakrifkan atas semua integer positif.
Dan cara yang n faktorial dikira
adalah anda membiak semua nombor kurang daripada
atau sama dengan n together-- semua integer kurang daripada
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 sebagainya.
Anda akan mendapat idea.
>> Sebagai pengaturcara, kita tidak menggunakan n, tanda seru.
Oleh itu, kita akan menentukan faktorial berfungsi sebagai hakikat n.
Dan kami akan menggunakan faktorial untuk mewujudkan penyelesaian rekursi kepada masalah.
Dan saya fikir anda mungkin mendapati bahawa ia banyak lebih visual
menarik daripada lelaran versi ini, yang
kami juga akan mengambil lihat di dalam seketika.
>> Jadi di sini adalah beberapa pun facts-- intended--
tentang factorial-- yang fungsi faktorial.
Faktorial 1, seperti yang saya katakan, adalah 1.
Faktorial 2 adalah 2 kali 1.
Faktorial 3 adalah 3 kali 2 kali 1, dan sebagainya.
Kita bercakap tentang 4 dan 5 sudah.
>> Tetapi melihat ini, tidak adakah ini benar?
Bukankah faktorial 2 Sama 2 kali faktorial 1?
Maksud saya, faktorial 1 adalah 1.
Jadi mengapa tidak boleh kita hanya mengatakan bahawa, sejak faktorial 2 adalah 2 kali 1,
ia adalah benar-benar hanya 2 kali faktorial 1?
>> Dan kemudian melanjutkan idea itu, tidak faktorial 3
hanya 3 kali faktorial 2?
Dan faktorial 4 adalah 4 kali faktorial 3, dan sebagainya?
Malah, faktorial yang mana-mana nombor boleh hanya
dinyatakan jika kita jenis untuk melaksanakan ini selama-lamanya.
Kita boleh jenis umum masalah faktorial
kerana ia adalah n kali faktorial n tolak 1.
Ia adalah n kali hasil daripada semua nombor yang kurang daripada saya.
>> Idea ini, ini generalisasi masalah ini,
membolehkan kita untuk secara rekursif menentukan fungsi faktorial.
Apabila anda menentukan fungsi secara berulang, ada
dua perkara yang perlu menjadi sebahagian daripadanya.
Anda perlu mempunyai sesuatu yang dipanggil kes asas, yang apabila anda mencetuskan ia,
akan menghentikan proses rekursi.
>> Jika tidak, satu majlis yang menyeru itself-- kerana anda mungkin imagine--
boleh pergi selama-lamanya.
Fungsi panggilan fungsi memanggil panggilan fungsi
fungsi panggilan fungsi.
Jika anda tidak mempunyai cara yang untuk menghentikannya, program anda
akan terperangkap dengan berkesan di gelung tak terhingga.
Ia akan kemalangan akhirnya, kerana ia akan kehabisan memori.
Tetapi itu pokoknya.
>> Kita perlu mempunyai cara lain untuk menghentikan perkara selain terhempas program kami,
kerana program yang kemalangan adalah mungkin tidak cantik atau elegan.
Dan dengan itu kita panggil ini kes asas.
Ini adalah penyelesaian yang mudah kepada masalah yang berhenti
proses rekursi daripada berlaku.
Jadi itulah satu bahagian fungsi rekursi.
>> Bahagian kedua adalah kes rekursi.
Dan di sinilah rekursi sebenarnya akan berlaku.
Ini adalah di mana fungsi akan memanggil sendiri.
>> Ia tidak menghukum dirinya betul-betul cara yang sama ia dipanggil.
Ia akan menjadi sedikit perbezaan yang membuat masalah itu
cuba untuk menyelesaikan sedikit pemudi yang lebih kecil.
Tetapi ia secara amnya pas tanggungjawab itu menyelesaikan sebahagian besar daripada penyelesaian
panggilan yang berbeza ke bawah baris.
>> Yang kelihatan ini seperti kes asas di sini?
Yang mana satu kelihatan seperti ini penyelesaian paling mudah untuk masalah?
Kami mempunyai sekumpulan faktorial, dan kita boleh terus
akan pada-- 6, 7, 8, 9, 10, dan sebagainya.
>> Tetapi salah satu kelihatan seperti ini kes baik untuk menjadi kes asas.
Ia adalah penyelesaian yang sangat mudah.
Kami tidak mempunyai berbuat apa-apa yang istimewa.
>> Faktorial 1 hanya 1.
Kami tidak mempunyai melakukan apa-apa pendaraban sama sekali.
Ia seolah-olah seperti jika kita akan untuk mencuba dan menyelesaikan masalah ini,
dan kita perlu untuk menghentikan jadi semula di suatu tempat,
kita mungkin mahu berhenti apabila kita dapat 1.
Kami tidak mahu berhenti sebelum itu.
>> Jadi, jika kita menentukan fungsi faktorial kami,
di sini adalah rangka untuk bagaimana kita boleh berbuat demikian.
Kita perlu pasangkan kedua-dua things-- kes asas dan kes rekursi.
Apakah kes asas?
Jika n adalah sama dengan 1, kembali 1-- itulah masalah benar-benar mudah untuk menyelesaikan.
>> Faktorial 1 adalah 1.
Ia bukan 1 kali apa-apa.
Ia hanya 1.
Ia adalah satu fakta yang sangat mudah.
Dan sebagainya yang boleh menjadi kes asas kami.
Jika kita mendapat lulus 1 ke dalam ini fungsi, kita hanya akan kembali 1.
>> Apa yang rekursi yang kes mungkin kelihatan seperti?
Bagi setiap nombor lain selain 1, apa corak?
Nah, jika kami mengambil faktorial n,
ia n kali faktorial n tolak 1.
>> Jika kita mengambil faktorial sebanyak 3, ia 3 kali faktorial 3 tolak 1,
atau 2.
Dan jadi jika kita tidak melihat 1, jika tidak,
pulangan n kali faktorial n tolak 1.
Ia agak mudah.
>> Dan demi yang mempunyai sedikit lebih bersih dan lebih elegan kod,
tahu bahawa jika kita mempunyai gelung tunggal talian atau tunggal talian cawangan bersyarat,
kita boleh menghilangkan semua daripada pendakap kerinting di sekeliling mereka.
Oleh itu, kita boleh menggabungkan ini dengan ini.
Ini mempunyai sama fungsi seperti ini.
>> Saya hanya mengambil dari kerinting kawat gigi, kerana ada hanya satu baris
dalam orang-orang cawangan bersyarat.
Jadi ini berkelakuan sepercaman.
Jika n adalah sama dengan 1, kembali 1.
Jika tidak kembali n kali faktorial n tolak 1.
Jadi, kita membuat masalah yang lebih kecil.
Jika n bermula sebagai 5, kita akan kembali 5 kali faktorial 4.
Dan kita akan melihat dalam satu minit apabila kita bercakap tentang stack-- panggilan dalam video lain
di mana kita bercakap mengenai memanggil stack-- kita akan belajar
tentang mengapa sebenarnya proses ini berfungsi.
>> Tetapi manakala faktorial 5 mengatakan kembali 5 kali faktorial 4, dan 4
akan berkata, OK, baik, pulangan 4 kali faktorial 3.
Dan seperti yang anda boleh lihat, kami semacam menghampiri 1.
Kami mendapat lebih dekat dan lebih dekat dengan kes asas.
>> Dan apabila kita mencapai kes asas, semua fungsi sebelum
mempunyai jawapan yang mereka cari.
Faktorial 2 telah berkata pulangan 2 kali faktorial 1.
Nah, faktorial 1 mengembalikan 1.
Jadi panggilan untuk faktorial 2 boleh kembali 2 kali 1,
dan memberikan yang kembali ke faktorial 3, yang sedang menunggu untuk keputusan itu.
>> Dan kemudian ia boleh mengira hasilnya, 3 kali 2 ialah 6,
dan memberikan kembali kepada faktorial 4.
Dan sekali lagi, kita mempunyai video pada timbunan panggilan
di mana ini digambarkan sedikit lebih daripada apa yang saya katakan sekarang.
Tetapi ini adalah ia.
Ini sahaja adalah penyelesaian untuk mengira faktorial bagi nombor.
>> Ia hanya empat baris kod.
Yang agak sejuk, bukan?
Ia adalah jenis seksi.
>> Jadi secara umum, tetapi tidak biasa, fungsi rekursi
boleh menggantikan gelung dalam fungsi bukan rekursi.
Jadi di sini, sebelah menyebelah, adalah lelaran versi fungsi faktorial.
Kedua-dua mengira ini perkara yang sama.
>> Mereka berdua mengira faktorial n.
Versi di sebelah kiri menggunakan rekursi untuk melakukannya.
Versi di sebelah kanan menggunakan lelaran untuk melakukannya.
>> Dan notis, kita perlu mengisytiharkan pembolehubah produk integer.
Dan kemudian kita gelung.
Selagi n lebih besar daripada 0, kita menyimpan mendarabkan produk dengan n
dan decrementing n sehingga kita mengira produk.
Jadi kedua-dua fungsi, sekali lagi, melakukan perkara yang sama.
Tetapi mereka tidak melakukannya dalam betul-betul cara sama.
>> Kini, ia adalah mungkin untuk mempunyai lebih daripada satu asas
kes atau lebih daripada satu kes rekursi, bergantung
kepada apa fungsi anda cuba lakukan.
Anda tidak semestinya hanya terhad kepada kes asas tunggal atau rekursi tunggal
kes.
Jadi contoh sesuatu dengan kes-kes asas pelbagai
mungkin this-- yang Fibonacci urutan nombor.
>> Anda mungkin ingat dari hari sekolah rendah
urutan Fibonacci ditakrifkan seperti this-- elemen pertama adalah 0.
Elemen kedua ialah 1.
Kedua-dua mereka adalah hanya dengan definisi.
>> Maka setiap elemen lain ditakrifkan sebagai jumlah n tolak 1 dan n tolak 2.
Jadi elemen yang ketiga akan menjadi 0 tambah 1 adalah 1.
Dan kemudian elemen keempat akan menjadi elemen kedua, 1,
ditambah elemen yang ketiga, 1.
Dan yang akan menjadi 2.
Dan sebagainya dan sebagainya.
>> Jadi dalam kes ini, kami mempunyai dua kes asas.
Jika n adalah sama dengan 1, kembali 0.
Jika n adalah sama dengan 2, kembali 1.
Jika tidak, kembali Fibonacci n tolak 1 tambah Fibonacci n tolak 2.
>> Jadi itulah kes pangkalan berbilang.
Bagaimana pula dengan pelbagai kes rekursi?
Well, ada sesuatu dipanggil dugaan Collatz itu.
Saya tidak akan berkata, anda tahu apa itu,
kerana ia sebenarnya akhir kami masalah untuk video ini tertentu.
Dan ia adalah senaman kami untuk bekerja bersama-sama.
>> Jadi di sini adalah apa yang Collatz tekaan is--
ia terpakai kepada setiap integer positif.
Dan ia membuat spekulasi bahawa itu selalu mungkin untuk kembali
1 jika anda mengikuti langkah-langkah ini.
Jika n adalah 1, berhenti.
Kami telah mendapat kembali ke 1 jika n 1.
>> Jika tidak, melalui ini proses sekali lagi pada n dibahagikan dengan 2.
Dan lihat jika anda boleh kembali kepada 1.
Jika tidak, jika n ganjil, melalui proses ini sekali lagi pada 3n campur 1,
atau 3 kali n campur 1.
Jadi di sini kita mempunyai kes asas tunggal.
Jika n adalah sama dengan 1, berhenti.
Kami tidak melakukan apa-apa rekursi lagi.
>> Tetapi kita mempunyai dua kes rekursi.
Jika n adalah lebih, kita melakukan satu rekursi kes, laungan n dibahagikan dengan 2.
Jika n ganjil, yang kita lakukan yang berbeza kes rekursi 3 kali n campur 1.
>> Dan supaya matlamat untuk video ini adalah untuk mengambil kedua, jeda video,
dan cuba menulis ini fungsi rekursi Collatz
di mana anda lulus dalam nilai n, dan ia mengira berapa banyak langkah-langkah yang
mengambil masa untuk sampai ke 1 jika anda bermula dari n dan anda mengikuti langkah-langkah ke atas.
Jika n adalah 1, ia mengambil masa 0 langkah.
Jika tidak, ia akan mengambil satu langkah plus bagaimanapun
banyak langkah-langkah yang diperlukan sama ada di n dibahagikan dengan 2 jika n walaupun, atau 3n campur 1
jika n ganjil.
>> Sekarang, saya telah meletakkan pada skrin di sini beberapa perkara ujian untuk anda,
beberapa ujian kes untuk anda, untuk melihat apa ini pelbagai nombor Collatz berada,
dan juga ilustrasi daripada langkah-langkah yang
perlu melalui supaya anda boleh semacam melihat proses ini dalam tindakan.
Jadi, jika n adalah sama dengan 1, Collatz n adalah 0.
Anda tidak perlu berbuat apa sahaja untuk mendapatkan kembali ke 1.
Anda sudah ada.
>> Jika n adalah 2, ia mengambil masa satu langkah untuk sampai ke 1.
Anda bermula dengan 2.
Nah, 2 tidak sama dengan 1.
Oleh itu, ia akan menjadi satu langkah plus bagaimanapun banyak langkah-langkah yang
mengambil n dibahagikan dengan 2.
>> 2 dibahagikan dengan 2 adalah 1.
Jadi ia mengambil satu langkah plus bagaimanapun banyak langkah-langkah yang diambil untuk 1.
1 mengambil langkah sifar.
>> Untuk 3, seperti yang anda lihat, ada agak beberapa langkah yang terlibat.
Anda pergi dari 3.
Dan kemudian anda pergi ke 10, 5, 16, 8, 4, 2, 1.
Ia mengambil masa tujuh langkah untuk kembali kepada 1.
Dan seperti yang anda boleh lihat, terdapat beberapa kes-kes ujian lain di sini
untuk menguji program anda.
Jadi sekali lagi, jeda video.
Dan saya akan pergi melompat kembali sekarang untuk apa proses sebenar di sini,
apa andaian ini boleh.
>> Lihat jika anda boleh memikirkan bagaimana untuk menentukan Collatz n
supaya ia mengira berapa banyak beberapa langkah yang diperlukan untuk mendapatkan ke 1.
Jadi mudah-mudahan, anda telah dihentikan sementara video dan anda tidak hanya menunggu saya
memberikan jawapan di sini.
Tetapi jika anda adalah, baik, inilah jawapan pula.
>> Jadi di sini adalah definisi mungkin fungsi Collatz itu.
Pangkalan kami case-- jika n sama dengan 1, kita kembali 0.
Ia tidak mengambil apa-apa langkah-langkah untuk kembali kepada 1.
>> Jika tidak, kita mempunyai dua cases-- rekursi satu untuk nombor genap dan satu untuk ganjil.
Cara yang saya menguji nombor genap adalah untuk memeriksa jika n mod 2 sama dengan 0.
Ini adalah pada dasarnya, sekali lagi, bertanya soalan,
jika anda masih ingat apa mod is-- jika saya jurang n dengan 2 adalah tidak ada baki?
Yang akan menjadi nombor genap.
>> Dan jadi jika n mod 2 sama dengan 0 adalah ujian ini satu nombor genap.
Jika ya, saya mahu kembali 1, kerana ini adalah pasti
mengambil satu langkah plus Collatz daripada apa nombor adalah separuh daripada saya.
Jika tidak, saya mahu kembali 1 ditambah Collatz 3 kali n campur 1.
Itulah yang lain langkah rekursi yang kita
boleh mengambil untuk mengira Collatz-- bilangan langkah
ia mengambil masa untuk kembali 1 diberi nombor.
Jadi diharapkan, contoh ini memberikan anda sedikit
satu rasa yang prosedur rekursi.
Mudah-mudahan, anda berfikir kod adalah sedikit lebih cantik jika dilaksanakan
dengan cara yang elegan, rekursi.
Tetapi, jika tidak, rekursi adalah alat yang benar-benar kuat tetap.
Dan maka ia pasti sesuatu untuk mendapatkan kepala anda sekitar,
kerana anda akan dapat mewujudkan program cukup sejuk menggunakan rekursi
yang sebaliknya mungkin menjadi rumit untuk menulis jika anda menggunakan gelung dan lelaran.
Saya Doug Lloyd.
Ini adalah CS50.