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

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?

CodePudding user response：

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

CodePudding user response：

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.