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

    Join Date
    Dec 2012
    Posts
    6
    Rep Power
    0

    Question 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. #2
  3. 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?)
  4. #3
  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
    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
  6. #4
  7. 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.)
  8. #5
  9. 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
  10. #6
  11. 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.
  12. #7
  13. 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.
    thanks for your help
  14. #8
  15. 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?
  16. #9
  17. 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
  18. #10
  19. 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
  20. #11
  21. 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

    Comments on this post

    • portcitysoftwar disagrees
  22. #12
  23. 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.

IMN logo majestic logo threadwatch logo seochat tools logo