在Python中减少递归深度的方法

Question

我目前正在制作一个利用填充递归的程序(例如将带有黑色边框的白色圆圈填充为不同的颜色).当我点击我的图像进行填充时,只有部分圆圈会被填充到不同的颜色,然后我得到递归错误.我的代码中唯一有递归的部分就是这个.

def floodfill(x,y):
    floodfill(x+1,y)
    floodfill(x-1,y)
    floodfill(x, y+1)
    floodfill(x, y-1)

Answer 1

你不使用递归就可以了 ; 你会遇到半径与递归限制相匹配的圆的递归限制,默认为1000,并且不能任意提高限制.请改用迭代方法.你可以在这里使用队列:

from collections import deque

def floodfill(x, y, _directions=((-1, 0), (0, -1), (1, 0), (0, 1))):
    queue = deque([(r, c)])
    handled = {(r, c)}
    while queue:
        r, c = queue.popleft()
        for dr, dc in _directions:
            nr, nc = r + dr, c + dc
            if (nr, nc) not in handled:
                handled.add((nr, nc))
                queue.append((nr, nc))

                # do something with these coordinates, like filling
                # this position in an image.

我用一套来跟踪这里尚未处理的坐标; 您的应用程序可能有更简单的方法来执行相同操作(例如,仅测试泛光填充颜色已应用于该像素).

您还将在同一if测试位置测试边界条件.如果像素在那里已经是黑色,那么你也会忽略这些坐标.