Ways to reduce recursion depth in Python

Question

I am currently making a program which makes use of floodfill recursion (such as filling a white circle with black borders into a different color). When I click on my image to floodfill, only part of the circle will get filled into the different color, then I get the Recursion Error. The only part of my code that has recursion is this.

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

Do you check that you don't "ping pong" between two values? When you floodfill(1, 1) this will call floodfill(2, 1) which will call floodfill(1, 1) which will... If you have no infinite recursion either try raising the recursion limit or implement it in a more direct way, i.e. instead of calling the function write the arguments in a list and use while list: args = list.pop(); f(*args) or something like that (which is basically dynamic programming). — syntonym
– syntonym, Commented Jun 17, 2018 at 16:42
@syntonym I'm fairly new to recursion, how would I check that they don't ping pong? — Jay Klope
– Jay Klope, Commented Jun 17, 2018 at 16:45
@BrettCommandeur I purposely left that out because I'm using a program called SimpleGraphics, which a lot of people here don't use, so the coding will look unfamiliar. — Jay Klope
– Jay Klope, Commented Jun 17, 2018 at 16:46
@JayKlope you can print coordinates of processed pixel. Here your flood fill will process, for example, 0,0; 1,0; then, after some time, return back to 0,0 via second floodfill call, and bounce around that way — Andrew Morozko
– Andrew Morozko, Commented Jun 17, 2018 at 17:03

Martijn Pieters · Accepted Answer · 2018-06-17 16:59:51Z

You do so by not using recursion; you'd run into the recursion limit for circles with a radius matching the recursion limit, which defaults to 1000, and the limit can't arbitrarily be raised. Use an iterative approach instead. You can do so here with a queue:

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.

I used a set to track what coordinates have not yet been handled here; there may be simpler way for your application to do the same (like simply testing that the floodfill colour is already applied to that pixel).

You also would test for the boundary conditions in the same if test location. If the pixel is already black there, you'd also ignore those coordinates.

Collectives™ on Stack Overflow

Ways to reduce recursion depth in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related