Python:最大递归深度错误

Question

我在 python 中遇到“超出最大递归深度”的问题
我将一个 java(我不知道 java，所以这并不容易)函数转换为 python 函数，它确实适用于小列表，但是当我使用大列表时，我得到了那个错误。我尝试执行 sys.setrecursionlimit(10000) 但似乎存在问题，因为它不会完成，可能是因为我以错误的方式将 java 代码转换为 python。

这是函数的python代码

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]

该函数应该从列表 b 中返回一个列表，该列表是列表 a 中最近的点我认为将此函数转换为迭代函数将解决问题。
我的问题是，如何使该函数 100% 迭代而不是递归？谢谢

Answer 1

要删除递归，您需要使您的函数迭代。

要添加到列表，这很容易。这样的事情应该有效。

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

对于 maxMatching，这也是可能的，但需要做更多的工作。但是，您是否注意到您的递归从左上角到右下角构建了 dp 表？并且您使用 dp 的值来计算更靠右和靠下的值 maxMatching？

所以您可以做的是创建一个辅助表(如 dp 和 boolean)并从上到下、从左到右构建它。对于每个单元格，您可以像现在一样根据这些值计算值，但您不使用递归，而是使用辅助表中的值。

这种方法称为动态规划，它是根据较小问题的解决方案构建解决方案。许多可以使用某种形式的数学回归定义的问题可以使用动态规划来解决。参见 http://en.wikipedia.org/wiki/Dynamic_programming更多示例。