1
$\begingroup$

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$

  • 0
    It's suspicious that you don't get the same value, e.g., for $(4,1)$ and $(4,3)$, and that you don't compute $(4,4)$. Looking at the implementation, it appears to be getting the base cases severely wrong, although it's not clear exactly what you're trying to compute.... Also, the arguments to the definition of `binomial` don't match the arguments you're passing into the recursive calls.2013-01-13

1 Answers 1

2

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.

  • 0
    @Arira I'm afraid the nature of the problem is recursive. I'm looking at the classic fibonacci recursion, but for number of calls and I found http://stackoverflow.com/questions/1738923/number-of-calls-for-nth-fibonacci-number. I could be wrong, but I think you can know the number of calls if you have a formula for solving the number itself (a bit like calculating formula for velocity from a formula which plots the path of a projectile). So the question then becomes, is there a non-recursive formula for finding binomial?2012-12-12