Python: Maximum recursion depth error

Question

I am having a problem with 'Maximum recursion depth exceeded' in python
I converted a java(I dont know java so it wasn't easy) function to python function and it did work for small lists but when I use large lists I get that error. I tried to do sys.setrecursionlimit(10000) but it seem that there is a problem because it will not finish, maybe because I converted the java code to python in a wrong way.

this is the python code of the function

def fun(a, b):
    inf = 10000
    c=[]
    boolean = [[0 for x in xrange(len(b))] for x in xrange(len(a))]
    dp = [[inf for x in xrange(len(b))] for x in xrange(len(a))]

    def maxMatching(i, j):
        if i == -1:
            return 0
        if j == -1:
            return inf
        if dp[i][j] != inf:
            return dp[i][j]
        val1 = maxMatching(i, j - 1)
        val2 = abs(a[i] - b[j]) + maxMatching(i - 1, j - 1)
        if cmp(val1, val2) > 0:
            dp[i][j] = val2
            boolean[i][j] = True
        else:
            dp[i][j] = val1
        return dp[i][j]

    def add_to_list(i, j):
        if i == -1 or j == -1:
            return
        if boolean[i][j]:
            c.append(b[j])
            add_to_list(i - 1, j - 1)
        else:
            add_to_list(i, j - 1)

    maxMatching(len(a) - 1, len(b) - 1)
    add_to_list(len(a) - 1, len(b) - 1)
    return sorted(c, reverse=True)

a=[20, 19, 13]
b=[21, 20, 14, 11, 5]
c=fun(a, b)

assert c == [21, 20, 14]

the function should return a list from list b which are the nearest points from list a I thought that convert this function to iterative will resolve the problem.
my question is , how to make that function 100% iterative instead of recursive ? thanks

Hans Then · Accepted Answer · 2014-05-10 12:01:39Z

1

To remove the recursion, you need to make your functions iterative.

For add to list, this is easy. Something like this should work.

def add_to_list(i, j):
    while i != -1 and j == -1:
        if boolean[i][j]:
            c.append(b[j])
            i = i - 1
            j = j - 1
        else:
            j = j - 1

For maxMatching, this is also possible, but it takes some more work. However, do you notice that your recursion builds the dp table from top left to bottom right? And that you use the values of the dp to calculate the value maxMatching more to the right and to the bottom?

So what you can do is to create a helper table (like dp and boolean) and construct that from top to bottom and left to right. For each of the cells you calculate the value based on the values as you would now, but instead of using recursion, you use the value from the helper table.

This method is called Dynamic Programming, which is building a solution based on the solutions of smaller problems. Many problems that can be defined using some form of mathematical resursion can be solved using Dynamic Programming. See http://en.wikipedia.org/wiki/Dynamic_programming for more examples.

edited May 10, 2014 at 12:01

answered May 10, 2014 at 7:46

Hans Then

11.4k3 gold badges36 silver badges52 bronze badges

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

5 Comments

user2776193 Over a year ago

I will try your solution now, I didn't do any functional programming language classes before, I learned python in internet

user2776193 Over a year ago

that didn't solve the problem, because the error is maximum recursion depth exceeded in val1 = maxMatching(i, j - 1) so I think that maxMatching(i, j) function should be converted to iterative

Hans Then Over a year ago

Yes, I missed that you had recursion in that function too. I will look at the second function.

user2776193 Over a year ago

thanks for Dynamic Programming link, I will read it and try to understand it even that I think this beyond my capabilities :(

Hans Then Over a year ago

Try it, I gave some direct pointers inside my answer. If you get stuck further down the road, show us what you have tried.

Collectives™ on Stack Overflow

Python: Maximum recursion depth error

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related