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, Dec 06 '14 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, Dec 06 '14 at 11:23

score 1 · Accepted Answer · edited Apr 13 '17 at 12:19

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 '17 at 12:19

Community

1
1

answered Dec 06 '14 at 12:33

manlio

18,345
14
76
126

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? – Train Heartnet Dec 06 '14 at 14:33
1

You can increase the maximum depth of the Python call stack by calling [sys.setrecursionlimit](https://docs.python.org/2/library/sys.html#sys.setrecursionlimit). Also take a look at http://stackoverflow.com/questions/2917210/python-what-is-the-hard-recursion-limit-for-linux-mac-and-windows and http://stackoverflow.com/questions/3323001/maximum-recursion-depth – manlio Dec 06 '14 at 15:56

Coding a recursive function on Python 3.0

1 Answers1