斐波納契功能問題

Question

我計算了斐波那契序列，連同這個代碼迷迷糊糊中，我看到了很多：

int Fibonacci (int x) 
{ 
    if (x<=1) { 
     return 1; 
    } 
    return Fibonacci (x-1)+Fibonacci (x-2); 
} 

什麼我不明白是如何工作的，尤其是返回部分在年底：它是否再次調用斐波那契函數？有人能通過這個功能來引導我嗎？

Answer 1

是的，函數調用自己。例如，

Fibonacci(4) 
= Fibonacci(3) + Fibonacci(2) 
= (Fibonacci(2) + Fibonacci(1)) + (Fibonacci(1) + Fibonacci(0)) 
= ((Fibonacci(1) + Fibonacci(0)) + 1) + (1 + 1) 
= ((1 + 1) + 1) + 2 
= (2 + 1) + 2 
= 3 + 2 
= 5 

請注意，斐波那契函數在這裏被稱爲9次。一般來說，天真的遞歸斐波納契函數有exponential running time，這通常是一件壞事。

Answer 2

這是recursive function的一個經典示例，它是一個調用自身的函數。

如果你仔細閱讀，你會看到，它會調用自身，或者，遞歸，一遍又一遍，直到它到達所謂基本情況，當x <= 1此時它會開始以「回溯」並總結計算出的值。

下面的代碼清楚地打印出該算法的跟蹤：

public class Test { 

    static String indent = ""; 

    public static int fibonacci(int x) { 

     indent += " "; 
     System.out.println(indent + "invoked with " + x); 

     if (x <= 1) { 

      System.out.println(indent + "x = " + x + ", base case reached."); 
      indent = indent.substring(4); 

      return 1; 
     } 

     System.out.println(indent + "Recursing on " + (x-1) + " and " + (x-2)); 
     int retVal = fibonacci(x-1) + fibonacci(x-2); 
     System.out.println(indent + "returning " + retVal); 
     indent = indent.substring(4); 
     return retVal; 

    } 


    public static void main(String... args) { 
     System.out.println("Fibonacci of 3: " + fibonacci(3)); 
    } 
} 

輸出如下：

invoked with 3 
Recursing on 2 and 1 
    invoked with 2 
    Recursing on 1 and 0 
     invoked with 1 
     x = 1, base case reached. 
     invoked with 0 
     x = 0, base case reached. 
    returning 2 
    invoked with 1 
    x = 1, base case reached. 
returning 3 

Fibonacci of 3: 3 

跟蹤的樹的描述看起來像

       fib 4 
       fib 3    +   fib 2 
    fib 2  + fib 1    fib 1 + fib 0 
fib 1 + fib 0   1     1  1 
    1  1 

編寫遞歸函數時需要考慮的重要部分是：

1.照顧底部殼體的

，如果我們忘記了在上面的例子中if (x<=1) return 1;會發生什麼？

2.確保遞歸調用以某種方式對基本情況

，如果我們不小心修改了算法返回fibonacci(x)+fibonacci(x-1);

Answer 3

這是經典的遞歸函數會發生什麼下降。 http://en.wikipedia.org/wiki/Recursive_function應該讓你開始。基本上，如果x小於或等於1，則返回1.否則，它會在每一步中減少運行斐波那契的x。

Answer 4

是的，斐波那契函數再次被調用，這就是所謂的遞歸。

就像你可以調用另一個函數一樣，你可以再次調用相同的函數。由於函數上下文是堆疊的，因此可以調用相同的函數而不干擾當前執行的函數。

請注意，遞歸很難，因爲您可能會無限次地調用同一個函數並填充調用堆棧。這個錯誤被稱爲「堆棧溢出」（這是它！）

Answer 5

在C和大多數其他語言中，允許函數像調用其他函數一樣調用自己。這被稱爲遞歸。

如果看起來很奇怪，因爲它與您要寫的循環不同，那麼您是對的。這不是一個很好的遞歸應用，因爲找到第二個斐波納契數需要兩倍的時間，因爲找到了n -1th，導致運行時間指數在n。

對Fibonacci序列進行迭代，記住先前的斐波那契數，然後再進入下一個斐波那契數，將運行時間改進爲n，它應該是這樣。

遞歸本身並不可怕。事實上，我剛纔所描述的環路（和任何環路）可以被實現爲一個遞歸函數：

int Fibonacci (int x, int a = 1, int p = 0) { 
    if (x == 0) return a; 
    return Fibonacci(x-1, a+p, a); 
} // recursive, but with ideal computational properties 

Answer 6

返回斐波那契（X-1）+斐波那契（X-2）;

這是非常低效的。我建議以下線性替代：

unsigned fibonacci(unsigned n, unsigned a, unsigned b, unsigned c) 
{ 
    return (n == 2) ? c : fibonacci(n - 1, b, c, b + c); 
} 

unsigned fibonacci(unsigned n) 
{ 
    return (n < 2) ? n : fibonacci(n, 0, 1, 1); 
} 

斐波納契序列可以在功能語言中更簡潔地表達。

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci) 

> take 12 fibonacci 
[0,1,1,2,3,5,8,13,21,34,55,89] 

Answer 7

你的問題被標記爲C++，我覺得有必要指出的是，這個功能也可以在編譯時作爲模板實現，你應該有一個編譯時變量在使用它。

template<int N> struct Fibonacci { 
    const static int value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value; 
}; 
template<> struct Fibonacci<1> { 
    const static int value = 1; 
} 
template<> struct Fibonacci<0> { 
    const static int value = 1; 
} 

已經有一段時間，因爲我寫這樣的，所以它可能是一點點，但是這應該是它。

Answer 8

或者如果你想要更快，但使用更多的內存使用這個。

int *fib,n; 
void fibonaci(int n) //find firs n number fibonaci 
{ 
fib= new int[n+1]; 
fib[1] = fib[2] = 1; 
for(int i = 3;i<=n-2;i++) 
    fib[i] = fib[i-1] + fib[i-2]; 
} 

以及用於爲例N = 10，你將有： FIB [1] FIB [2] FIB [3] FIB [4] FIB [5]謊[6]謊[7]謊[8 ] fib [9] fib [10] 1 1 2 3 5 8 13 21 34 55``