counter in recursiv function

Question

I have the following recursiv function in python:

def _floodfill(matrix, x, y, counter):
    if matrix[x][y] != 9:
        matrix[x][y] = 9
        counter += 1
        # recursively invoke flood fill on all surrounding cells:
        if x > 0:
            counter += int(_floodfill(matrix, x - 1, y, counter) or 0)
        if x < len(matrix) - 1:
            counter += int(_floodfill(matrix, x + 1, y, counter) or 0)
        if y > 0:
            counter += int(_floodfill(matrix, x, y - 1, counter) or 0)
        if y < len(matrix[0]) - 1:
            counter += int(_floodfill(matrix, x, y + 1, counter) or 0)
        return counter

I want to count how often this function is called respectively count how many numbers are != 9 in the region. Using he following matrix and invocing the function like: _floodfill(matrix,1,1,0) the function should return 2:

[[9,9,9],
 [9,2,9],
 [9,3,9],
 [9,9,9]]

what's the problem with my code?

EDIT I think the function is more readable like this:

def _floodfill(matrix, x, y, counter):
    if matrix[x][y] != 9:
        matrix[x][y] = 9
        counter += 1
        # recursively invoke flood fill on all surrounding cells:
        if x > 0:
            counter += _floodfill(matrix, x - 1, y, counter)
        if x < len(matrix) - 1:
            counter += _floodfill(matrix, x + 1, y, counter)
        if y > 0:
            counter += _floodfill(matrix, x, y - 1, counter)
        if y < len(matrix[0]) - 1:
            counter += _floodfill(matrix, x, y + 1, counter)
        return counter
    else:
        return 0

Did you test it? I doubt you can get the correct counts like that. In most cases, you return counter; then you use this return value in a counter += _floodfill(...). So, counter at least doubles with each recursive call. — Stef
– Stef, Commented Dec 9, 2021 at 18:36

Stef · Accepted Answer · 2021-12-09 18:50:24Z

Three remarks:

You don't need to pass counter down to your recursive calls. What would they need it for? counter holds the number of cells previously visited. Your recursive calls don't need to know how many cells you have already visited. That information moves the other way around: what you want is for your recursive calls to tell you how many cells they visit.
It's much easier to write the function and use the function if all branches in an if/else have a consistent return value. If the function sometimes returns the number of visited cells, but sometimes returns None, it will be super inconvenient to use; notice how you had to add int(...) or 0 after every recursive call to fix that issue.
The way your matrix is stored as a list of lists, it makes more sense to me to index the rows with y and the columns with x than the other way around.

def _floodfill(matrix, y, x):
    if matrix[y][x] == 9:
        return 0
    else:
        matrix[y][x] = 9
        counter = 1
        if x > 0:
            counter += _floodfill(matrix, y, x - 1)
        if x < len(matrix) - 1:
            counter += _floodfill(matrix, y, x + 1)
        if y > 0:
            counter += _floodfill(matrix, y - 1, x)
        if y < len(matrix[0]) - 1:
            counter += _floodfill(matrix, y + 1, x)
        return counter

mat = [
 [9,9,9],
 [9,2,9],
 [9,3,9],
 [9,9,9]
]

c = _floodfill(mat, 1, 1)
print(c)
print(mat)

# 2
# [[9, 9, 9], [9, 9, 9], [9, 9, 9], [9, 9, 9]]

Z Li · Accepted Answer · 2021-12-09 18:00:58Z

1

Use a list to save the counter as int are passed by value:

def _floodfill(matrix, x, y, counter):
    if matrix[x][y] != 9:
        matrix[x][y] = 9
        counter[0] += 1
        # recursively invoke flood fill on all surrounding cells:
        if x > 0:
            _floodfill(matrix, x - 1, y, counter)
        if x < len(matrix) - 1:
            _floodfill(matrix, x + 1, y, counter)
        if y > 0:
            _floodfill(matrix, x, y - 1, counter)
        if y < len(matrix[0]) - 1:
            _floodfill(matrix, x, y + 1, counter)
        return counter
    else:
        return 0

_floodfill([[9,9,9],
            [9,2,9],
            [9,3,9],
            [9,9,9]], 1, 1, [0])

answered Dec 9, 2021 at 18:00

Z Li

4,3381 gold badge7 silver badges21 bronze badges

1 Comment

Stef Over a year ago

Using a list with one single element to emulate a "mutable int" is a bit hacky and makes the code really hard to understand.

Collectives™ on Stack Overflow

counter in recursiv function

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related