I have problem with recursion depth in Python. I want to know how to make it efficient or replace it, or make recursion depth larger.
I tried make it larger by sys.setrecursionlimit, but no result. It's stopping on 990 every time.
Basicly, I making flood fill for my mini-paint program on Tkinter.
On small fields it's fill prefectly fine, but on larger there error RecursionError: maximum recursion depth exceeded in __instancecheck__
Also, there code:
import tkinter as tk
from random import randint, seed
# don't mind me about these global vars
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)
# b-motion is when holding button and moving
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
# creating block
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=False if self.is_flood_fill else True
# left click handler
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)
# right click handler
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: print(self.field[row][col]);self.field[row][col] = color; print(self.field[row][col])
except Exception: pass; print(Exception)
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)))
# grabing color from dict, or generating if it's not there and puting in same dict
def color_case(self, code):
global color
if code == 0: return 'white'
elif not code in color_dict:
# seed of random by code
seed(code)
# generating hex color
r = lambda: randint(0,255)
color_dict[code] = '#%02X%02X%02X' % (r(),r(),r())
return color_dict[code]
# main problem is there
def flood_fill(self,col,row,old_color,new_color):
# checks
if col < 0 or col >= blocks or row < 0 or row >= blocks: return
if self.field[row][col] != old_color: return
self.field[row][col] = new_color
self.create_block(col*block_size, row*block_size, block_size, self.color_case(color))
# attempt to fill the neighboring positions
self.flood_fill(col+1, row, old_color, new_color)
self.flood_fill(col-1, row, old_color, new_color)
self.flood_fill(col, row+1, old_color, new_color)
self.flood_fill(col, row-1, old_color, new_color)
if __name__ == "__main__":
app = MainWindow()
app.mainloop()
You could convert the use of recursion into using an explicit stack (list). Secondly, you should skip the whole thing when the old and new color are equal, as otherwise you'll keep running in circles and eventually run out of memory.
def flood_fill(self, col, row, old_color, new_color):
if old_color == new_color:
return
stack = [(col, row)]
while stack:
col, row = stack.pop()
if 0 <= col < blocks and 0 <= row < blocks and self.field[row][col] == old_color:
self.field[row][col] = new_color
self.create_block(col*block_size, row*block_size, block_size, self.color_case(color))
stack.extend([(col+1, row), (col-1, row), (col, row+1), (col, row-1)])