Python recursively adding to a class variable gives different results

user_12328503 0
Viewed 56
class Perimeter:
    def __init__(self):
        super().__init__()
        self.count = 0
        self.grid = [[0, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
        self.seen = set()

    def perimeter_calculator(self, x: int, y: int) -> int:

        if self.grid[x][y] == 0:
            print(f"count: {self.count}")
            return 1

        if (x, y) not in self.seen:
            self.seen.add((x, y))

            a = self.perimeter_calculator(x + 1, y)
            b = self.perimeter_calculator(x - 1, y)
            c = self.perimeter_calculator(x, y + 1)
            d = self.perimeter_calculator(x, y - 1)

            self.count += a + b + c + d
        return 0

if __name__ == "__main__":
    perm = Perimeter()
    perm.perimeter_calculator(1, 1)
    print(perm.count)
    assert perm.count == 8

I'm working on leetcode problem 463 "Island Perimeter" (https://leetcode.com/problems/island-perimeter/) and noticed some "Python" behavior I cannot explain when using a class variable.

The above function creates a simple 4x4 grid with a 2x2 island in the middle. We start the search at (1, 1) and it should give 8 as the perimeter of that island. If I run it like above everything is fine and the function returns 8 as expected.

If, however, I change the recursive call like so:

      self.count += self.perimeter_calculator(x + 1, y)
      self.count += self.perimeter_calculator(x - 1, y)
      self.count += self.perimeter_calculator(x, y + 1)
      self.count += self.perimeter_calculator(x, y - 1)

self.count is two in the end and somehow decreases within the recursive call (which can be seen with the print output).

Why is the result different when assigning the result of self.perimeter_calculator() directly to self.count instead of using the local variables a, b, c, and d as temporary storages? What is Python "doing under the hood"?

recursion class scope python variables
1 Answers

As @ThierryLathuille mentioned in the Python chat: https://chat.stackoverflow.com/transcript/message/54642897#54642897 the problem results from the way Python assigns values to the class variables when calling functions. Here is a simpler example from @Kevin highlighting that issue:

class Fred:
    def __init__(self):
        self.value = 0
    def f(self):
        self.value += self.h()
        print(self.value)
    def g(self):
        x = self.h()
        self.value += x
        print(self.value)
    def h(self):
        self.value += 1
        return 2

Fred().f() #2
Fred().g() #3

When calling f(), we add to the value self.value had before calling h()

When calling g(), we use the value it had after calling h()

When doing this recursively (as in the original example), I assume that Python overwrites the value within a deeper call stack, even leading to "decreasing" values of self.count.

Thank you @ThierreLathuille and @Kevin!

user_123285030
Related