Doug LLOYD: Jika Anda pernah melihat video di rekursi, seluruh proses mungkin memiliki tampak sedikit ajaib. Bagaimana cara kerjanya? Bagaimana fungsi tahu bahwa mereka harus menunggu dan menunggu untuk nilai lain untuk kembali dari fungsi yang berbeda panggilan untuk mendapatkan hasil yang kita inginkan? Nah, alasan ini bekerja karena dari sesuatu yang dikenal sebagai panggilan stack. Ketika Anda memanggil fungsi, yang Sistem menyisihkan ruang di memori untuk fungsi yang melakukan pekerjaannya. Dan kita sebut potongan ini memori yang sedang disisihkan untuk setiap fungsi sebut stack frame atau bingkai fungsi. Dan seperti yang Anda harapkan, tumpukan frame ini hidup di tumpukan bagian dari memori. 

Lebih dari satu fungsi stack frame bisa ada di memori pada waktu tertentu. Jika utama panggilan langkah fungsi, dan bergerak panggilan arah, semua tiga fungsi memiliki frame terbuka. Tapi mereka tidak semua memiliki frame yang aktif. Frame ini disusun dalam tumpukan. Dan frame dari yang terakhir disebut Fungsi selalu di atas tumpukan. Dan yang selalu frame aktif. Hanya ada benar-benar pernah satu Fungsi yang aktif pada suatu waktu. Ini adalah salah satu di atas tumpukan. 

Ketika fungsi panggilan lain fungsi, itu semacam menekan jeda. Hal semacam ini ditahan, menunggu. Dan stack frame lain didorong ke tumpukan di atasnya. Dan yang menjadi frame yang aktif. Dan frame segera bawah perlu menunggu sampai lagi frame aktif sebelum dapat melanjutkan pekerjaannya. Ketika fungsi adalah lengkap dan itu dilakukan, frame yang muncul dari tumpukan. Itu terminologi. Dan frame segera bawahnya, karena saya hanya berkata, menjadi frame yang aktif baru. 

Dan jika panggilan fungsi lain, itu akan berhenti lagi. Bahwa fungsi baru stack frame akan didorong ke atas tumpukan. Ini akan melakukan tugasnya. Mungkin pop kembali off. Dan fungsi lainnya bawah itu dapat melanjutkan lagi. 

Jadi mari kita pergi melalui ini lagi, mencari pada gagasan fungsi faktorial bahwa kita ditetapkan dalam rekursi Video untuk melihat persis bagaimana keajaiban di balik ini Proses rekursif berlangsung. Jadi ini adalah seluruh file kita, kan? Kami mendefinisikan dua functions-- utama dan fakta. Dan seperti yang kita harapkan, program C akan untuk memulai pada baris pertama utama. 

Jadi kita membuat stack frame baru untuk utama. Dan itu akan mulai berjalan. Panggilan utama printf. Dan printf akan mencetak faktorial dari 5. Yah, itu tidak tahu apa faktorial dari 5 adalah, dan panggilan ini sudah tergantung pada panggilan fungsi lain. Jadi utama akan berhenti di sana. Aku akan meninggalkan nya panah di sana, warna itu warna yang sama sebagai tumpukan bingkai di sebelah kanan, untuk menunjukkan bahwa utama akan membekukan di sini sementara faktorial dari 5 disebut. 

Jadi faktorial dari 5 disebut. Dan itu akan mulai sangat mulai dari fungsi faktorial. Ini meminta pertanyaan saya sama dengan 1? Apakah 5 sama dengan 1? Nah, tidak ada. Jadi itu akan pergi ke yang lain bagian, kembali n kali faktorial dari n minus 1. Baiklah. 

Jadi sekarang, faktorial 5 adalah tergantung pada panggilan lain untuk faktorial, melewati di 4 sebagai parameter. Dan faktorial dari 5 bingkai, frame merah, akan membekukan di sana pada baris yang saya ditunjukkan dan menunggu faktorial 4 untuk menyelesaikan apa yang perlu dilakukan agar kemudian dapat menjadi frame aktif kembali. 

Jadi faktorial dari 4 dimulai pada awal faktorial. Adalah 4 sama dengan 1? Tidak ada, jadi itu akan melakukan hal yang sama. Ini akan turun cabang lain. Ini akan mendapatkan bahwa baris kode. OK, aku akan kembali empat kali. Oh, faktorial 3-- sehingga faktorial dari 4 tergantung pada faktorial dari 3 finishing. 

Dan sehingga perlu untuk memanggil faktorial dari 3. Dan itu akan pergi melalui proses yang sama lagi. Dimulai melalui, tiba di sini. Faktorial 3 tergantung pada faktorial 1. Jadi faktorial 2 dimulai, tiba di sini. Hal ini tergantung pada faktorial dari 1. Faktorial 1 dimulai. 

OKE. Jadi sekarang, kita sudah suatu tempat yang menarik, bukan? Jadi sekarang, 1 sama dengan 1. Dan jadi kami kembali 1. Pada titik ini, kami akan kembali. Fungsi dilakukan. Ini perilaku is-- ada tidak ada yang lain untuk itu harus dilakukan, dan stack frame untuk faktorial 1 muncul dari. Selesai. Itu kembali 1. Dan sekarang, faktorial 2, yang adalah frame segera bawahnya dalam tumpukan, menjadi frame yang aktif. 

Dan dapat mengambil persis di mana ia tinggalkan. Sudah menunggu faktorial dari 1 untuk menyelesaikan pekerjaannya. Kini telah selesai. Dan jadi di sini kita. 

Faktorial 1 kembali nilai 1. Jadi faktorial 2 kaleng katakanlah kembali 2 kali 1. Pekerjaannya sekarang dilakukan. Ini kembali ke faktorial 2 dari 3, yang sedang menunggu untuk itu. Faktorial 3 sekarang frame atas, frame aktif dalam stack. Dan ia mengatakan, OK, baik, aku akan untuk kembali 3 kali 2, yang adalah 6. Dan aku akan memberikan yang menghargai kembali ke faktorial 4, yang telah menunggu saya. Saya selesai. Faktorial 3 muncul dari tumpukan, dan faktorial 4 sekarang frame aktif. 

4 mengatakan, OK, aku akan kembali 4 kali faktorial dari 3, yang enam. Itu nilai yang faktorial 3 kembali. Dan 4 kali 6 adalah 24. Dan aku akan lulus yang kembali ke faktorial dari 5, yang telah menunggu saya. Faktorial dari 5 sekarang frame aktif. Ini akan kembali 5 kali faktorial 4-- 5 kali 24, atau 120-- dan memberikan nilai yang kembali ke utama, yang memiliki telah menunggu sangat sabar untuk lama di bagian bawah tumpukan. 

Ini di mana ia mulai. Hal itu membuat panggilan ini. Beberapa frame mengambil alih di bagian atas. Sekarang kembali di atas tumpukan. Ini frame yang aktif. Jadi utama mendapat nilai 120 kembali dari faktorial 5. Sudah menunggu untuk mencetak nilai tersebut. Dan kemudian hal itu dilakukan. Tidak ada garis yang lebih kode di utama. Jadi bingkai utama muncul dari stack, dan kami sudah selesai. 

Dan itulah cara rekursi bekerja. Begitulah cara tumpukan frame bekerja. Mereka fungsi panggilan yang terjadi sebelumnya hanya pada jeda, menunggu untuk panggilan berikutnya untuk menyelesaikan sehingga mereka dapat menjadi aktif bingkai dan menyelesaikan apa yang harus mereka lakukan. 

Aku Doug Lloyd. Ini adalah CS50.