### Thread: Calculate recursive calls number

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
6
Rep 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
2. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1313
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?)
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
6
Rep Power
0
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

Code:
```(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
(7,0)=15
(7,1)=57
(7,2)=127
(7,3)=197
(7,4)=239
(7,5)=253
(7,6)=255
(8,0)=17
(8,1)=73
(8,2)=185
(8,3)=325
(8,4)=437
(8,5)=493
(8,6)=509
(8,7)=511```
(numbers is recursive calls numbers)
I couldn't find anything from this numbers
4. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1313
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:
Code:
```(0,-1) (0,0) (0,1) (0,2) (0,3)
(1,-1) (1,0) (1,1) (1,2) (1,3)
(2,-1) (2,0) (2,1) (2,2) (2,3)   (etc.)
(3,-1) (3,0) (3,1) (3,2) (3,3)

(etc.)```
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
6
Rep Power
0
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:
Code:
```(0,-1) (0,0) (0,1) (0,2) (0,3)
(1,-1) (1,0) (1,1) (1,2) (1,3)
(2,-1) (2,0) (2,1) (2,2) (2,3)   (etc.)
(3,-1) (3,0) (3,1) (3,2) (3,3)

(etc.)```
I tried every thing for 3 day
searched in the net and ask everyone I know
now I think maybe there is not a formula
6. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,939
Rep Power
1313
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.
7. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
6
Rep Power
0
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.
8. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
6
Rep Power
0
I sent an email to writer of the book that I found this problem in it and he answered me:

Hint: calculate the number of calls for some small values of N and k and consider functions that involve N! (N factorial) and k! (k factorial).
does anyone have any idea?
9. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
1
Rep 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
10. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
6
Rep Power
0
I think formula is something like 2*n+X+1
it works if k=0
(1,0)=2*1+1=3
(2,0)=2*2+1=5
(5,0)=2*5+1=11

but when k is not zero it is different and I think X is related to k
11. No Profile Picture
Permanently Banned
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
2
Rep Power
0

#### woman affiliated applause to grab for their Franch men pk Louis vuitton Bags

Tiffany & Co Outlet
Tiffany & Co Bracelets
Tiffany & Co Jewelry
Karen Millen Dress
Doudoune Moncler Pas Cher

• portcitysoftwar disagrees
12. No Profile Picture
Banned
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2013
Location
New York
Posts
28
Rep Power
0
Actually i dont know how to calculate this one.But really its very interesting.