Python: Depth First Search 'maximum recursion depth exceeded'

Question

I have a recursive depth first search algorithm which takes in a black/white mask image, e.g.:

And outputs the x largest clusters of white pixels in that mask, e.g. (for x = 2):

The function is below:

def split_mask_into_x_biggest_clusters(input_mask, x):
    def generate_neighbours(point):
        neighbours = [
            (1, -1), (1, 0), (1, 1),
            (0, -1), (0, 1),
            (1, -1), (1, 0), (-1, 1)
        ]
        for neigh in neighbours:
            yield tuple(map(sum, zip(point, neigh)))

    def find_regions(p, points):
        reg = []
        seen = set()

        def dfs(point):
            if point not in seen:
                seen.add(point)
                if point in points:
                    reg.append(point)
                    points.remove(point)
                    for n in generate_neighbours(point):
                        dfs(n)

        dfs(p)
        return reg

    region = []
    data = np.array(input_mask)[:, :, 0]
    wpoint = np.where(data == 255)
    points = set((x, y) for x, y in zip(*wpoint))

    while points:
        cur = next(iter(points))
        reg = find_regions(cur, points)
        region.append(reg.copy())

    areas = {idx: area for idx, area in enumerate(map(len, region))}
    areas = sorted(areas.items(), key=lambda x: x[1], reverse=True)
    num = x

    masks = []
    for idx, area in enumerate(areas[:num]):
        input_mask = np.zeros((512, 512, 3))
        for x, y in region[area[0]]:
            input_mask[x, y] = [255, 255, 255]
        input_mask = input_mask.astype(np.uint8)
        masks.append(Image.fromarray(input_mask))

    return masks

My problem is that when I run it I get the following error: maximum recursion depth exceeded. Experimentally, I have tried increasing the recursion limit to 2000 then to 10000(!):

sys.setrecursionlimit(10000)

This fixes the problem sometimes but not all the time (i.e. not when the clusters of white pixels are bigger).

What can I do to fix this problem? Thank you for any help.

Answer 1

For big images you will always end up with this error.

You can either change you implementation to iterative DFS (which doesn't use recursion), or use BFS.

UPD

Implementation can be found here (for iterative DFS)

BFS implementation