So I’m trying to create a flood fill algorithm and I keep getting a recursion error with this. The algorithm seems to have infinite recursion and I cannot pinpoint why. I have looked all over the internet and I cannot find a solution as it seems like my program is correct according to most sources. There seems to be something wrong however. This is the edited version of the code. The error message is still maximum recursions.
Can I get some help?
from PIL import Image, ImageTk from random import * w= 75 h= w flood = Image.new("RGB", (w,h), (0,0,0)) x = 0 y = 0 count = 0 colorlist = [] i = 0 while x < w -1: y = 0 while y < h-1: r = random() if r < .25: flood.putpixel((x,y), (0,0,0)) else: flood.putpixel((x,y), (255,255,255)) y += 1 x += 1 x = 0 y = 0 while x < w-1: y = 0 while y < h-1: r = random() if x == 0 or y == 0 or x == w-1 or y ==h-1: flood.putpixel((x,y), (0,0,0)) y += 1 x += 1 def floodfill(x,y, d,e,f, g,h,i, image, count): count+=1 (a,b,c) = image.getpixel((x,y)) if (a,b,c) == (255,255,255): (j,k,l) = image.getpixel((x-1,y)) (m,n,o) = image.getpixel((x+1, y)) (p,q,r) = image.getpixel((x,y-1)) (s,t,u) = image.getpixel((x,y+1)) if count > 990: return if (a,b,c) == (255,255,255): image.putpixel((x,y), (g,h,i)) floodfill(x-1, y, d,e,f, g,h,i, image, count) floodfill(x+1, y, d,e,f, g,h,i, image, count) floodfill(x, y-1, d,e,f, g,h,i, image, count) floodfill(x, y+1, d,e,f, g,h,i, image,count) floodfill(2,2, 0,0,0,255,0,0,flood, 0) flood.save("flood.png") print("done")
Advertisement
Answer
Python has a tendency to throw a maximum recursion depth exceeded
error, even if the algorithm doesn’t recurse infinitely and would eventually halt on its own. There are two solutions to this: increase the recursion limit, or switch to an iterative algorithm.
You can raise your recursion limit with sys.setrecursionlimit
. Choose a number higher than the worst-case recursion depth of your algorithm. In your case, that would be the number of pixels in your image, length * height
.
Changing your algorithm into an iterative one is fairly simple, since it doesn’t really matter in what order you paint the pixels, as long as you get them all at least once. A set
is very well suited to holding unique non-ordered data, so let’s use that to store the pixels we need to paint.
def floodFill(x,y, d,e,f, g,h,i, image): toFill = set() toFill.add((x,y)) while not toFill.empty(): (x,y) = toFill.pop() (a,b,c) == image.getpixel((x,y)) if not (a,b,c) == (255, 255, 255): continue image.putpixel((x,y), (g,h,i)) toFill.add((x-1,y)) toFill.add((x+1,y)) toFill.add((x,y-1)) toFill.add((x,y+1)) image.save("flood.png")
If you do use the iterative method, be sure to put bound checking in it. Otherwise, it might run forever! Or at least until your hard drive is filled by one gigantic toFill
set.