如何在 C++ 中使用递归打印最多 n 个数的斐波那契数列

Question

我正在尝试使用递归打印斐波那契数列。不幸的是，它反复打印最后一个数字。

例如；如果我输入 5，它首先打印：1，然后是 0，然后是 1 & 1，然后是 2，然后它再次开始重复 0 1 1 2 然后打印 3.

#include<iostream>
using namespace std;

int fibonacci(int n)
{
    if (n == 0 || n == 1)
    {
        cout << n << " ";
        return n;
    }
    else
    {
        int sum = fibonacci(n - 1) + fibonacci(n - 2);
        cout << sum << " ";
        return sum;
    }
}

//====================================================================
void main()
{
    int n;
    cout << "Please input the Limit: ";
    cin >> n;
    fibonacci(n);
    system("pause>null");
}

Answer 1

斐波那契函数的递归定义是

fib(n) = fib(n-1) + fib(n-2)

所以只需更改

int sum = fibonacci(n - 1) + fibonacci(n - 1);

至

int sum = fibonacci(n - 1) + fibonacci(n - 2);

测试：

Please input the Limit: 5
1 0 1 1 2 1 0 1 3 1 0 1 1 2 5

Please input the Limit: 6
1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8

编辑 1

您想使用此算法打印斐波那契数列 fib(0), fib(1), ...。如果你稍微加强你的输出你会看到它是如何工作的 fib(5):

fib 1 = 1
fib 0 = 0
fib 2 = 1
fib 1 = 1
fib 3 = 2
fib 1 = 1
fib 0 = 0
fib 2 = 1
fib 4 = 3
fib 1 = 1
fib 0 = 0
fib 2 = 1
fib 1 = 1
fib 3 = 2
fib 5 = 5
5

如您所见，很多值被计算了多次，这解释了打印的顺序。一种只计算每个结果一次的方法是 Memoization。如果您使用记忆并且只在第一次确定结果时打印，您将得到：

fib 1 = 1
fib 0 = 0
fib 2 = 1
fib 3 = 2
fib 4 = 3
fib 5 = 5
5

所以即使那样你也得不到你想要的订单。所以你必须使用 memoisation 并且只在过程结束时打印哈希映射。

5
fib 0 = 0
fib 1 = 1
fib 2 = 1
fib 3 = 2
fib 4 = 3
fib 5 = 5

当然，您也可以创建一个额外的循环并打印 fib(i) for i 从 1 到 n 的所有值。不过，那将是相当低效的。

编辑 2

免责声明：我对 C++ 一无所知。我很久以前写了最后一个 C 程序。但是下面的作品，我相信其他人会做得更好。

下面是一个使用普通数组进行记忆的简单示例，没有哈希映射。既然你没有说 你到现在学到了哪些 个概念，我希望这很简单。

#include <iostream>

#define MAX 100
#define UNDEF -1

using namespace std;

int memo[MAX]; // memoization of results

int fibonacci(int n) {
    int res = memo[n];
    if (res != UNDEF) return res; // result has been computed before
    if (n == 0 || n == 1)
        res = n;
    else
        res = fibonacci(n - 1) + fibonacci(n - 2);
    memo[n] = res; // memoize result
    return res;
}

int main() {
    int n, i;
    do {
        cout << "Please input the Limit (max " << MAX << ") : ";
        cin >> n;
    } while (n < 0 || n >= MAX);
    for (i=0; i<=n; i++) memo[i] = UNDEF; // intitialize memo
    fibonacci(n);
    for (i=0; i<=n; i++) cout << memo[i] << " "; // print results
    cout << endl;
}

测试：

Please input the Limit (max 100) : 40
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155

Answer 2

这是一个实现示例，使用 memoization:

// header needed for the container: map
#include <map> 

int mem_fact (int i, std::map<int, int>& m) {

    // if value with key == i does not exist in m: calculate it
    if (m.find(i) == m.end()) {

        // the recursive calls are made only if the value doesn't already exist
        m[i] = mem_fact (i - 1, m) + mem_fact (i - 2, m); 
    }

    // if value with key == i exists, return the corresponding value
    return m[i];
}

int fast_factorial (int i) {
    // key (Fibonacci index) - value (Fibbonaci number)
    std::map<int, int> memo;

    // initialize the first two Fibonacci numbers
    memo.insert(std::pair<int,int>(0, 0));
    memo.insert(std::pair<int,int>(1, 1));

    return mem_fact(i, memo);
}

我会把 std::cout 放在哪里，这样每个斐波那契数都显示一次。

注意：在main()你需要调用fast_factorial(num_of_fib);

Answer 3

这有效

#include <iostream>
#include <chrono>

void _fib(unsigned int current, unsigned int max, unsigned int oneBack, unsigned int twoBack)
{
    if (current == max) return;
    unsigned int sum = oneBack + twoBack;
    std::cout << sum << '\n';
    _fib(current+1, max, sum, oneBack);
}

void fib(unsigned int max)
{
    if (max >= 2)
    {
        std::cout << "0\n1\n";
        _fib(2, max, 1, 0);
    }
    else if (max == 1)
    {
        std::cout << "0\n1\n";
    }
    else if (max == 0)
    {
        std::cout << "0\n";
    }
}

int main()
{
    auto start = std::chrono::system_clock::now();
    fib(1000);
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> diff = end - start;
    std::cout << diff.count() << "seconds";
}

Answer 4

#include<iostream>

using namespace std;

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

int main()
{
int n,i=0;
cout<<"Input the number of terms for Fibonacci Series:";
cin>>n;
cout<<"\nFibonacci Series is as follows\n";

while(i<n)
{
    cout<<" "<<fibonacci(i);
    i++;
}

return 0;
}
//use this one it is easy

如何在 C++ 中使用递归打印最多 n 个数的斐波那契数列

How to print Fibonacci Series upto n numbers using Recursion in C++

c++

recursion

fibonacci