理解斐波那契數列

-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

理解斐波那契數列

回答

相關問題