斐波那契（n）的這種實現是如何工作的？ [遞歸]

即使世界的運動從一個Java書我讀已我困惑：斐波那契（n）的這種實現是如何工作的？ [遞歸]

斐波納契數列是數字1，1，2，3，5，8，13 的序列， 21,34等，其中每個數字（從第三個開始）是前兩個的總和。創建一個將整數作爲參數的方法，並顯示從開始開始的許多斐波那契數字。如果，例如，你運行java斐波納契5（其中斐波那契是類的名稱），輸出將是：1，1，2，3，5

我可以發誓，這將需要一個陣列或存儲先前數的一些方式，但是當我看到答案是不是這樣的：

import java.util.*; 

public class Fibonacci { 

    static int fib(int n) { 
     if (n <= 2) 
       return 1; 

     return fib(n-1) + fib(n-2); 
    } 
    public static void main(String[] args) { 
    // Get the max value from the command line: 
    int n = Integer.parseInt(args[0]); 
    if(n < 0) { 
     System.out.println("Cannot use negative numbers"); return; 
    } 
    for(int i = 1; i <= n; i++) 
     System.out.print(fib(i) + ", "); 
    } 
}

會有人能夠解釋如何使用函數中自身產生的？

來源

2011-10-25 iRector

指算法使用中本身就是一個函數被調用'recursion' – Marcus

瞭解遞歸的最好方法是瞭解遞歸。 –

學習遞歸的最好方法就是做到這一點，而不是考慮花哨的名字。試想一下，你是編譯器/虛擬機，並且正在運行該程序。感受堆棧的存在。達到禪宗。 – sehe

您提供的代碼是recursive解決方案的示例。當函數第一次被調用時，它會執行直到它自己調用。其狀態存儲在堆棧中，並且代碼將再次使用新的輸入數據執行。這個過程重複，直到輸入小於2，在此點返回1，並且答案返回到前一個調用者。

例如，調用下面的執行FIB（5）結果：

fib(5): 
    fib(4): 
     fib(3): 
      fib(2): 1 
      fib(1): 1 
     fib(2): 1 
    fib(3): 
     fib(2): 1 
     fib(1): 1

需要注意的是部分正確。中間結果存儲在此解決方案的stack中。這是遞歸解決方案如此昂貴的原因之一。另一種是其複雜性。但是，如果可以迭代計算Fibonacci(n)並且不存儲全部先前的結果。所有你真正需要的是將最後的結果存儲起來，並從1到n。

來源

2011-10-25 20:11:36 ObscureRobot

沒有必要因爲他比以前的帖子慢30秒而投票給他！ +1 順便說一句：也許把標題改爲更有意義的東西，比如「理解斐波那契數列」並不是一個壞主意。 – mweisz

這是一個遞歸解決方案。遞歸函數調用自己直到滿足給定的停止條件。然後每個呼叫都會退出，直到只有第一個呼叫保持。第一次調用輸出結果。

在您的解決方案，爲停止條件：

if (n <= 2) 
      return 1;

，直到這一條件得到滿足，這個功能使自身的連續通話。每次調用都會減少作爲參數傳遞的int值。當它達到2時，停止條件表明函數返回值1（在斐波納契（n）中n = 1且n = 2的結果）。

由於斐波納契是最後兩個數字的總和，函數的遞歸部分，

return fib(n-1) + fib(n-2);

確實n-1和N-2的和（如我說，最後兩個數字的序列）。當n等於2時，這些調用函數fib將最終得到一個值，並將返回。例如，如果n = 3，遞歸部分將調用fib（2）和fib（1），兩者都等於或小於2，因此兩個調用都將返回1.因此，printf將打印1,1,1， 2。 2是1 + 1的總和（我知道這很明顯，但有時會說明明顯的幫助）。

來源

2011-10-25 20:12:49

這是recursive function的標準示例。

Fibonacci Numbers也被聲明爲遞歸。

fib(1)和fib(2)都被聲明爲1.所有其他的都是通過加上最後兩個斐波納契數來計算的，所以fib(3)=fib(2)+fib(1)。

比較這其中正是這樣做的計算方法：

static int fib(int n) { 
    if (n <= 2) 
      return 1; 

    return fib(n-1) + fib(n-2); 
}

順便說一句，這是計算Fibonacci數非常緩慢的方式，使用兩個變量（你並不需要所有的人對於最後一個，只有最後兩個！）和一個循環在O（n）中，上面的遞歸函數有O（2^n）個操作。

來源

2011-10-25 20:18:12

當然是。糟糕的錯字。 –

      F(n) 
          / \ 
         F(n-1) F(n-2) 
         / \ / \ 
        F(n-2) F(n-3) F(n-3) F(n-4) 
       / \ 
       F(n-3) F(n-4)

要注意的重要一點是，該算法是指數因爲它不存儲以前計算的數字的結果。例如F（n-3）被稱爲3次。

有關詳細信息通過達斯古普塔章0.2

來源

2014-03-04 07:41:44

斐波那契（n）的這種實現是如何工作的？ [遞歸]

回答

相關問題