Ruby 中的递归斐波那契

Question

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

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

return array if num == 2

如果我推送到数组，它不起作用，如果我创建一个新的变量序列并推送到它，它 return 是正确的答案。我对此很满意，但我的基本情况是 return 数组，而不是序列。我最初将序列推入数组，结果不是 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 是非法的，应该通过错误检查来处理。

我还明确添加了 return。明确的 returns 使得正在 returned 的内容非常明显，这有助于理解递归。在本例中为 seq。（“明确的 return 是邪恶的！”所有 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]，因为在第一个 return 之后，堆栈必须展开。

让我们来看看 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 return 从 fib_seq(2) 编辑为 [0,1]。它在末尾添加 seq[-2] + seq[-1] 和 returns [0,1,1].

fib_seq(4) 从中断处继续。 seq return 从 fib_seq(3) 编辑为 [0,1,1]。它在末尾添加 seq[-2] + seq[-1] 和 returns [0,1,1,2].

堆栈已展开，所以我们返回 [0,1,1,2]。

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

Answer 2

递归函数需要有一个退出条件以防止它们永远运行。您的递归方法的主要部分如下：

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

在Ruby中，方法的最后一个表达式被认为是该方法的return值，所以上面的行等同于：

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

让我们运行记下如果方法只包含这两行会发生什么，num = 4:

call fib_seq(4)
  call fib_seq(3)
    call fib_seq(2)
      call fib_seq(1)
        call fib_seq(0)
          call fib_seq(-1)
            ...

显然这会导致无限循环，因为我们没有退出条件。我们总是在第一行再次调用 fib_seq，所以代码不可能到达最后的 return 语句。为了解决这个问题，让我们在开头添加这两行：

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

这些可以简化为：

return [0, 1] if num <= 2

现在让我们看看当我们用 num = 4:

调用方法时会发生什么

call fib_seq(4)
  4 > 2, exit condition not triggered, calling fib_seq(n - 1)
  call fib_seq(3)
    3 > 2, exit condition not triggered, calling fib_seq(n - 1)
    call fib_seq(2)
    2 == 2, exit condition triggered, returning [0, 1]!
  fib_seq(2) returned with seq = [0, 1]
  add 0 + 1 together, push new value to seq
  seq is now [0, 1, 1]
  return seq
fib_seq(3) returned with seq = [0, 1, 1]
add 1 + 1 together, push new value to seq
seq is now [0, 1, 1, 2]
return seq
FINAL RESULT: [0, 1, 1, 2]

因此看起来此方法适用于 >= 2:

的 num 值

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

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

还有一个错误：num = 0 和 num = 1 都是 return [0, 1]。让我们解决这个问题：

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

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

稍微清理一下：

def fib_seq(num)
  return [0, 1].first(num) if num <= 2
  seq = fib_seq(num - 1)
  seq << seq[-2] + seq[-1]
end

Answer 3

当人们将命令式风格突变与函数式风格递归混合使用时，我总是感到困惑 – 如果您要进行所有重新分配和手动数组查找，为什么还要使用递归作为循环机制呢？只需使用一个循环。

但这并不是说这个程序不能用更函数式的方式来表达。在这里，我们将计算斐波那契数和生成序列的关注点分开——结果是一个非常容易理解的程序

def fib n
  def aux m, a, b
    m == 0 ? a : aux(m - 1, b, a + b)
  end
  aux n, 0, 1
end

def fib_seq n
  (0..n).map &method(:fib)
end

fib_seq 10
#=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

另一种更有效地生成序列的方法 – 下面，我定义了一个辅助函数 aux，它利用 4 个状态变量以相对简单的方式生成序列。

请注意与输入 10 的区别 - 这个更接近您建议的函数，其中 0 returns [] 尽管 the 0^th fibonacci number is actually 0

def fib_seq n
  def aux acc, m, a, b
    m == 0 ? acc << a : aux(acc << a, m - 1, b, a + b)
  end
  case n
    when 0; []
    when 1; [0]
    when 2; [0,1]
    else;   aux [0,1], n - 3, 1, 2
  end
end

fib_seq 10
# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Ruby 中的递归斐波那契

Recursive Fibonacci in Ruby

ruby

recursion

fibonacci