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
    I hope you're not going to use this algorithm in real life?2012-12-11
  • 0
    Assuming you are using Java, add a global variable. `public static int counter;`2012-12-11
  • 0
    I calculated this numbers with java but it is very big number and takes hours to find it. I am sure that there is number and I think formula is like this 2*n+X+1 but can't find X2012-12-11
  • 0
    You have gotten the answer in several of the other forums where you posted this question.2012-12-11
  • 0
    Maybe post it on stackoverflow2012-12-11
  • 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
    thanks. but I know that there is ways to avoid calculate the values that already calculated by using matrix. but the purpose of the problem is to show without using matrix how many recursive calls we need and there fully why we should use matrix. I don't need a better way2012-12-11
  • 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