ruby - 斐波那契数列递归的解释

Question

我找到了一个代码来确定一个数字是否是斐波那契数列。我希望有人能够更容易地分解它。

def is_fibonacci?(i, current = 1, before = 0)  
  return true if current == i || i == 0
  return false if current > i
  is_fibonacci?(i, current + before, current)
end

is_fibonacci?(3) # => true
is_fibonacci?(4) # => false

我知道一个方法在递归中调用自身并且需要有一个基本情况，但同样，我很难想象正在发生的事情。任何帮助将不胜感激。

Answer 1

最简单的可视化方法是一次通过一个方法调用逐步计算，假设我们想要评估 is_fibonacci?(8) , 然后 ruby​​ 会设置 current = 1, before = 0因为我没有覆盖默认值。

然后，自 i不是 0 或 8，它必须递归，所以会发生以下方法调用:

is_fibonacci?(8, 1, 1)
is_fibonacci?(8, 2, 1)
is_fibonacci?(8, 3, 2)
is_fibonacci?(8, 5, 3)
is_fibonacci?(8, 8, 5)

最后，is_fibonacci?(8, 8, 5)可以自 i == current (8 == 8) 后终止, 所以它返回 true。

编辑:考虑此递归的另一种方法是您的 current和 before参数正在“重建”斐波那契数列，如果它们达到 i , 那么答案是正确的，但如果他们超过了 i , 这是假的。