c++ - 递归斐波那契..不知道发生了什么

我最近为c ++应用程序中的过程函数编写了代码，用于计算斐波那契序列中的F（n）。

无论如何，我无法使用递归获得正确的结果。例如，每当我输入值5时，它返回8，而我的其他过程代码返回的正确值是5。

这是我正在使用的功能...以及从网上获得的代码。我的问题是网络上的代码和我的代码完全相同（几乎），但是两者都给出了错误的值...

http://codepad.org/pMKs4kvb

到底是怎么回事？

最佳答案

简而言之，您的功能是打印以下系列：

1, 1, 2, 3, 5, 8 ...

因此，F(5) = 8（如果我们在这里谈论零索引）。如果要打印以下内容：

0, 1, 1, 2, 3, 5, 8 ...

这是OEIS识别的顺序，那么您要做的就是确保定义了F(0) = 0。在这种程度上，您的功能应该只是：

int FibiRec(int n) {
    if (n == 0 || n == 1) {
        return n; // IMPORTANT
    } else {
        return FibiRec(n-1) + FibiRec(n-2);
    }
}

同时，我想补充一下：您的函数的时间复杂度很差O(2^n)。使用您的函数，尝试生成第40或第100斐波那契数，您将了解我在说什么。

关于c++ - 递归斐波那契..不知道发生了什么，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9662184/