計劃和調用堆棧遞歸

我是一名大學生，攻讀球拍/計劃和C爲我的CS學位課程的入門課程。計劃和調用堆棧遞歸

我已經在網上看了，它是使用迭代而不是遞歸在C，因爲遞歸是昂貴的，因爲節省堆棧幀到調用堆棧等一般的最佳實踐...

現在像Scheme函數式語言，遞歸總是被使用。我知道尾遞歸在Scheme中是一個巨大的好處，並且根據我的理解，它只需要一個堆棧幀（任何人都可以澄清這一點），無論遞歸有多深。

我的問題是：那麼非尾遞歸呢？每個函數應用程序是否都保存在callstack上？如果我可以簡要概述這是如何工作的，或者將我指向某個資源，我將不勝感激;我似乎無法找到明確說明這一點的任何地方。

2014-01-24 Anthony Calandra

計劃要求淘汰尾數。不是tail調用遞歸的代碼將需要額外的堆棧框架。

讓我們假設javascript支持尾部調用優化，這些函數定義中的第二個將僅使用1個堆棧幀，而第一個由於+將需要額外的堆棧幀。

function sum(n) { 
    if (n === 0) 
     return n; 
    return n + sum(n - 1); 
} 

function sum(n) { 
    function doSum(total, n) { 
    if (n === 0) 
     return total; 
    return doSum(total + n, n - 1); 
    } 
    return doSum(0, n); 
}

許多遞歸函數可以尾調用優化通過把計算的結果在棧上

概念調用的第一個定義這個樣子的

 
3 + sum(2) 
3 + sum(2) = 3 + 2 + sum(1) 
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) 
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 3 + 2 + 1 + 0 
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 6 
3 + sum(2) = 3 + 2 + sum(1) = 6 
3 + sum(2) = 6 
6

調用的寫入第二個定義看起來像這樣

 
sum(3, sum(2)) = sum(5, sum(1)) = sum(6, sum(0)) = 6

來源

2014-01-24 00:30:06 Bhaskar

當你說：「雖然第一個，由於+需要一個額外的堆棧框架」在任何時候只有一個額外的堆棧框架？ C爲每個函數調用添加了一個新的堆棧框架，我相信這樣做是否意味着Scheme中的遞歸更有效？如果我錯過了什麼，請告訴我;這只是一個奇怪的想法，我不能在明年之前採取任何深入的課程。謝謝你的方式真棒回答。 –

尾部調用優化是編譯器的魔力。 Scheme標準要求編譯器實現它。使用跳轉指令而不是呼叫實現尾部呼叫優化。尾調用優化遞歸因此更有效。 – Bhaskar

啊，所以如果沒有尾遞歸（例如在第一個函數中），那麼Scheme中遞歸的效率在C中是相同的？ –

是的，處於非尾部位置的呼叫需要向堆棧添加內容，以便在呼叫返回時知道如何恢復工作。（關於堆棧，尾部調用和非尾部調用的更全面的解釋，請參閱Steele的文章揭示'昂貴的過程調用'的神話或程序調用被認爲有害的實現或Lambda：The Ultimate GOTOlambda papers page at readscheme.org。）

但是Racket（以及其他許多Schemes和一些其他語言）實現了「堆棧」，因此即使您有深度遞歸，也不會用完堆棧空間。換句話說，Racket沒有堆棧溢出。其中一個原因是用於支持深度遞歸的技術與支持一級延續的技術一致，這是Scheme標準所要求的。您可以在Clinger等人的Implementation Strategies for First-Class Continuations中閱讀它們。

來源

2014-01-24 03:54:48

我不知道球拍不能堆棧溢出......謝謝！我將閱讀你本週末提供的一些論文。 –

計劃和調用堆棧遞歸

回答

相關問題