DOUG LLOYD: Jika anda lihat video di rekursi,
keseluruhan proses mungkin mempunyai seolah-olah sedikit ajaib.
Bagaimanakah ia berfungsi?
Bagaimana fungsi tahu bahawa mereka perlu menunggu dan menunggu nilai lain
untuk kembali dari fungsi yang berbeza memanggil untuk mendapatkan hasil yang kita mahu?
>> Nah, sebab kerja-kerja ini adalah kerana sesuatu yang dikenali sebagai timbunan panggilan.
Apabila anda memanggil fungsi, yang sistem mengetepikan ruang dalam ingatan
untuk fungsi bahawa untuk melakukan tugasnya.
Dan kita panggil ketulan memori yang sedang diketepikan untuk setiap fungsi
memanggil bingkai tindanan atau bingkai fungsi.
Dan seperti yang anda jangkakan, bingkai tindanan
tinggal di pihak timbunan memori.
>> Lebih daripada satu fungsi bingkai tindanan boleh wujud dalam memori pada masa yang diberikan.
Jika panggilan utama perpindahan fungsi, dan langkah panggilan arah,
ketiga-tiga fungsi mempunyai bingkai terbuka.
Tetapi mereka tidak semua mempunyai bingkai aktif.
Ini bingkai disusun dalam timbunan.
Dan kerangka dari Yang baru dipanggil
fungsi adalah sentiasa di atas timbunan.
Dan yang sentiasa bingkai aktif.
Terdapat hanya benar-benar pernah satu fungsi itulah yang aktif pada satu masa.
Ia adalah salah satu di atas timbunan.
>> Apabila fungsi panggilan lain fungsi, ia semacam menekan jeda.
Ia semacam sedang ditunda, menunggu.
Dan bingkai tindanan lain ditolak ke dalam tindanan di atasnya.
Dan yang menjadi bingkai aktif.
Dan rangka dengan segera di bawahnya perlu menunggu
sehingga ia sekali lagi bingkai aktif sebelum ia boleh meneruskan tugasnya.
Apabila fungsi adalah lengkap dan ia dilakukan,
bingkai yang muncul dari timbunan.
Itulah istilah.
Dan rangka dengan segera di bawahnya, kerana saya hanya berkata,
menjadi bingkai aktif yang baru.
>> Dan jika ia memerlukan fungsi yang lain, ia akan berhenti seketika lagi.
Bingkai tindanan bahawa fungsi baru akan dapat ditolak ke bahagian atas timbunan.
Ia akan melakukan tugasnya.
Ia mungkin pop berundur.
Dan fungsi yang lain di bawahnya boleh meneruskan lagi.
>> Jadi mari kita pergi melalui ini sekali lagi, mencari pada idea fungsi faktorial
bahawa kita yang ditakrifkan dalam video rekursi untuk melihat
tepat bagaimana keajaiban di sebalik ini proses rekursi sedang berlaku.
Jadi ini adalah keseluruhan fail kita, bukan?
Kami ditakrifkan dua functions-- utama dan fakta.
Dan seperti yang kita jangkakan, mana-mana program C akan
bermula pada baris pertama utama.
>> Oleh itu, kita membuat bingkai tindanan baru untuk utama.
Dan ia akan mulai berjalan.
Panggilan utama printf.
Dan printf akan mencetak faktorial 5.
Nah, ia tidak tahu apa faktorial 5 adalah,
dan sebagainya panggilan ini sudah bergantung kepada panggilan fungsi yang lain.
Jadi utama akan berhenti seketika di sana.
Saya akan meninggalkan mereka arrow di sana, warna
ia warna yang sama dengan stack bingkai di sebelah kanan,
untuk menunjukkan bahawa utama akan membekukan di sini manakala faktorial 5 dipanggil.
>> Jadi faktorial 5 dipanggil.
Dan ia akan mula sekurang- bermula fungsi faktorial.
Ia meminta soalan aku sama dengan 1?
Adalah 5 sama dengan 1?
Well, tidak.
Jadi ia akan turun ke itu pun sebahagian, pulangan n kali
faktorial n tolak 1.
Baiklah.
>> Oleh sebab itu, faktorial 5 adalah bergantung kepada panggilan lain
untuk faktorial, lulus dalam 4 sebagai parameter.
Dan sebagainya faktorial 5 bingkai, kerangka merah,
akan membekukan di sana di garisan yang saya telah dinyatakan
dan tunggu faktorial 4 hingga selesai apa yang diperlukan untuk berbuat demikian yang maka ia
boleh menjadi bingkai aktif lagi.
>> Jadi faktorial 4 bermula pada awal faktor.
Adalah 4 sama dengan 1?
Tidak, jadi ia akan melakukan perkara yang sama.
Ia akan pergi ke cawangan lain.
Ia akan sampai ke baris kod.
OK, saya akan kembali empat kali.
Oh, faktorial 3-- supaya faktorial 4 bergantung kepada faktorial 3 penamat.
>> Dan jadi ia perlu untuk memanggil faktorial 3.
Dan itu akan pergi melalui proses yang sama lagi.
Ia bermula melalui, mendapat di sini.
Faktorial 3 bergantung pada faktorial 1.
Jadi faktorial 2 bermula, mendapat di sini.
Ia bergantung kepada faktorial 1.
Faktorial 1 bermula.
>> OKAY.
Oleh sebab itu, kami mendapat di suatu tempat yang menarik, bukan?
Oleh sebab itu, 1 adalah sama dengan 1.
Dan supaya kita kembali 1.
Pada ketika ini, kami kembali.
Majlis tersebut dilakukan.
Ia adalah tingkah laku is-- ada apa-apa lagi untuk itu yang perlu dilakukan,
dan sebagainya bingkai tindanan untuk faktorial 1 timbul di luar.
Ia selesai.
Ia kembali 1.
Dan kini, faktorial 2, yang adalah bingkai segera di bawahnya
dalam tindanan, menjadi bingkai aktif.
>> Dan ia boleh mengambil tepat di mana ia berhenti.
Ia telah menunggu Faktorial daripada 1 untuk menyelesaikan tugasnya.
Ia kini telah selesai.
Dan sebagainya di sini kita.
>> Faktorial 1 kembali nilai 1.
Jadi faktorial 2 tin katakan kembali 2 kali 1.
Tugasnya kini dilakukan.
Ia kembali 2 hingga faktorial 3, yang sedang menunggu untuk itu.
Faktorial 3 kini bingkai atas, bingkai aktif dalam timbunan.
Dan maka ia berkata, OK, baik, saya akan untuk kembali 3 kali 2, iaitu 6.
Dan saya akan memberikan yang menghargai kembali ke faktorial
4, yang telah menunggu saya.
Aku selesai.
Faktorial 3 muncul dari timbunan, dan faktorial 4 kini bingkai aktif.
>> 4 mengatakan, OK, saya akan kembali 4 kali faktorial 3, yang enam.
Itu adalah nilai yang faktorial 3 dikembalikan.
Dan sebagainya 4 kali 6 adalah 24.
Dan saya akan lulus kembali bahawa untuk faktorial
5, yang telah menunggu saya.
Faktorial 5 kini bingkai aktif.
Ia akan kembali 5 kali faktorial 4-- 5 kali 24, atau 120--
dan memberikan nilai yang kembali ke utama, yang mempunyai
telah menunggu sangat sabar untuk masa yang lama di bahagian bawah timbunan.
>> Ia adalah di mana ia bermula.
Ia membuat panggilan ini.
Beberapa bingkai mengambil alih di bahagian atas.
Ia kini kembali di atas timbunan.
Ia bingkai aktif.
Jadi utama mendapat nilai 120 kembali dari faktorial 5.
Ia telah menunggu untuk mencetak nilai itu.
Dan kemudian ia dilakukan.
Tidak ada yang lebih baris kod dalam utama.
Jadi kerangka utama yang timbul daripada timbunan, dan kami sudah selesai.
>> Dan itulah bagaimana rekursi berfungsi.
Itulah bagaimana bingkai tindanan bekerja.
Mereka panggilan fungsi yang berlaku sebelum ini
hanyalah pada jeda, menunggu untuk panggilan seterusnya
untuk menyelesaikan supaya mereka boleh menjadi aktif merangka dan menyelesaikan apa yang mereka perlu lakukan.
>> Saya Doug Lloyd.
Ini adalah CS50.