Python递归深度超限问题：Tkinter油漆程序洪水填充优化求助

问题场景 #

• 为Tkinter迷你油漆程序实现洪水填充（flood fill）功能，小画布上填充正常，但大画布触发RecursionError: maximum recursion depth exceeded in __instancecheck__错误
• 尝试通过sys.setrecursionlimit增大递归深度，但仍会在递归深度约990时报错

核心问题 #

递归版洪水填充的调用深度受限于Python默认递归栈大小，即使手动调整上限，也存在栈溢出风险，且Python本身不支持尾递归优化，无法从根本上解决大区域填充的问题。

解决方案 #

1. 替换为迭代版洪水填充（推荐）

用栈（深度优先）或队列（广度优先）模拟递归过程，彻底避开递归深度限制。以下是修改后的flood_fill方法：

def flood_fill(self, col, row, old_color, new_color):
    if old_color == new_color:
        return  # 避免无意义重复填充
    
    # 用栈存储待填充的坐标对（深度优先，和原递归逻辑一致）
    stack = [(col, row)]
    
    while stack:
        current_col, current_row = stack.pop()
        
        # 边界检查和颜色匹配检查
        if (current_col < 0 or current_col >= blocks 
            or current_row < 0 or current_row >= blocks):
            continue
        if self.field[current_row][current_col] != old_color:
            continue
        
        # 更新颜色并绘制块
        self.field[current_row][current_col] = new_color
        self.create_block(current_col*block_size, current_row*block_size, 
                          block_size, self.color_case(new_color))
        
        # 将相邻坐标加入栈
        stack.append((current_col + 1, current_row))
        stack.append((current_col - 1, current_row))
        stack.append((current_col, current_row + 1))
        stack.append((current_col, current_row - 1))

可选优化：如果想要从点击位置向外扩散的平滑填充效果，可改用队列实现广度优先遍历，只需将栈替换为collections.deque，并把pop()改成popleft()：

from collections import deque

def flood_fill(self, col, row, old_color, new_color):
    if old_color == new_color:
        return
    
    queue = deque([(col, row)])
    
    while queue:
        current_col, current_row = queue.popleft()
        
        if (current_col < 0 or current_col >= blocks 
            or current_row < 0 or current_row >= blocks):
            continue
        if self.field[current_row][current_col] != old_color:
            continue
        
        self.field[current_row][current_col] = new_color
        self.create_block(current_col*block_size, current_row*block_size, 
                          block_size, self.color_case(new_color))
        
        queue.append((current_col + 1, current_row))
        queue.append((current_col - 1, current_row))
        queue.append((current_col, current_row + 1))
        queue.append((current_col, current_row - 1))

2. 修复代码中的小问题

原代码中flood_fill方法误用全局变量color，应该改为使用参数new_color，否则填充颜色会不符合预期。

修改后的完整代码 #

import tkinter as tk
from random import randint, seed
from collections import deque

# 全局变量
blocks = 100
block_size = 5
res = (block_size*blocks,)*2
color = 'a'
color_dict = {}

class MainWindow(tk.Tk):
    def __init__(self):
        super().__init__()
        self.resizable(False,False)
        self.c = tk.Canvas(self, width=res[0], height=res[1], highlightthickness=0, bg='white')
        self.c.grid(sticky='w')
        self.title('Main Window')
        self.bind("<Key>", self.key_handler)
        self.bind("<B1-Motion>", self.left_click)
        self.bind("<Button-1>", self.left_click)
        self.bind("<B3-Motion>", self.right_click)
        self.bind("<Button-3>", self.right_click)
        self.field = [[0]*blocks for i in range(blocks)]
        self.is_flood_fill = False

    def create_block(self, x, y, size, fill='white'): 
        self.c.create_rectangle(x,y,x+size,y+size,fill=fill,outline='')

    def key_handler(self, event):
        print(event.keycode)
        match event.keycode:
            case 82: self.is_flood_fill = not self.is_flood_fill
    
    def left_click(self, event):
        if self.is_flood_fill:
            col,row = self.get_field_pos(event.x, event.y)
            self.flood_fill(col, row, self.field[row][col], color)
        else: 
            self.draw(event.x, event.y, color)

    def right_click(self, event): 
        self.draw(event.x, event.y, 0)

    def draw(self, cursor_x, cursor_y, color):
        col,row = self.get_field_pos(cursor_x, cursor_y)
        if self.field[row][col] != color:
            try:
                self.field[row][col] = color
            except Exception as e:
                print(e)
            self.create_block(col*block_size, row*block_size, block_size, self.color_case(color))

    def get_field_pos(self, x, y): 
        return (round(x/block_size), round(y/block_size))

    def color_case(self, code):
        if code == 0: 
            return 'white'
        elif code not in color_dict:
            seed(code)
            r = lambda: randint(0,255)
            color_dict[code] = '#%02X%02X%02X' % (r(),r(),r())
        return color_dict[code]

    # 迭代版洪水填充（深度优先）
    def flood_fill(self, col, row, old_color, new_color):
        if old_color == new_color:
            return
        
        stack = [(col, row)]
        
        while stack:
            current_col, current_row = stack.pop()
            
            if (current_col < 0 or current_col >= blocks 
                or current_row < 0 or current_row >= blocks):
                continue
            if self.field[current_row][current_col] != old_color:
                continue
            
            self.field[current_row][current_col] = new_color
            self.create_block(current_col*block_size, current_row*block_size, 
                              block_size, self.color_case(new_color))
            
            stack.append((current_col + 1, current_row))
            stack.append((current_col - 1, current_row))
            stack.append((current_col, current_row + 1))
            stack.append((current_col, current_row - 1))

if __name__ == "__main__":
    app = MainWindow()
    app.mainloop()

内容的提问来源于stack exchange，提问作者TheVorkMan