这段代码为什么会导致堆栈溢出？

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

出于同样的原因，第一个堆栈溢出...调用堆栈太大。