CODEWITHSUNDEEP
pythonpython-2.7recursioniteration
user2776193
user2776193

Reputation: 103

Python: Maximum recursion depth error

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

Upvotes: 3

Views: 296

Answers (1)

Hans Then
Hans Then

Reputation: 11322

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.

Upvotes: 1

Related Questions