Number of recursion calls for each Fibonacci number

Question

Why is there a variation between the numbers in the output of my code, versus the expected output result (as pasted at the end)?

I went through these questions related to the calculation of the number of recursive calls:

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

I could not form a proper answer or a solution to my question.

I even tried re-initializing the count by writting call_count = 0; in the main() function after the for loop or also in the function definitions (as suggested in the answers of the second link above) but, it did not work or give me the expected output.

I have pasted my code below and its output below the code, and the expected output below my code output.

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

The Output for My Code:

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 . . .

Whereas the EXPECTED output numbers are as follows:

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 . . .

How do I resolve this mismatch?

Answer 1

Reset the call_count to zero before making call to fibo() method.

#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

Collectively summarizing from the pin-point inputs of @rlbond and @zeroCool, along with a tiny change to both to form a single answer:-

resetting call_count to zero on each loop iteration, and printing the call_count on a separate statement from the call to fibo (since it could be evaluated at the call point), will yield the expected output. Also one needs to subtract 1 from call_count (for the initial call), while printing out the count statement for each fibonacci number to get the expected count.

Following Code reduces the need of an extra variable and splits the print statement evaluating to expected output. (alternatively one could refer to the link from rlbond's comment on the question above. 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;
}

Works fine, output as follows:-

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 0 calls

3th number 2 2 calls

4th number 3 4 calls

5th number 5 8 calls

6th number 8 14 calls

7th number 13 24 calls

8th number 21 40 calls

9th number 34 66 calls

10th number 55 108 calls

11th number 89 176 calls

12th number 144 286 calls

13th number 233 464 calls

14th number 377 752 calls

15th number 610 1218 calls

the total number of recursive calls made were 1218

Press any key to continue . . .

gratitude to everyone's contribution.