Python递归错误范围错误：超出了最大调用堆栈大小

Question

使用Python2.7，我试图编写一个代码来递归地替换二维列表中的元素。以下是函数的代码片段：

import sys
sys.setrecursionlimit(10000)

def assimilate(population, x, y, influence):
    """Replace adjacent list elements recursively with -1 if cell is 
    lesser than the adjacent influenced cell.

    Keyword arguments:
    population -- 2D list of integers
    x -- x-coordinate of influencing cell
    y -- y-coordinate of influencing cell
    influence -- value of influencing cell

    Returns:
    Modified population list.
    """

    if population[y][x] <= influence:
        population[y][x] = -1
    if population[y][x] == -1:
        # Check adjacent cells
        if y - 1 > 0:
            if population[y - 1][x] <= influence:
                population = assimilate(population, y - 1, x, influence)
        if x + 1 < len(population):
            if population[y][x + 1] <= influence:
                population = assimilate(population, y , x + 1, influence)
        if y + 1 < len(population):
            if population[y + 1][x] <= influence:
                population = assimilate(population, y + 1, x, influence)
        if x - 1 > 0:
            if population[y][x - 1] <= influence:
                population = assimilate(population, y, x - 1, influence)
    return population

该代码的目标是将相邻的列表元素（上、下、左、右、无对角线）替换为-1，如果其值小于或等于influence。它需要迭代，直到范围内所有可能的单元格都被转换。在

例如：

^{pr2}$

在代码中，输入5到influence会导致错误的输出，而增加influence的值会导致RuntimeError: maximum recursion depth exceeded（通过添加import sys和sys.setrecursionlimit(10000)或{}来修正。在

三个问题：

• 递归的实现有什么问题？在
• 有没有更好的方法在检查相邻值的同时遍历列表？在
• 有什么可能解决这个错误？在

递归不是强制性的，可以使用其他替代方法。我尝试使用while循环，但它仍然有错误的输出。我尽量不使用第三方软件包。在

Answer 1

这不是Python的问题，而是一个逻辑错误。在

这里的逻辑有问题（以及其他类似的地方）

if population[y][x] <= influence:

    population[y][x] = -1

比如说

population[3][2] = -1

一。现在，在递归过程中，当程序

population[3][1] , it will see that it's adjacent cell > (population[3][2])

小于影响值。如果影响是积极的，它将永远是真实的。因此，它将再次到达已访问过一次的>；population[3][2]单元格。因此递归调用将变得无限大。在

要检查此项，可以按如下方式更改行：

if population[ y ][ x ] <= influence and population[ y ][ x ] != -1 : population[y][x] = -1

请告知这个解决方案是否有效。你必须在if条件的每个地方改变这个逻辑

当它访问一个单元格并使其为-1时，它将不再访问该单元格并停止递归。我实现了这个，递归停止了。但这也有一个问题。如果有效值为-1的单元格被大于influence的值包围，则永远不会访问该单元格。在

考虑以下示例：

influence=5

[ 9, 9, 2 ]
[ 9, 9, 9 ]
[ 9, 9, 9 ]

在本例中，如果只使用-1检查，则永远不会访问2的单元格。因为，2被9包围，而9永远不会被-1取代。在

为了解决这个问题，我们需要另一个数组来跟踪访问。数组将初始化为0。如果一个单元格已经被访问，那么它的值将为1，并且将永远不会再访问该单元格。在

检查下面的代码。它工作正常。在

^{pr2}$

输出：

[[-1, -1, -1], [8, -1, -1], [6, 7, -1]]