ruby - Ruby 中的递归斐波那契数列

Question

这周是我第一次做递归。我能够解决的问题之一是斐波那契数列到第 n 个数字；搞砸了5分钟后并不难。

但是，我无法理解为什么这适用于当前的 return 语句。

return array if num == 2

如果我推送到数组，它不起作用，如果我创建一个新的变量序列并推送到它，它会返回正确的答案。我对此很满意，但我的基本情况是返回数组，而不是序列。我最初将序列插入数组，结果不是 fibs 序列。当我尝试看看如果我插入序列数组会发生什么时，我才解决了这个问题。

我不只是让它工作，我希望有人能够解释幕后发生的事情、堆栈可能是什么以及问题是如何工作的。

我在一定程度上理解递归，并且在某种程度上直观地可以通过假设来使其发挥作用，但我觉得很有趣的是，我实际上不知道其背后的所有原因。

def fib_seq(num)
  return [0] if num == 1
  return [] if num == 0

  array = [0, 1]
  return array if num <= 2 

  seq = fib_seq(num - 1)  
  seq << seq[-2] + seq[-1]
end 

Answer 1

通过删除临时的 array 可以稍微简化代码。多变的。这是一种干扰。它也仅适用于 num == 2 时; num < 2将由其他基本情况处理。 num < 0是非法的，应该通过错误检查来处理。

我还添加了显式返回。显式返回使得返回的内容非常明显，这有助于理解递归。在本例中为 seq 。 (“显式返回是邪恶的!”所有 Ruby 风格的人都哭了。很难受。好的风格不是绝对的。)

def fib_seq(num)
  # Error check
  if num < 0 then
      raise ArgumentError, "The number must be a positive integer"
  end

  # Terminating base cases
  return [] if num == 0
  return [0] if num == 1
  return [0,1] if num == 2 

  # Recursion
  seq = fib_seq(num - 1) 

  # The recursive function
  seq << seq[-2] + seq[-1]

  return seq
end

现在更清楚了 return [0,1] if num == 2是递归的三个基本情况之一。这些是停止递归的终止条件。但处理并没有结束。结果不是[0,1]因为在第一次返回之后堆栈必须展开。

让我们看一下fib_seq(4) .

fib_seq(4) calls fib_seq(3)
fib_seq(3) calls fib_seq(2)
fib_seq(2) returns `[0,1]`

我们已经达到了基本情况，现在我们需要展开调用堆栈。

调用fib_seq(3)从中断处继续。 seq从 fib_seq(2) 返回是 [0,1] 。它添加了 seq[-2] + seq[-1]到最后并返回 [0,1,1] .

fib_seq(4)从中断处继续。 seq从 fib_seq(3) 返回是 [0,1,1] 。它添加了 seq[-2] + seq[-1]到最后并返回 [0,1,1,2] .

堆栈已展开，因此我们返回 [0,1,1,2] .

如您所见，实际计算是向后进行的。 f(n) = f(n-1) + f(n-2)和f(2) = [0,1] 。它递归到 f(2) ，基本情况，然后展开回做 f(3)使用 f(2) 的结果，和f(4)使用 f(3) 的结果等等。