這段代碼爲什麼會導致堆棧溢出？

Question

以下將導致大型'n'堆棧溢出，我可以理解爲什麼。

def factorial(n) 
    (n > 1) ? (return (n * factorial(n - 1))) : (return 1) 
end 

爲什麼以下原因溢出呢？

def factorial(n, k) 
    (n > 1) ? (return factorial(n - 1, lambda {|v| return k.call(v * n)})) : (return k.call(1)) 
end 

Answer 1

你的第二種算法創建了一個長的lambda程序鏈，每個鏈都包含對前一個程序的引用。我不確切知道Ruby是做什麼的，但是用適當的尾遞歸語言，堆棧不會在第二種算法中溢出，因爲lambda中的k.call也處於尾部位置。如果像Brian的實驗所表明的那樣，Ruby沒有正確的尾部調用，即使Ruby的頭部足夠聰明以轉換尾部，當鏈的頭部被調用時，對Lambda嵌套調用的長鏈會溢出堆棧-recursive factorial調用循環（=尾部調用優化）。

Answer 2

如在第一個函數，遞歸調用可以最終被太多的系統來處理。

Answer 3

在大多數語言中，函數調用進入調用堆棧，這實際上只是堆棧。以遞歸方式調用函數會繼續添加到調用堆棧。最終你填滿堆棧，並且你得到堆棧溢出。在遞歸級別很深的情況下運行遞歸函數時，這總是很危險。

Answer 4

出於同樣的原因，第一個堆棧溢出...調用堆棧太大。