使用斐波那契數列的遞歸函數

我是自學C++ Sams自學C++一天一小時和第150頁作者討論了使用斐波那契數列的遞歸函數。使用斐波那契數列的遞歸函數

他使用以下代碼：

#include <iostream> 
using namespace std; 

int GetFibNumber(int FibIndex) 
{ 
    if(FibIndex < 2) 
     return FibIndex; 
    else 
     return GetFibNumber(FibIndex - 1) + GetFibNumber(FibIndex - 2); 
} 

int main() 
{ 
    cout << " Enter 0 based index of desired Fibonacci Number: "; 
    int Index = 0; 
    cin >> Index; 

    cout << " Fibonacci number is: " << GetFibNumber(Index) << endl; 

    return 0; 

}

是什麼具有

返回GetFibNumber之間的差值（FibIndex - 1）+ GetFibNumber（FibIndex - 2）;

和

返回FibIndex - 1 + FibIndex - 2;

爲什麼你必須在它自己內部調用函數？

預先感謝您！

來源

2013-12-17 JOG-Design

您能否提供一個您做過的例子，並更清楚地解釋您的問題。 –

第9行現在讀了什麼？沒有這兩個函數調用，它將不會計算斐波那契數列。 –

請看看斐波納契系列是什麼http://en.wikipedia.org/wiki/Fibonacci_number如果沒有最後一次'GetFibNumber（FibIndex - 1）+ GetFibNumber（FibIndex - 2）'計算是錯誤的。 – bkausbk

你問：「你爲什麼不得不在自己內部調用函數？」那麼，嚴格來說，你沒有。

的Fibonacci sequence是由該數學遞歸定義數序列：

一個 = 0
一個 = 1
一個_Ñ =一個_n-1 + a _n-2

原始函數的確計算了這個序列，儘管效率很低。如果Index爲0，則返回0;如果它是1，則返回1.否則返回GetFibNumber(Index - 1) + GetFibNumber(Index - 2)，這正是數學定義所在。對於序列的每個元素，必須在序列中添加前兩個項。

你的代碼只是返回Index - 1 + Index - 2，這將給出不同的數字序列。比較：

斐波：0，1，1，2，3，5，8，13，21，36 ...
此致：0，1，1，3，5，7，9 ，11,13,17 ...

但是，除此之外，您並不嚴格需要遞歸函數來計算此數學遞歸。所有你需要的是一個簡單的for循環：

int GetFibNumber(int FibIndex) 
{ 

    if(FibIndex < 2) 
     return FibIndex; 

    int a_n_2 = 0, a_n_1 = 1, a_n; 

    for (i = 2; i < FibIndex; i++) 
    { 
     a_n = a_n_1 + a_n_2; 
     a_n_2 = a_n_1; 
     a_n_1 = a_n; 
    } 

    return a_n; 
}

這種方法會更快，也。

代碼遞歸技術在數學上是正確的。但是，它比較慢，因爲它不會重複使用任何計算。它通過將遞歸返回到來計算_n-1。然後計算一個_n-2，而不重複使用任何生成_n-1的工作。如果您認爲在遞歸的每一步都會發生這種重複使用不足的情況，那麼您會發現running time grows exponentially for the recursive function.它對於for循環線性增長。

_{高級話題：有一種方法可以使遞歸版本運行速度更快，而且可以知道，如果你遇到的是最容易遞歸定義編程的問題非常重要。一旦你對C++更加熟悉，請查閱memoization。一個記憶遞歸斐波那契給出了線性最壞情況下的運行時間和重複查找的恆定運行時間（假設備忘錄查找本身是O（1））。}

來源

2013-12-17 13:20:10

Lol，知道他不必編程一個迭代程序了，就像我建議的:) – RvdV79

@ RvdV79：我想我們幾個人平行回答了這個問題。有時候，我認爲這些問題是羅夏測驗。 ;-) –

使用不使用遞歸的版本不正確。它只會計算正確的前幾個Fiboonacci數字。嘗試使用這兩個版本計算前10個斐波納契數，並且您會看到自己的兩個版本計算兩個不同的序列。

來源

2013-12-17 13:13:22

函數GetFibNumber計算斐波那契數列中的第N個數。如果你只是看看關於http://en.wikipedia.org/wiki/Fibonacci_number的解釋，它是通過在斐林納奇系列中加上Nth-1和Nth-2數字來計算的。這正是這個功能的作用。您可以在斐波那契數列中提供您想要計算的指數（可以說6;這應該有8個結果）。

要計算Fibonacci系列中的第6個元素，您需要將第5個和第4個元素添加到一起。所以你首先需要計算這些。這是遞歸進入的地方。你可以讓函數自己調用;但不是再次用值6作爲參數再次調用它，您現在使用5和4.這將再次導致相同的問題（您需要通過添加元素4和3來計算第5個元素）等。等等。

通過遞歸函數，您可以簡單地重複使用代碼一遍又一遍地執行相同的計算，直到達到某個計算結果的某個點（在這種情況下，如果N = 1或N = 0;這些情況將導致1）。

來源

2013-12-17 13:18:09 RFerwerda

因爲您仍然在學習，所以我會建議您遞歸編程（如作者所做的那樣）並使用循環（while，for）。它很可能會告訴你如何構建這個算法的答案。

提示1：你必須知道，Fibonnaci序列被建造在兩個初始值...

提示2：當涉及到遞歸，你應該知道的功能結果是如何存儲。這也會解釋你的問題。

來源

2013-12-17 13:20:00 RvdV79

它們不是等價的，它肯定不會計算fibonanic序列。遞歸可以像一棵樹被認爲是，如此計算蛋白原（8）說，通過定義，我們採取蛋白原（7）+纖維蛋白原（6）

 Fib(8) 
     / \ 
    Fib(7) Fib(6)

而這又需要計算纖維蛋白原（6），纖維蛋白原（ 5），Fib（4）如下：

    Fib(8) 
      /  \ 
      Fib(7)  Fib(6) 
     /  \ / \ 
    Fib(5) Fib(6) Fib(5) Fib(4)

依此類推。你在做什麼，會產生不同的，深度爲1種的樹：

Fib(8) 
    / \ 
    7  6

因爲，如果你從來沒有在函數中調用該函數，它永遠不能去比較深。這應該清楚，其他答案爲什麼它不正確。

來源

2013-12-17 13:33:47

使用斐波那契數列的遞歸函數

回答

相關問題