了解斐波那契数列 [英] Understanding the Fibonacci sequence

问题描述

我有一个在线发现的算法，可以计算斐波那契数列.我有点像个傻瓜，但我不知道它是如何工作的！

I have an algorithm that I found online that calculates the Fibonacci sequence. I feel a bit like a fool but I have no idea how it works!

 def fib(n)

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

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

如果我使用参数10调用该方法，为什么它不返回18?我认为这里正在进行递归，但我不知道.有人可以帮我理解吗?

If I call the method with the argument of 10 why does it not return 18? I assume some recursion is happening here but I have no idea. Can someone help me understand this?

推荐答案

根据上面的代码，让我们看一下fib(4):

Let's look at fib(4), according to your code above:

fib(4) #=> 3

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

It does so by using the following results:

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

粗略地说，您的方法以下列方式使用上述结果 (注意:下面我使用数学符号(不是代码)和一些可疑的空格来说明用上面的结果替换了哪些位):

Crudely speaking your method uses the above results in the following fashion (note: below I am using math-notation (not code) and some dubious spacing to illustrate which bits are being substituted with the results from above):

# 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)相似，尽管它非常麻烦，但几乎不值得手动进行.只要您掌握了基本思想，就继续前进.顺便说一下，您不是傻瓜，您只是想在某些人要做的事情上变得更好.祝你好运.

Your algorithm goes through the above steps. Similarly for fib(10), although it's hardly worth going through it manually as it can be quite cumbersome. As long as you get the basic idea, move on. And by the way you're not a fool, you're just trying to get better at something which is what many of us are trying to do as well. Good luck.

这篇关于了解斐波那契数列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！