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参数尚未被压入堆栈,因此每个调用的堆栈占用的空间略小.这就是为什么你可以从该版本中获得更多的迭代,但不是更多 - 你正在考虑减少几个百分点的堆栈使用.