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

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

您的第二个算法创建一个 n 长的 lambda 过程链，每个过程都包含对前一个过程的引用。我不知道 Ruby 到底做了什么，但在适当的尾递归语言中，堆栈不会在你的第二个算法中溢出，因为 lambda 中的 k.call 也处于尾部位置。如果像 Brian 的实验所暗示的那样，Ruby 没有适当的尾调用，那么当调用链的头部时，对 lambda 的 n 嵌套调用链将溢出堆栈，即使 Ruby足够聪明，可以将尾递归 factorial 调用转换为循环(= 尾调用优化)。