number of recursive calls

Question

How to estimate the number of recursive calls that would be used by the code

public static double binomial(int N, int k, double p) {
if ((N == 0) || (k < 0)) return 1.0;
return (1.0 - p)*binomial(N-1, k) + p*binomial(N-1, k-1); 
}

to compute binomial(100, 50)???

I am looking for the formula that gives me the exact number of calls I think it is related to factorial but I can't find formula

number of recursive calls for $n\leq 6$

$(1,0)=3$
$(2,0)=5$
$(2,1)=7$
$(3,0)=7$
$(3,1)=13$
$(3,2)=15$
$(4,0)=9$
$(4,1)=21$
$(4,2)=29$
$(4,3)=31$
$(5,0)=11$
$(5,1)=31$
$(5,2)=51$
$(5,3)=61$
$(5,4)=63$
$(6,0)=13$
$(6,1)=43$
$(6,2)=83$
$(6,3)=113$
$(6,4)=125$
$(6,5)=127$

Answer 1

This indirectly answers your question, in the sense that it offers a more efficient algorithm in which the number of calculations can be calculated.

Assuming a matrix C with height N + 1 and width K + 1:

for (int k = 1; k <= K; k++) C[0][k] = 0;
for (int n = 0; n <= N; n++) C[n][0] = 1;

for (int n = 1; n <= N; n++)
   for (int k = 1; k <= K; k++)
      C[n][k] = C[n-1][k-1] + C[n-1][k];

If you want, you can make the last line into a function, but the number of total calulations will be $N*K$ ($(N+1)(K+1)$ if you take into consideration the first two loops).

If you use recursion here, you will have to calculate values you've already calculated. Doing it this way means you do it once and once only.

Edit: You can optimize this further by retaining the calculated matrix so you can avoid calculating from the beginning, calculating only the values which haven't been discovered yet.