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

Question

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

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

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

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

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

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

#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;
}

Answer 2

根据@rlbond 和@zeroCool 的精确输入进行集体总结，并对两者进行微小的更改以形成一个答案：-

在每次循环迭代时将 call_count 重置为零，并在调用 fibo 的单独语句中打印 call_count （因为它可以在调用点进行评估），将产生预期的输出。还需要从 call_count 中减去 1（对于初始调用），同时打印出每个斐波那契数的计数语句以获得预期计数。

以下代码减少了对额外变量的需求，并将评估为预期输出的打印语句拆分。（或者可以参考 rlbond 对上述问题的评论中的 link。ideone.com/8EWjOC ）

#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 {
            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";
        cout<<call_count-1<<" calls\n";
    }
cout<<endl<<"\n the total number of recursive calls made were "<<call_count-1<<endl<<endl;
system("pause");
return 0;
}

运行正常，输出如下：-

输入斐波那契数列中要打印的整数个数 15

前 15 个数字的斐波那契数列是

序列号FIBO_NUMBERNO_OF_CALLS制造

第1个号码1 0个电话

第2个号码1 0个电话

第3个号码2 2个电话

第4个号码3 4个电话

第5个号码5 8个电话

第6号8号14次

第7号13 24来电

8号21 40来电

第9号34 66来电

10号55108来电

11号89176来电

第12号144286来电

第13号233464来电

第14号377752次来电

第15号610 1218来电

递归调用总数为1218

按任意键继续。 . .

感谢大家的付出

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

Number of recursion calls for each Fibonacci number

c++

recursion

counter