道格·勞埃德:如果你看過 視頻上的遞歸, 整個過程可能 似乎有點不可思議。 它是如何工作的? 如何職能知道他們 需要等待,等待另一個值 從不同的功能回歸 為了得到我們想要的結果打電話? 好了,這個工作的原因是因為 對一些被稱為調用堆棧。 當你調用一個函數時, 系統留出內存空間 該函數來完成其工作。 我們呼籲內存這些塊的 被預留給每個功能 調用堆棧幀或功能框架。 正如你所期望的, 這些堆棧幀 住在內存堆棧的一部分。 多個函數棧幀 可以在內存在給定時間存在。 如果主調用一個函數的舉動, 與移動電話的方向, 所有這三個功能都開放框架。 但他們並不都具有積極的框架。 這些幀被佈置成堆疊。 而從框架 最近被稱為 功能總是在堆棧的頂部。 這始終是有效的框架。 這裡只有真正過1 功能處於活動狀態的時間。 這是一個在堆棧的頂部。 當一個函數調用另一個 功能,它的排序按暫停。 排序是待命,等待著。 而另一個堆棧幀被壓 入堆棧在它的上面。 而這將成為活動框架。 和框架立即 下面需要等待 直到它再次活動框架 才可以恢復工作。 當一個功能是 完整,它的完成, 其框架被彈出堆棧。 這就是術語。 和框架立即 在它下面,正如我剛才所說, 成為新的活動框架。 而如果它調用另一個函數, 這將再次暫停。 這個新功能的堆棧幀會 被壓入堆棧的頂部。 它會做的工作。 它可能彈回了。 和其它功能 下面就可以再次恢復。 因此,讓我們通過這一次,看 在階乘函數的想法 我們在定義 遞歸視頻看 究竟這背後的魔力 遞歸過程正在發生。 所以,這是我們整個文件,對不對? 我們定義了兩個 functions--主的事實。 正如我們所預期的, 任何C程序是怎麼回事 處開始的主要的第一行。 因此,我們創造主一個新的堆棧幀。 而且它會開始運行。 主要調用printf。 和printf是要 打印出的5階乘。 那麼,它不知道 什麼階乘5, 因此這個調用已 根據另一個函數調用。 所以主要是要暫停在那裡。 我要離開了 箭頭在那裡,顏色 它的顏色相同的 堆在右邊框, 以指示主要是要凍結 在這裡而5階乘被調用。 所以階乘5被調用。 而且它會啟動在最 開始階乘函數。 它問這個問題我會等於1? 是5等於1? 哦,不。 因此,它會下去 else部分,返回n倍 階乘ñ減1。 嗯,好吧。 所以,現在的5階乘是 根據另一個電話 到階乘,傳遞 在4作為參數。 所以的階乘 5架,即紅色邊框, 會凍結在那裡 在該行我已經指示 和等待的4因子,完成 它所需要做的,這樣則 可以再次成為活動框架。 因此,在階乘4開始 的階乘的開始。 為4等於1? 沒有,所以它會做同樣的事情。 這將下井else分支。 它會得到該行的代碼。 好了,我要回四倍。 呵呵,3--階乘所以階乘 4取決於3整理因子。 所以它需要調用的3因子。 這就是要通過 再次同樣的過程。 它開始通過,送過來。 3階乘依賴 在1階乘。 所以階乘2開始,送過來。 這取決於1階乘。 階乘的1開始。 確定。 所以,現在,我們正在 有趣的地方,對不對? 所以,現在,1等於1。 因此,我們返回1。 在這一點上,我們正​​在返回。 該函數的實現。 它的行為is--有 閒來無事為它做, 因此對於堆棧幀 1階乘彈出關閉。 它的完成。 它返回1。 而現在,2階乘,這 立即低於它的幀 在棧,成為活動框架。 它可以拿起 正是離開的地方。 它一直在等待一個階乘 1完成其工作。 如今,它已完成。 所以,我們在這裡。 1階乘返回值1。 所以階乘的2個CAN 說回2次1。 它的工作現在已經完成。 它返回2階乘 3,這是等著呢。 的3因子是現在頂框, 活動幀在堆棧中。 所以它說,好了,好了,我要去 返回3次2,這是6。 而我要去給那個 值回階乘 4,已在等著我。 我完成了。 3的階乘離開本層,並 4階乘是現在的活動框架。 4說,OK,我要回到4倍 3階乘,這是六。 這是值 3階乘返回。 所以,4次6是24。 而我要通過 這回階乘 5,已經在等著我。 5階乘現在是活動框架。 這將返回5倍 的4-- 5次24,或120--階乘 並給予該值 回到主,它具有 一直在等待很耐心的 長時間在堆棧的底部。 這就是它開始。 這讓這一呼籲。 幾幀接手頂部。 現在是回到了堆棧的頂部。 這是活動框架。 因此,主要得到了價值120 回從5階乘。 它一直在等待 打印出該值。 然後,它的完成。 有沒有主多行代碼。 因此,主要的彈出框關閉 堆棧,我們就大功告成了。 這就是遞歸如何工作的。 這是堆棧幀是如何工作的。 這些函數調用 以前發生 只是在暫停,等待 為隨後的呼叫 完成,這樣他們可以成為活動 框架和拋光他們需要做的。 我是道格·勞埃德。 這是CS50。