Coding a recursive function on Python 3.0

Question

I'm trying to code the recursive function given in this answer (which unfortunately I can't post here due to the lack of LaTeX), in Python 3.0.

I'm new to coding and this is my attempt:-

def q(r,b,L):
    pr = r/(r+b)
    for k in range(1,L+1):
        for j in range(1,k):
            pr = pr * ((r-j)/(r+b-j)) * (b/r+b-j) * q(r-j,b-1,L)

    f = pr + ((b/(r+b)) * q(r,b-1,L))
    return f

But this is giving me a "division by zero" error for q(3,0,2). Could anyone help me with the code?

Thank you, I'll update my Python version. But I hardly think this is the problem here. The code seems to have a mistake somewhere. — Train Heartnet
– Train Heartnet, Commented Dec 6, 2014 at 11:12
No, I wasn't suggesting it was the problem. I can only suggest putting some print statements in to see the values at various points in the loops and at each recursion. — Daniel Roseman
– Daniel Roseman, Commented Dec 6, 2014 at 11:23

Community · Accepted Answer · 2017-04-13 12:19:19Z

1

I'm not sure yours is an exact translation of the function given in that answer.

It seems to me that it should be something like:

def q(r, b, L):
    s = 0

    for k in range(1, L+1):
        p = 1
        for j in range(0, k):
            p *= (r - j) / (r + b - j)

        s += p * b / (r + b - k) * q(r - k, b - 1, L)

    return b / (r + b) * q(r, b - 1, L) + s

But this recursive function definition is missing the base cases (meaning the inputs for which the function produces a result trivially, i.e. without recurring).

Here you only have the recursive cases (meaning the inputs for which the function calls itself).

You should add checks like:

if r <= L:
  return 1;

if b <= 0:
    return 0;

(this isn't enough)

edited Apr 13, 2017 at 12:19

CommunityBot

11 silver badge

answered Dec 6, 2014 at 12:33

manlio

19.1k14 gold badges83 silver badges139 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Train Heartnet Over a year ago

Thank you, this helped me a lot! :) Just a related question; for large values of r and b, the number of recursions are going to be alarmingly high. There has to be a "limit" to the number of recursions that can be performed (I think I read somewhere in terms of the terminology of maximum stack size, it is 5000). Do you know how I might be able to increase this limit?

manlio Over a year ago

You can increase the maximum depth of the Python call stack by calling sys.setrecursionlimit. Also take a look at stackoverflow.com/questions/2917210/… and stackoverflow.com/questions/3323001/maximum-recursion-depth

Collectives™ on Stack Overflow

Coding a recursive function on Python 3.0

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related