Discuss Calculate recursive calls number in the Software Design forum on Dev Shed. Calculate recursive calls number Software design forum discussing design principles and non-language specific algorithms. Get help with logic, algebraic, or relational concepts.
Posts: 6
Time spent in forums: 2 h 3 m 52 sec
Reputation Power: 0
Calculate recursive calls number
How I can estimate the number of recursive calls that would be used by the code
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
dont wanna to do it with a counter because the number is very very big and it takes time to calculate
I'm sure there is a formula
Posts: 1,936
Time spent in forums: 1 Month 1 Week 2 h 12 m 42 sec
Reputation Power: 1312
If f(N,k) is the number of recursive calls made by binomial(N,k,p), then:
f(0,k) = f(N,0) = 0 (basis case: no recursive calls)
f(N,k) = 2 + f(N,k-1) + f(N-1,k-1) if N >= 0 and k >= 0 (two recursive calls, plus however many recursive calls they make)
Make a table of the values for small values of N and k, and hopefully, you'll see a pattern. (Hint: the function g(N,k) = f(N,k)/2 + 1 satisfies a simpler recurrence than f(N,k). Are you familiar with Pascal's triangle?)
Posts: 6
Time spent in forums: 2 h 3 m 52 sec
Reputation Power: 0
Quote:
Originally Posted by Lux Perpetua
If f(N,k) is the number of recursive calls made by binomial(N,k,p), then:
f(0,k) = f(N,0) = 0 (basis case: no recursive calls)
f(N,k) = 2 + f(N,k-1) + f(N-1,k-1) if N >= 0 and k >= 0 (two recursive calls, plus however many recursive calls they make)
Make a table of the values for small values of N and k, and hopefully, you'll see a pattern. (Hint: the function g(N,k) = f(N,k)/2 + 1 satisfies a simpler recurrence than f(N,k). Are you familiar with Pascal's triangle?)
I think your answer is not true because if f(N,k) is the number of recursive calls it should be like this
f(N,k)=f(N-1,k)+f(N-1,k-1)+1
I know this formula but I want to find the formula to calculate the f(100,50) or something like that
this is the table of value for N<6
Posts: 1,936
Time spent in forums: 1 Month 1 Week 2 h 12 m 42 sec
Reputation Power: 1312
Quote:
Originally Posted by arira
I think your answer is not true because if f(N,k) is the number of recursive calls it should be like this
f(N,k)=f(N-1,k)+f(N-1,k-1)+1
I interpreted the problem differently than you: in your formula, top-level calls count as recursive calls, while in mine, they do not. No big deal. Also, I see that I misread "k < 0" as "k <= 0" in your code, which does change the formula.
Look at f(N,k) - f(N,k-1), and hopefully you'll notice the pattern. Also, arrange the table like this:
Posts: 6
Time spent in forums: 2 h 3 m 52 sec
Reputation Power: 0
Quote:
Originally Posted by Lux Perpetua
I interpreted the problem differently than you: in your formula, top-level calls count as recursive calls, while in mine, they do not. No big deal. Also, I see that I misread "k < 0" as "k <= 0" in your code, which does change the formula.
Look at f(N,k) - f(N,k-1), and hopefully you'll notice the pattern. Also, arrange the table like this:
Posts: 1,936
Time spent in forums: 1 Month 1 Week 2 h 12 m 42 sec
Reputation Power: 1312
There is definitely a formula. Do you not see a pattern after writing f(N,k) - f(N,k-1) in the grid like I said and comparing it to Pascal's Triangle?
I've all but written down the answer for you at this point. Of course, I could be wrong, like I was wrong before, but I think it's more likely that you're not following my hints. Also, if you've really been trying this for three days with no success, then the law of diminishing returns probably applies. After a while, spending additional time banging one's head against a problem doesn't pay off. Sometimes stepping away for a while can help.
Posts: 6
Time spent in forums: 2 h 3 m 52 sec
Reputation Power: 0
Quote:
Originally Posted by Lux Perpetua
There is definitely a formula. Do you not see a pattern after writing f(N,k) - f(N,k-1) in the grid like I said and comparing it to Pascal's Triangle?
I've all but written down the answer for you at this point. Of course, I could be wrong, like I was wrong before, but I think it's more likely that you're not following my hints. Also, if you've really been trying this for three days with no success, then the law of diminishing returns probably applies. After a while, spending additional time banging one's head against a problem doesn't pay off. Sometimes stepping away for a while can help.
I did what you said
but I couldn't find the relationship between the numbers after spending 3 days and asking all of my friends. I have another works to do so I give up. maybe you are right and I should leave this problem ,do another things and after few days try it again.
thanks for your help
Posts: 1
Time spent in forums: 9 m 35 sec
Reputation Power: 0
Interesting question to which, unfortunately at the moment, I don't know the answer. One thing though is that all your computed number of calls are out by 1 i.e.:
let a = 1, b = 1
g(a,b) => g(1,1) => #1
g(a, b-1) => g(1, 0) => #2 + g(a-1, b) => g(0, 1) => #3
Del.icio.us
Digg
Google
Spurl
Blink
Furl
Simpy
Y! MyWeb
Calculate recursive calls number
because if f(N,k) is the number of recursive calls it should be like this
Linear Mode
