理解斐波那契数列

Question

我在网上找到了一个计算斐波那契数列的算法。我觉得有点像个傻瓜，但我不知道它是如何工作的！

 def fib(n)

  if n == 0 || n == 1
   return n
  end

  if n >= 2
    return fib(n-1) + fib(n-2)
  end
 end

如果我用参数 10 调用方法，为什么它不 return 18？我假设这里发生了一些递归，但我不知道。有人可以帮我理解吗？

Answer 1

让我们看看fib(4)，根据你上面的代码：

fib(4) #=> 3

它通过使用以下结果来做到这一点：

fib(4) #calculates fib(3) + fib(2)
fib(3) #calculates fib(2) + fib(1)
fib(2) #calculates fib(1) + fib(0)
fib(1) #returns 1
fib(0) #returns 0

粗略地说，您的方法以下列方式使用上述结果（注意：下面我使用数学符号（不是代码） 和一些可疑的间距来说明哪些位被上面的结果替换）：

# fib(4) =   fib(3)                       +  fib(2)
#        = ( fib(2)            + fib(1))  + (fib(1) + fib(0))
#        = ((fib(1) + fib(0))  + 1     )  + (1      + 0     )
#        = ((1      + 0     )  + 1     )  +  1
#        = ( 1                 + 1     )  +  1
#        =   2                            +  1
#        =   3

您的算法经过了上述步骤。对于 fib(10) 也是类似的，尽管手动检查它几乎不值得，因为它可能非常麻烦。只要您了解基本概念，就可以继续。顺便说一句，你不是傻子，你只是想在某件事上做得更好，这也是我们许多人都在努力做的事情。祝你好运。

理解斐波那契数列

Understanding the Fibonacci sequence

ruby

fibonacci