>> ZAMYLA: Untuk memahami rekursi, anda mesti
memahami rekursi.
Mempunyai rekursi dalam program reka bentuk cara bahawa anda mempunyai diri rujukan-
definisi.
Struktur data rekursif, misalnya, adalah struktur data yang
termasuk diri mereka dalam definisi mereka.
Tetapi hari ini, kita akan memberi tumpuan kepada fungsi rekursif.
>> Ingat bahawa fungsi mengambil input, hujah-hujah, dan mengembalikan nilai seperti mereka
output diwakili oleh gambar rajah ini di sini.
Kami akan berfikir dari kotak sebagai badan majlis itu, yang mengandungi set
arahan yang mentafsirkan input dan memberikan output.
Mengambil melihat dengan lebih dekat di dalam badan fungsi boleh mendedahkan panggilan ke
fungsi lain juga.
Ambil fungsi ini mudah, foo, yang mengambil rentetan tunggal sebagai input dan
cetakan bagaimana banyak surat tali yang mempunyai.
Fungsi strlen, untuk panjang tali, dipanggil, yang keluaran adalah
diperlukan untuk panggilan kepada printf.
>> Sekarang, apa yang membuatkan fungsi rekursi istimewa ialah ia panggilan sendiri.
Kami boleh mewakili rekursi ini panggilan dengan oren anak panah ini
menggelung kembali kepada dirinya sendiri.
Tetapi melaksanakan sendiri lagi hanya akan membuat satu lagi panggilan rekursif, dan
yang lain dan yang lain.
Tetapi fungsi rekursi tidak boleh tidak terbatas.
Mereka perlu berakhir entah bagaimana, atau anda program akan berjalan selama-lamanya.
>> Oleh itu, kita perlu mencari jalan untuk memecahkan daripada panggilan rekursif.
Kami menyeru ini kes asas.
Apabila keadaan kes asas dipenuhi, fungsi mengembalikan tanpa membuat
satu lagi panggilan rekursif.
Ambil fungsi ini, hi, fungsi tidak sah yang mengambil int n sebagai input.
Kes asas diutamakan.
Jika n adalah kurang daripada sifar, bye cetak dan kembali Untuk semua kes lain,
fungsi akan mencetak hi dan melaksanakan panggilan rekursif.
Satu lagi panggilan kepada fungsi hi dengan nilai input decremented.
>> Sekarang, walaupun kita mencetak hi, yang fungsi tidak akan menamatkan sehingga kita
kembali jenis pulangan, dalam kes ini tidak sah.
Jadi bagi setiap n selain daripada kes asas, fungsi hi ini akan kembali hi
n tolak 1.
Kerana fungsi ini adalah tidak sah walaupun, kita tidak akan jelas menaip kembali di sini.
Kami hanya akan melaksanakan fungsi tersebut.
Jadi memanggil hi (3) akan mencetak dan hi melaksanakan hi (2) yang melaksanakan hi (1) satu
yang melaksanakan hi (0), di mana keadaan kes asas dipenuhi.
Jadi hi (0) mencetak bye dan pulangan.
>> OK.
Jadi sekarang kita memahami asas-asas fungsi rekursif, bahawa mereka perlu
sekurang-kurangnya satu kes asas serta panggilan rekursif, mari kita beralih kepada
contoh lebih bermakna.
Satu yang tidak hanya kembali tidak sah tidak kira apa.
>> Mari kita lihat faktoran operasi yang paling biasa digunakan dalam
pengiraan kebarangkalian.
Faktorial n adalah hasil dari setiap integer positif kurang daripada
dan sama dengan n.
Lima Jadi faktorial adalah 5 kali 4 kali 3 kali 2 kali 1 bagi memberikan 120.
Empat faktorial adalah 4 kali 3 kali 2 kali 1 untuk memberi 24.
Dan peraturan yang sama terpakai kepada mana-mana integer positif.
>> Jadi bagaimana kita boleh menulis rekursif yang fungsi yang mengira faktorial yang
sebilangan?
Nah, kita perlu mengenal pasti kedua-dua kes asas dan panggilan rekursif.
Panggilan rekursif akan sama untuk semua hal melainkan asas
kes, yang bermakna bahawa kita akan perlu mencari corak yang akan memberikan kita kita
keputusan yang dikehendaki.
>> Sebagai contoh ini, lihat bagaimana 5 faktorial melibatkan mendarabkan 4 dengan 3 oleh 2 dengan 1
Dan pendaraban yang sama didapati di sini,
definisi 4 faktor.
Jadi kita lihat bahawa 5 faktorial hanya 5 kali 4 faktor.
Sekarang tidak corak ini memohon 4 faktorial juga?
Ya.
Kita lihat bahawa 4 faktorial mengandungi pendaraban 3 kali 2 kali 1,
definisi yang sama seperti 3 faktor.
Jadi 4 faktorial adalah sama dengan 4 kali 3 faktorial, dan sebagainya dan sebagainya kami
corak melekat sehingga 1 faktorial, yang oleh definisi adalah sama dengan 1.
>> Tidak ada positif lain integer kiri.
Jadi kita mempunyai corak untuk panggilan rekursif kami.
n faktorial adalah sama dengan n kali faktorial n tolak 1.
Dan kes asas kita?
Itu hanya akan definisi kita 1 faktor.
>> Jadi sekarang kita boleh bergerak ke bertulis kod untuk majlis itu.
Untuk kes asas, kita akan mempunyai keadaan n sama setaraf 1, di mana
kami akan kembali 1.
Kemudian bergerak ke panggilan rekursif, kami akan kembali n kali
faktorial n tolak 1.
>> Sekarang mari kita menguji kita ini.
Mari kita cuba faktorial 4.
Per fungsi kami itu sama 4 kali faktorial (3).
Faktorial (3) adalah sama dengan 3 kali faktorial (2).
Faktorial (2) adalah sama dengan 2 kali faktorial (1), yang mengembalikan 1.
Faktorial (2) kini kembali 2 kali 1, 2.
Faktorial (3) kini boleh kembali 3 kali 2, 6.
Dan akhirnya, faktorial (4) kembali 4 kali 6, 24.
>> Jika anda menghadapi apa-apa kesukaran dengan seruan rekursif, berpura-pura bahawa
fungsi kerja-kerja sudah.
Apa yang saya maksudkan dengan ini adalah bahawa anda harus mempercayai panggilan rekursif anda untuk kembali
nilai-nilai yang betul.
Sebagai contoh, jika saya tahu bahawa faktorial (5) bersamaan 5 kali
faktorial (4), saya akan percaya bahawa faktorial (4) akan memberi saya 24.
Anggapkannya sebagai satu pemboleh ubah, jika anda akan, seperti jika anda sudah ditakrifkan
faktorial (4).
Jadi untuk apa-apa faktorial (n), ia adalah produk n dan
faktorial sebelumnya.
Dan faktorial ini sebelumnya diperolehi dengan menghubungi
faktorial n tolak 1.
>> Sekarang, lihat jika anda boleh melaksanakan berfungsi diri rekursif.
Muatkan terminal anda, atau run.cs50.net, dan menulis sejumlah fungsi
yang mengambil integer n dan mengembalikan jumlah semua positif berturut-turut
integer dari n kepada 1.
Saya telah menulis daripada jumlah wang yang beberapa Nilai untuk membantu anda kami.
Pertama, memikirkan keadaan kes asas.
Kemudian, melihat jumlah (5).
Bolehkah anda menyatakan ia dari segi jumlah wang yang lain?
Kini, apa kira-kira jumlah (4)?
Bagaimana anda boleh meluahkan jumlah (4) dari segi jumlah yang lain?
>> Sebaik sahaja anda mempunyai jumlah (5) dan jumlah (4) dinyatakan dari segi jumlah wang yang lain, lihat
jika anda boleh mengenal pasti corak untuk jumlah (n).
Jika tidak, cuba beberapa nombor lain dan menyatakan jumlah wang mereka dalam
segi lain nombor.
Dengan mengenal pasti corak untuk diskret nombor, anda juga pada cara anda untuk
mengenal pasti corak untuk mana-mana n.
>> Rekursi adalah alat yang benar-benar kuat, jadi sudah tentu ia tidak terhad kepada
fungsi matematik.
Jadi semula boleh digunakan dengan amat berkesan apabila berurusan dengan pokok-pokok misalnya.
Semak pendek di atas pokok untuk lebih kajian menyeluruh, tetapi untuk sekarang
ingat bahawa pokok-pokok carian binari, dalam tertentu, terdiri daripada nod, setiap
dengan nilai dan dua petunjuk nod.
Biasanya, ini diwakili oleh nod ibu bapa mempunyai satu baris menunjuk
kepada nod anak kiri dan satu ke nod anak yang betul.
Struktur carian binari pokok meminjam dirinya dengan baik
untuk carian rekursif.
Panggilan rekursif sama ada pas dalam kiri atau nod yang betul, tetapi lebih
itu ringkasnya pokok.
>> Katakanlah anda mahu untuk melakukan pembedahan ke atas setiap nod tunggal dalam pokok binari.
Bagaimana anda boleh pergi tentang itu?
Nah, anda boleh menulis rekursif yang fungsi yang melaksanakan operasi
pada nod induk dan membuat rekursif yang panggilan untuk majlis yang sama,
lulus dalam kiri dan nod anak betul.
Sebagai contoh, fungsi ini, foo, yang menukar nilai nod yang diberikan dan
semua kanak-kanak untuk 1.
Kes asas yang punca nod null fungsi untuk kembali, menunjukkan
bahawa tidak ada apa-apa nod kiri dalam yang sub-pokok.
>> Mari kita berjalan melaluinya.
Ibu bapa pertama adalah 13.
Kami menukar nilai kepada 1, dan kemudian memanggil fungsi kami di sebelah kiri dan juga
sebagai betul.
Fungsi, foo, dipanggil di sebelah kiri sub-pokok pertama, jadi nod kiri
akan ditukarkan ke 1 dan foo akan dipanggil pada kanak-kanak yang nod ini,
yang pertama di sebelah kiri dan kemudian yang betul, dan sebagainya dan sebagainya.
Dan memberitahu mereka bahawa cawangan tidak mempunyai lagi anak-anak supaya proses yang sama
akan terus untuk kanak-kanak yang betul sehingga nod keseluruhan pokok adalah
ditukarkan ke 1.
>> Seperti yang anda lihat, anda tidak terhad dengan hanya satu panggilan rekursif.
Sama seperti ramai seperti yang akan mendapatkan pekerjaan yang dilakukan.
Bagaimana jika anda mempunyai pokok di mana setiap nod mempunyai tiga orang anak,
Kiri, tengah, dan kanan?
Bagaimana anda mengedit foo?
Nah, mudah.
Hanya menambah satu lagi panggilan rekursif dan lulus dalam penunjuk nod tengah.
>> Jadi semula adalah sangat kuat dan tidak lagi elegan, tetapi ia boleh menjadi satu
konsep yang sukar pada mulanya, jadi pesakit dan mengambil masa anda.
Bermula dengan kes asas.
Ia biasanya yang paling mudah untuk mengenal pasti, dan kemudian anda boleh bekerja
ke belakang dari sana.
Anda tahu anda perlukan untuk mencapai anda kes asas, jadi kekuatan yang
memberi anda beberapa petunjuk.
Cuba untuk menyatakan satu kes tertentu dalam segi kes-kes lain, atau sub-set.
>> Terima kasih kerana menonton ini pendek.
Sekurang-kurangnya, sekarang anda boleh memahami jenaka seperti ini.
Nama saya Zamyla, dan ini adalah cs50.
>> Ambil fungsi ini, hi, a fungsi tidak sah yang mengambil
int satu, n, sebagai input.
Kes asas diutamakan.
Jika n adalah kurang daripada 0, cetak "Bye" dan kembali.