Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
December 1st, 2012, 07:16 PM
 arira
Registered User

Join Date: Dec 2012
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

#2
December 1st, 2012, 10:01 PM
 Lux Perpetua
Contributing User

Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,939
Time spent in forums: 1 Month 1 Week 3 h 27 m 29 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?)

#3
December 2nd, 2012, 07:48 AM
 arira
Registered User

Join Date: Dec 2012
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

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
December 2nd, 2012, 01:37 PM
 Lux Perpetua
Contributing User

Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,939
Time spent in forums: 1 Month 1 Week 3 h 27 m 29 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:
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
December 2nd, 2012, 06:44 PM
 arira
Registered User

Join Date: Dec 2012
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: 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
December 2nd, 2012, 09:28 PM
 Lux Perpetua
Contributing User

Join Date: Feb 2004
Location: San Francisco Bay
Posts: 1,939
Time spent in forums: 1 Month 1 Week 3 h 27 m 29 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.

#7
December 3rd, 2012, 05:05 AM
 arira
Registered User

Join Date: Dec 2012
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.

#8
December 6th, 2012, 07:15 AM
 arira
Registered User

Join Date: Dec 2012
Posts: 6
Time spent in forums: 2 h 3 m 52 sec
Reputation Power: 0
I sent an email to writer of the book that I found this problem in it and he answered me:

Quote:
 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
December 11th, 2012, 02:49 AM
 Cyril22
Registered User

Join Date: Dec 2012
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

#10
December 11th, 2012, 07:50 AM
 arira
Registered User

Join Date: Dec 2012
Posts: 6
Time spent in forums: 2 h 3 m 52 sec
Reputation 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
January 4th, 2013, 09:41 PM
 wsmmwx
Permanently Banned

Join Date: Nov 2012
Posts: 2
Time spent in forums: 7 m 58 sec
Warnings Level: 10
Number of bans: 1
Reputation 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
March 5th, 2013, 01:45 AM
 RobertWoges
Permanently Banned

Join Date: Jan 2013
Location: New York
Posts: 32
Time spent in forums: 6 h 14 m 48 sec
Warnings Level: 10
Number of bans: 1
Reputation Power: 0
Actually i dont know how to calculate this one.But really its very interesting.

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Calculate recursive calls number