Q:

Counting number of recursive calls in fibonacci, in C

I faced the following question:
Calling fib(8) (below), how many recursive calls are made (ignoring the first) ? And what's the return value?
int fib (int n) {
    if (n==0 || n==1) return 1;
    else return fib(n-1) + fib(n-2);
}

So I did:
#include <stdio.h>
#include <stdlib.h>

int r = 0;

int fib (int n) {
    printf("k: %d fib n: %d", r++, n);
    if (n==0 || n==1) {
        printf("\n");
        return 1;
    } else { 
        printf(" +\n");
        return fib(n-1) + fib(n-2); 
    }
}

int main(int argc, char **argv) {
    int n = atoi(argv[1]);
    int f = fib(n);
    printf("\nreturn: %d\n", f);
    return 1;
}

Using this I'll answer fib(8) = 34 the number of recursive calls is 66.
Am I right?

A:

First of all Total fib calls = 67
recursive calls is = 66
                   fib(5)   ---root-first call ,not consider recursive call 
                 /           \     
           fib(4)             fib(3)   
         /      \                /     \
     fib(3)      fib(2)       fib(2)    fib(1)
    /     \        /    \       /    \  

-
because first call is not considered as recursive call
Now lets derive a formula for calculate number of times fib(n) is called
Let f(n) be the number of calls made to calculate fib(n).
If n < 2 then f(n) = 1.
Otherwise, f(n) = 1 + f(n - 1) + f(n - 2)
So, f is at least O(fib(n)). In fact, f(n) is 2 * fib(n) - 1. 
We show this by induction:
Base cases (n < 2, that is, n = 0 or n = 1):
f(n) = 1 = 2 * 1 - 1 = 2 * fib(n) - 1.
Induction step (n >= 2):
f(n + 1) = f(n) + f(n - 1) + 1
f(n + 1) = 2 * fib(n) - 1 + 2 * fib(n - 1) - 1 + 1
f(n + 1) = 2 * fib(n + 1) - 1
Example
fib(8)=34   
so  recursive calls= 2*34-1=67
ans=67-1(for first call)
fib(4)=5
so recursive calls= 2*5-1=9
ans=9-1(for first call)
Also fib(n) can be calculated in o(logn)
so overall complexity reduces to o(logn)
O(logn) for finding fib(n) and O(1) for finding recursive calls
but your code takes exponential time

