Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
I hope you're not going to use this algorithm in real life? –  TonyK Dec 11 '12 at 12:28
    
Assuming you are using Java, add a global variable. public static int counter; –  sonystarmap Dec 11 '12 at 12:36
    
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 X –  Arira Dec 11 '12 at 12:45
    
You have gotten the answer in several of the other forums where you posted this question. –  Jakob Dec 11 '12 at 13:37
    
Maybe post it on stackoverflow –  xiamx Dec 11 '12 at 15:33

1 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.

share|improve this answer
    
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 way –  Arira Dec 11 '12 at 17:38
    
@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 stackoverflow.com/questions/1738923/…. 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? –  Neil Dec 12 '12 at 11:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.