Python class scope lost in nested recursion function

Question

When I attempted to write a recursive nested function within a python class, every time the recursive function completed and returned back to the first function my class property reverted back to the original state.

def main():
    input = [
        [1,3,1],
        [1,5,1],
        [4,2,1]
    ]
    sln = Solution()
    sln.findPath(input)
    print("Output: " + str(sln.minPathSum))
    print(*sln.minPath, sep = "->")

class Solution():
    minPath = []
    minPathSum = None
    grid = []

    def findPath(self, grid):
        self.minPath = []
        self.minPathSum = None
        self.grid = grid
        self.recurse(0,0,[])

    def recurse(self, xCoord, yCoord, currentPath):
        if(len(self.grid) <= yCoord):
            return
        if(len(self.grid[yCoord]) <= xCoord):
            return

        currentValue = self.grid[yCoord][xCoord]
        currentPath.append(currentValue)

        if(len(self.grid) - 1 == yCoord and len(self.grid[yCoord]) - 1 == xCoord):
            currentPathSum = sum(currentPath)
            if(self.minPathSum == None or currentPathSum < self.minPathSum):
                self.minPathSum = currentPathSum
                self.minPath = currentPath
        else:
            #right
            self.recurse(xCoord + 1, yCoord, currentPath)
            #down
            self.recurse(xCoord, yCoord + 1, currentPath)

        currentPath.pop()
        return

if __name__ == "__main__":
    main()

Running this results in:

Output: 7

Debugging the code within VSCode does indicate that self.minPath is getting set within the recurse function; however, it appears to be losing scope to the original class instance.

In addition I attempted to recreate the same nested situation with separate code and ended up with the following.

def main():
    tst = ScopeTest()
    tst.run()
    print(*tst.tstArray)
    print(tst.tstNumber)

class ScopeTest():
    tstArray = []
    tstNumber = 0

    def run(self):
        self.otherFunc()

    def otherFunc(self):
        self.tstArray = [1,2,3,4,5]
        self.tstNumber = 7

if __name__ == "__main__":
    main()

The above did return the expected outcome which leads me to think this has something to do with the recursion.

Just a heads up, I'm fairly new to python so I may be making a rookie mistake, but I can't seem to figure out why this is happening.

Given a M x N grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. — Justin Palagi
– Justin Palagi, Commented Aug 25, 2021 at 16:43

quamrana · Accepted Answer · 2021-08-25 16:44:09Z

1

Your recurse() method is generating a currentPath parameter and when this is deemed to be correct you execute: self.minPath = currentPath. Unfortunately, you just reference the same object as currentPath which is later mutated.

Your line should be: self.minPath = currentPath[:]

You then see some contents in self.minPath

Mandatory link to Ned Batchelder

Also you can remove these lines:

minPath = []
minPathSum = None
grid = []

from just below class Solution():

answered Aug 25, 2021 at 16:44

quamrana

39.6k13 gold badges57 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Justin Palagi Over a year ago

That makes sense! So essentially every time I was popping an item off of currentPath I was also popping off of self.minPath. Just needed a second set of eyes. Thank you for the answer!

Collectives™ on Stack Overflow

Python class scope lost in nested recursion function

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related