How many times does fib(3) gets called when we call fib(6) using the recursive approach to Fibonacci series?

Yes, you are correct. The fib(k - n + 1) will give number of times fib(n) called when calculating fib(k) recursively, where k > n and this works for n = 0 as well.

When we write code to calculate k^th Fibonacci number, we give seed values fib(0) = 0 and fib(1) = 1 which is also the terminating condition when using recursion.

From Generalizations of Fibonacci numbers:

Consider this example, assume that not given the seed values f(0) = 0 and f(1) = 1:

  // read f(x) as fibonacci(x)
                                   f(4)
                                    |
                  -------------------------------------
                  |                                   |
                 f(3)                                f(2)
                  |                                   |
          -----------------                  --------------------
          |               |                  |                  |
         f(2)            f(1)               f(1)               f(0)
          |               |                  |                  |
      ---------      ----------         ----------         -----------
      |       |      |        |         |        |         |         |
     f(1)    f(0)   f(0)     f(-1)     f(0)     f(-1)     f(-1)     f(-2)
      |       |      |        |         |        |         |         |
    -----   -----  -----    -----     -----    -----     -----     -----
    |   |   |   |  |   |    |   |     |   |    |   |     |   |     |   |
  f(0) f(-1)|   |f(-1)f(-2) |   |  f(-1) f(-2) |   |  f(-2) f(-3)  |   |
    |       |   |           |   |              |   |               |   |
    |    f(-1) f(-2)     f(-2) f(-3)        f(-2) f(-3)         f(-3) f(-4)
  -----
  |   |
f(-1) f(-2)
 .....
 ..... and so on

Now lets calculate the number of f(n) calls for f(4) using f(4 - n + 1), where n < 4:

n = 3  ==>  f(4 - 3 + 1)   ==> f(2) ==> 1  --
n = 2  ==>  f(4 - 2 + 1)   ==> f(3) ==> 2   |
n = 1  ==>  f(4 - 1 + 1)   ==> f(4) ==> 3   |-  Number of time f(n) called when calculating f(4)
n = 0  ==>  f(4 - 0 + 1)   ==> f(5) ==> 5   |   cross check it with recursive call trace shown above
n = -1 ==>  f(4 -(-1) + 1) ==> f(6) ==> 8  --
.....
..... and so on

EDIT:

The bidirectional sequence of fibonacci is (based on formula in above link):

----------------------------------------------------------------------------------
... f(−4) | f(−3) | f(−2) | f(−1) | f(0) | f(1) | f(2) | f(3) | f(4) | f(5) | f(6) ....
----------------------------------------------------------------------------------
... −3    | 2     | −1    | 1     | 0    | 1    | 1    | 2    | 3    | 5    | 8 ....
----------------------------------------------------------------------------------

From this sequence, fib(-3) = 2 and fib(-4) = -3. Lets use these values as terminating condition of recursion instead of fib(0) = 0 and fib(1) = 1:

#include <stdio.h>

int fib(int n) {
        if (n == -3) {
                return 2;
        }

        if (n == -4) {
                return -3;
        }

        printf ("recursive call - fib(%d) + fib(%d)\n", n - 1, n - 2);
        return fib(n - 1) + fib(n - 2);
}

// This is a test program to prove OP number of calls to f(n)
// when calculating f(k), where n < k

int main(void) {
        int n;
        printf ("Enter a number (>= -4):\n");
        scanf ("%d", &n);

        // Input less than -4 not allowed as -4 is
        // the least seed value provided which is also  
        // a terminating condition of recusive function
        // calculating kth fibonacci number

        if (n < -4) {
                return 0;
        }

        printf("Fibonacci Number at location %d in series : %d\n", n, fib(n));    return 0;
}

Output:

# ./a.out 
Enter a number (>= -4):
4
recursive call - fib(3) + fib(2)
recursive call - fib(2) + fib(1)
recursive call - fib(1) + fib(0)
recursive call - fib(0) + fib(-1)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
recursive call - fib(0) + fib(-1)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(1) + fib(0)
recursive call - fib(0) + fib(-1)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-1) + fib(-2)
recursive call - fib(-2) + fib(-3)
recursive call - fib(-3) + fib(-4)
recursive call - fib(-3) + fib(-4)
Fibonacci Number at location 4 in series : 3

In the output, the number of times f(0) called when calculating f(4) is same as the one calculated with f(k - n + 1) where k = 4 and n = 0 (satisfying condition k > n) and 0 is not the least value.

Yes, it is correct to do so, except for the case n = 0.
Let get_calls(k,n) denote the function which takes two arguments n and k and returns the number of calls made to fib(n) in the calculation of fib(k).
It is important to observe that: fib(0) is only called by fib(2) hence,

• get_calls(k,0) = get_calls(k,2)

• Base Case: get_calls(k,k-1)=1.

• Recurrence Relation: get_calls(k,m) = get_calls(k-1,m) + get_calls(k-2,m).

Implementation of the method

int get_calls(int k,int n)
{     
      if(n>k)  return 0;
      else if(n==0)  return get_calls(k,2);
      else if ((n==k-1)||(n==k))  return 1;
      return get_calls(k-1,n) + get_calls(k-2,n);
} 

This function mimics the working of the function fib

Claim: get_calls(n+m,n) = fib(m+1)

We'll prove this by strong form of induction on m. For m=1 it holds i.e. get_calls(n+1,n) = 1 = fib(2).
Now, let it also holds for all natural numbers m<p. But that means that
get_calls(n+p-1,n) = fib(p) and get_calls(n+p-2,n) = fib(p-1)
which gives
get_calls(n+p,n) = get_calls(n+p-1,n) + get_calls(n+p-2,n) = fib(p-1) + fib(p) = fib(p+1)

Putting m = k-n in the above formulla gives the required result.

Hence, for n!=0 and n<=k, get_calls(k,n)=fib(k-n+1) and get_calls(k,0) = get_calls(k,2) = fib(k-2+1) = fib(k-1).

$ cc fib.c -o fib && ./fib

3 occurrences of fib(3) in fib(6)

#include <stdio.h>

static size_t N, n, target;

size_t fib(size_t n)
{
  if (n == target)
    N++;

  if (n < 2)
    return n;

  return fib(n - 1) + fib(n - 2);
}
                                                                                                                                                                                               
int main()
{
  target = 3;
  n = 6;
  size_t result;
  /* target < n + 1 */
  if (target < n + 1)
    result = fib(n);

  printf("%ld occurrences of fib(%ld) in fib(%ld)\n", N, target, n);
  return 0;
}

You can determine the answer by instrumenting your code with a printf statement:

int fib(int n)
{
    static int fibcount;
    printf("fib() called for the %dth time with argument %d.\n", ++fibcount, n);
    if (n <= 1) return n; 
    return fib(n-1) + fib(n-2);
}