c++ - 每个斐波那契数的递归调用次数

Question

为什么我的代码输出中的数字与预期输出结果(粘贴在最后)之间存在差异？

我经历了这些与递归调用次数计算相关的问题:

• Number of calls for nth Fibonacci number
• Count number of recursive calls in fibonacci

我无法对我的问题形成正确的答案或解决方案。

我什至尝试通过在 for 循环之后的 main() 函数中或在函数定义中写入 call_count = 0; 来重新初始化计数(如第二个链接的答案中所建议的那样)上面)但是，它没有工作或没有给我预期的输出。

我在下方粘贴了我的代码及其输出，在我的代码输出下方粘贴了预期输出。

#include <iostream>
#include "math.h"
#include <iomanip>

using namespace std;

int call_count = 0;

int fibo(int n)
{
    call_count+=1;
    if(n<=2)
    {
        return 1;
    }
    else {
            //call_count += 1;
            return fibo(n-1) + fibo(n-2);
         }
    return n;
}

int main()
{
    int num;
    cout<<"\nenter the number of integers to be printed in the fibonacci series\n";
    cin>>num;
    cout<<"\nfibonacci series for first "<<num<<" numbers is\n";
    cout<<"\n\nSerial Number\t"<<"FIBO_NUMBER\t"<<" NO_OF_CALLS MADE\n\n";
    for(int i=1;i<=num;i++)
    {
        cout<<endl<<i<<"th number\t   "<<fibo(i)<<"\t\t"<<call_count<<" calls\n";
    }
cout<<endl<<"\n the total number of recursive calls made were "<<call_count<<endl<<endl;
system("pause");
return 0;
}

我的代码的输出:

enter the number of integers to be printed in the fibonacci series
15

fibonacci series for first 15 numbers is

Serial Number   FIBO_NUMBER      NO_OF_CALLS MADE


1th number         1            0 calls

2th number         1            1 calls

3th number         2            2 calls

4th number         3            5 calls

5th number         5            10 calls

6th number         8            19 calls

7th number         13           34 calls

8th number         21           59 calls

9th number         34           100 calls

10th number        55           167 calls

11th number        89           276 calls

12th number        144          453 calls

13th number        233          740 calls

14th number        377          1205 calls

15th number        610          1958 calls


 the total number of recursive calls made were 3177

Press any key to continue . . .

而预期的输出数字如下:

1 th integer of fibonacci series is 1 and it needed 0 recursive calls
2 th integer of fibonacci series is 1 and it needed 0 recursive calls
3 th integer of fibonacci series is 2 and it needed 2 recursive calls
4 th integer of fibonacci series is 3 and it needed 4 recursive calls
5 th integer of fibonacci series is 5 and it needed 8 recursive calls
6 th integer of fibonacci series is 8 and it needed 14 recursive calls
7 th integer of fibonacci series is 13 and it needed 24 recursive calls
8 th integer of fibonacci series is 21 and it needed 40 recursive calls
9 th integer of fibonacci series is 34 and it needed 66 recursive calls
10 th integer of fibonacci series is 55 and it needed 108 recursive calls
11 th integer of fibonacci series is 89 and it needed 176 recursive calls
12 th integer of fibonacci series is 144 and it needed 286 recursive calls
13 th integer of fibonacci series is 233 and it needed 464 recursive calls
14 th integer of fibonacci series is 377 and it needed 752 recursive calls
15 th integer of fibonacci series is 610 and it needed 1218 recursive calls
Press any key to continue . . .

如何解决这种不匹配？

Answer 1

在调用 fibo() 方法之前将 call_count 重置为零。

#include <iostream>
#include "math.h"
#include <iomanip>

using namespace std;

int call_count = 0;

int fibo(int n)
{
    call_count+=1;
    if(n<=2)
    {
        return 1;
    }
    else {
            //call_count += 1;
            return fibo(n-1) + fibo(n-2);
         }
    return n;
}

int main()
{
    int num;
    cout<<"\nenter the number of integers to be printed in the fibonacci series\n";
    cin>>num;
    cout<<"\nfibonacci series for first "<<num<<" numbers is\n";
    cout<<"\n\nSerial Number\t"<<"FIBO_NUMBER\t"<<" NO_OF_CALLS MADE\n\n";
    for(int i=1;i<=num;i++)
    {
        call_count = 0; 
        cout<<endl<<i<<"th number\t   "<<fibo(i)<<"\t\t"<<call_count<<" calls\n";
    }
    cout<<endl<<"\n the total number of recursive calls made were "    <<call_count<<endl<<endl;
    system("pause");
    return 0;
}