Ruby 左递归与右递归

Question

出于某种原因，Ruby 在面对左递归时似乎表现得更好。例如:

def left_recursive_factorial(number)
  return 1 if number.zero?
  left_recursive_factorial(number.pred) * number
end

def right_recursive_factorial(number)
  return 1 if number.zero?
  number * right_recursive_factorial(number.pred)
end

当我用超过 9000 (😉) 的值调用这些方法时，我得到不同的结果:

left_recursive_factorial(9001)
  # => factorial of 9001

right_recursive_factorial(9001)
  # => SystemStackError: stack level too deep
  #    from (pry):6:in `right_recursive_factorial'

我找不到对此行为的任何解释。

唯一似乎有点相关的是 LL() 解析器在左递归方面有问题，我想你可以翻转它，但我没有深入研究它。

有人可以更详细地解释一下是什么导致左递归和右递归执行不同(通常和在 Ruby 中)，如果你有可能选择一个或另一个，你为什么会选择它(以及为什么选择左递归)在 Ruby 中)？

Answer 1

好吧，我不是任何类型的 YARV 黑客，但这是我理解的区别。当您调用一个方法时，发送方将方法的参数压入堆栈，然后被调用的方法将其参数弹出并压入其返回值。第一次递归调用时，number 参数还没有被压入堆栈，所以每次调用的堆栈占用的空间稍微少一些。这就是为什么您可以从该版本中获得更多迭代，但不会更多 — 您正在寻找堆栈使用量减少几个百分点的原因。