为什么将1添加到递归的proc调用中会返回调用的计数？

Question

假设我有以下代码：

def rcall(num)
  return 0 if 10 == num
  1 + rcall(num - 1)
end

p rcall(90) # => 80

这段代码的返回值总是比传递给num的值少10个，即递归调用的计数。

我看不出它是怎么工作的。我有一个模糊的理解，如果满足退出条件，我们返回零，以避免再次增加计数器。但是，确切地说，在proc调用中添加一个调用是如何增加调用次数的？我看不出增量器是在哪里累积的。

而且，这是一种特定于Ruby体系结构的技术，还是更普遍地适用？我在询问如何计算递归调用的问题的任何回答中都没有提到它；似乎大多数时候人们都会传递一个计数器变量来跟踪计数。

Answer 1

我只是在您的代码中添加了一些puts，也许它有助于更好地遵循逻辑，而不是用我的英语来解释。

因此，这是经过修改的代码：

def rcall(num)
  if 10 == num
    rec = 0
    puts "rec = #{rec} ---- End of recursion"
    return rec
  end
  rec = rcall(num - 1)
  res = 1 + rec
  puts "rec = #{rec} \t\t res = i + rec = #{res}"
  res
end

例如，当您调用15时，您得到: rcall(15)

# rec = 0 ---- End of recursion
# rec = 0      res = i + rec = 1
# rec = 1      res = i + rec = 2
# rec = 2      res = i + rec = 3
# rec = 3      res = i + rec = 4
# rec = 4      res = i + rec = 5
# 5

如果调用小于10的数字，则永远不会到达递归的末尾，因此不返回值来构建“调用堆栈”，并引发错误：stack level too deep (SystemStackError)

其他语言支持递归，例如Python。这里是著名的斐波纳契(How to write the Fibonacci Sequence?)。

​

我还想分享一下这个亲计算机视频关于YouTube：https://youtu.be/Mv9NEXX1VHc上的递归

Answer 2

假设您将基本条件更改为return 0 if num.zero?，然后使用参数3调用它，如下所示：

1 + rcall(2)
    # => 1 + rcall(1)
             # => 1 + rcall(0)
                      # => 0

如果将rcall调用替换为它们的结果(从底部开始)，则会出现在1 + 1 + 1 + 0中。

换句话说，通过从大小写向上移动，您可以更容易地理解它：

rcall(0)
# 0

rcall(1)
# the same as 1 + rcall(0), which is one

rcall(2)
# the same as 1 + rcall(1), which is two.

希望你能看到模式。

正如注释中提到的，您可以这样优化它：

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

def rcall(num, sum=0)
  return sum if 10 == num
  rcall(num - 1, sum + 1)
end

虽然这可能需要一些其他设置，但我不太确定。

请参阅What Is Tail Call Optimization?

Answer 3

递归是很多人都知道的事情之一，但并不是很多人都能描述它的价值(包括我自己)。它是几种语言支持的通用编程方法，而不仅仅是Ruby。

任何给定的调用都会在再次调用该方法时保存其当前状态，因为该方法需要一个值才能继续。只有当最深级别返回一个值(在本例中为0)时，整个事件才会解除包装，因为以前的调用现在有了要处理的值(每次添加1)。因为您使用10作为“完成”值，所以您得到了10，实际上跳过了任何比保护比较更小的值(例如，将比较设置为0或负数)。

在这种情况下，保护测试避免了“堆栈级别太深”的错误，因为没有任何东西可以防止失控的递归--您可以通过使用小于比较的初始值来看到这一点，例如，当比较为10时，从5开始。