Computing the number of times fib(n) is called FOR EACH n

Question

I want to compute the number of times fib(n) is called FOR EACH n. I have written the code as below:

#include <stdio.h>
#define N 10

int count[N + 1]; // count[n] keeps track of the number of times each fib(n) is called

int fib(int n) {
    count[n]++;

    if(n <= 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

int main() {
    for(int i = 0; i <= N; i++) {
        count[i] = 0; // initialize count to 0
    }
    fib(N);

    // print values of count[]
    for(int i = 0; i <= N; i++) {
        printf("count[%d] = %d", i, count[i]);
    }
}

I have tried printing the array count[] to get the result, where the result is resembles the fibonacci numbers except for count[0]:

count[0] = 34 count[1] = 55 count[2] = 34 count[3] = 21 count[4] = 13 count[5] = 8 count[6] = 5 count[7] = 3 count[8] = 2 count[9] = 1 count[10] = 1

Is there a way to mathematically show this result, maybe a recursive formula? Also, why doesn't count[0], or rather fib(0), doesn't continue the fibonacci sequence? Thanks.

Answer 1

Because count[1] is going to be called for each count[2] + count[3] but count[0] is only going to be called for count[2]...count[1] doesn't contribute because it's a terminus.

As for mathematical formula:

if n == 0: fib(N - 1)
else: fib(N-(n-1))

Answer 2

As for calculation

call(n)=call(n-1)+call(n-2)+1
  call(1)=1
  call(0)=1

Hope this make things clear.

n  | calls
---+--------
0  |   1
1  |   1
2  |   3 
3  |   5  f(3)= f(2)[= f(1)+ f(0)]+ f(1)
5  |   9  
.
fib(n)    2*fib(n)-1