使用Fibonacci级数的递归函数

Question

我是来自Sams的自学C++，每天一小时自学C++，在第150页中，作者使用Fibonacci系列讨论递归函数。

他使用以下代码：

#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；

为什么要调用函数本身？

提前谢谢你！

Answer 1

使用不使用递归的版本是不正确的。它只会正确计算前几个Fiboonacci数。尝试使用这两个版本计算前10个Fibonacci数，您将看到自己，这两个版本计算两个不同的序列。

Answer 2

函数GetFibNumber计算斐波纳契级数中的N个数。如果您只是看看对数的解释，它是通过在Fibinacci系列中添加Nth-1和Nth-2数字来计算的。这正是这个函数的作用。您可以在Fibonacci系列中为函数提供要计算的索引(假设为6；结果应该是8)。

要计算Fibonacci系列中的第6个元素，需要将第5个和第4个元素相加。所以你首先要计算一下。这就是递归开始的地方。您可以让函数自己调用；但是，与其使用值6作为参数再次调用它，您现在使用5和4。这将再次导致同样的问题(您需要通过添加元素4和3来计算第5个元素)，等等。

使用递归函数，您可以简单地重复使用代码来一次又一次地执行相同的计算，直到达到了计算的答案(在这种情况下，如果N=1或N= 0；这些情况将导致1)。

Answer 3

我建议，既然您还在学习，就应该递归地(就像作者所做的那样)对其进行编程，并使用循环(while，for)。它很可能会告诉你这个算法是如何建立起来的。

提示1:您必须知道Fibonnaci序列是建立在两个初始值之上的。

提示2:对于递归，您应该知道函数结果是如何存储的。这也能解释你的问题。