理解斐波那契数列

-1

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

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？我假设在这里发生了一些递归，但我不知道。有人能帮助我理解这一点吗？

来源

2016-07-26 Bitwise

当你用10调用它时它会返回什么？你为什么要18？第十个斐波那契数是55. – Thilo

是的，它是递归。 [here]（http://www.theodinproject.com/ruby-programming/recursion）是一个很好的教程，其中涵盖了递归斐波纳契 –

也许是因为18不是斐波那契数？？您发布的代码似乎是正确的。 – axiac

让我们来看看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)也是如此，尽管手动操作几乎不值得，因为它可能非常麻烦。只要你有了基本的想法，继续前进。顺便说一下，你不是一个傻瓜，你只是想尝试改善我们许多人都想做的事情。祝你好运。

来源

2016-07-26 06:09:16

理解斐波那契数列

回答

相关问题