Ruby 左递归 vs 右递归

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 选择了左）？

- ndnenkov

---

似乎 Ruby 在乘法运算时会先计算右侧，因此左侧版本使用了尾递归，这样就不必添加到堆栈中。 - clcto

@clcto：这看起来不像尾调用消除。首先，乘法是函数中的最后一个操作，而不是递归调用。另外，如果你只是将数字增加到9500，仍然会导致堆栈溢出。 - Chuck

@clcto Ruby 绝对是从左到右评估操作数和方法参数，而不是从右到左。此外，操作数的评估顺序与是否尾递归无关。乘法必须在函数调用之后发生（因为在知道两个数字之前无法相乘），因此无论哪个数字首先被评估，该方法都不是尾递归。而且无论如何，标准的Ruby解释器都不会优化尾递归。 - sepp2k

Answer 1

好的，我虽然不是任何类型的YARV黑客，但我会尽力解释一下它们之间的区别。当您调用一个方法时，发件人将该方法的参数推入堆栈，然后被调用的方法弹出其参数并将其返回值推入堆栈。使用递归调用时，number参数还没有被推入堆栈，因此每个调用的堆栈占用的空间略小。这就是为什么您可以在该版本中获得更多迭代次数的原因，但并不是显著地多 - 您正在查看堆栈使用减少了几个百分点。

- Chuck

---

这很有道理，但我希望得到更详细的答案。例如，为什么Python和PHP似乎漠不关心，而JS表现出类似的行为。 - ndnenkov

@ndn：这高度依赖于语言实现。例如，Python有一个递归限制，这是解释器检查并拒绝递归调用的实际值。您可以使用sys.setrecursionlimit()更改它。在PHP的情况下，我不得不去获取反汇编器，因为我不知道它是如何工作的。它不采用推送参数然后调用乘法的堆栈机方法。相反，它将操作数作为MUL操作码的操作数提供给*，因此函数之间唯一的区别是MUL !0, $2与MUL $2, !0。 - Chuck