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

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-long链的lambda过程,每个过程包含对前一个的引用.我不确切知道Ruby的作用,但是在正确的尾递归语言中,堆栈不会在第二个算法中溢出,因为k.calllambda也处于尾部位置.如果正如Brian的实验所暗示的那样,Ruby没有正确的尾调用,那么n当调用链的头部时,对lambda的嵌套调用的长链将溢出堆栈,即使Ruby足够聪明以转换尾部 -递归factorial调用循环(=尾调用优化).