How could I calculate number of recursive calls for Fibonacci array in C?

Question

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

Is there a function for counting recursive calls?

Answer 1

One of the solutions is to use a static local integer counter (if you only want to access it inside) or global integer counter (if you want it to access outside) and then increment this counter inside the function each time you call it. you can try this!

int GlobalCount = 0 ;
int FibonacciArray(int n)
{
    static int LocalCounter = 0;
    LocalCounter++;
    GlobalCount++;
    if(n<=2)
    { 
        return 1;    
    }
    else 
    {
        return FibonacciArray(n-1) + FibonacciArray(n-2);
    }
}

Answer 2

The function can return a structure that will contain the result Fibonacci value and the number of the function calls.

Pay attention to that the function should deal with values of an unsigned integer type. Also the first Fibonacci number is equal to 0. And when n is equal to 2 the function is called 3 times: for initial value of 2 and then recursively for the value 1 and the value 0.

Here is a demonstration program.

#include <stdio.h>

struct FibonacciResult
{
    unsigned int value;
    unsigned int n_calls;
};

struct FibonacciResult Fibonacci( unsigned int n ) 
{
    if  ( n < 2 ) 
    {
        struct FibonacciResult result = { .value = n, .n_calls = 1 };
        return result;
    }
    else 
    {
        struct FibonacciResult result1 = Fibonacci( n - 1 );
        struct FibonacciResult result2 = Fibonacci( n - 2 );

        result1.value += result2.value;
        result1.n_calls += result2.n_calls + 1;

        return result1;
    }
}

int main( void )
{
    for (unsigned int n = 0; n < 10; n++)
    {
        struct FibonacciResult result = Fibonacci( n );
        printf( "n = %u: value = %u, number of calls = %u\n", 
            n, result.value, result.n_calls );
    }
}

The program output is

n = 0: value = 0, number of calls = 1
n = 1: value = 1, number of calls = 1
n = 2: value = 1, number of calls = 3
n = 3: value = 2, number of calls = 5
n = 4: value = 3, number of calls = 9
n = 5: value = 5, number of calls = 15
n = 6: value = 8, number of calls = 25
n = 7: value = 13, number of calls = 41
n = 8: value = 21, number of calls = 67
n = 9: value = 34, number of calls = 109

Or it would be more safer to declare members of the structure as having the type unsigned long long int as for example

struct FibonacciResult
{
    unsigned long long int value;
    unsigned long long int n_calls;
};

In this case the call of printf will look like

        printf( "n = %u: value = %llu, number of calls = %llu\n", 
            n, result.value, result.n_calls );

In fact numbers of calls also produce a series similar to the Fibonacci series increased by 1. For example for n is equal to 3 you have the number of calls for n equal to 2 (3) plus the number of calls for n equal to 1 (1) plus 1.

Answer 3

A call to a function is said to be recursive only when it is made by the function itself. So the first call to the recursive function, in main(), is not a recursive call. Also, each time your recursive function is called, if the stop condition is not satisfied, it makes two new recursive calls.

#include <stdio.h>

int F(int n, int *c) {
    if( n <= 2 ) return 1;
    *c += 2;                      // count next two recursive calls
    return F(n-1, c) + F(n-2, c);
}

int main(void) {
    int c, r;
    for(int n=1; n<=10; n++) {
        c = 0;
        r = F(n, &c);             // this call is not recursive!
        printf("F(%d) = %d (calls = %d)\n", n, r, c);
    }
}

Output:

F(1) = 1 (calls = 0)
F(2) = 1 (calls = 0)
F(3) = 2 (calls = 2)
F(4) = 3 (calls = 4)
F(5) = 5 (calls = 8)
F(6) = 8 (calls = 14)
F(7) = 13 (calls = 24)
F(8) = 21 (calls = 40)
F(9) = 34 (calls = 66)
F(10) = 55 (calls = 108)

Answer 4

How could I calculate number of recursive calls for Fibonacci array in C?

With OP's algorithm, the recursive call count is also based on the Fibonacci series.

For x > 0:

number_of_recursive calls(x) = (FibonacciArray(x) - 1) * 2;