CODEWITHSUNDEEP
pythonrecursionscope
Justin Palagi
Justin Palagi

Reputation: 23

Python class scope lost in nested recursion function

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.

Upvotes: 1

Views: 101

Answers (1)

quamrana
quamrana

Reputation: 39414

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():

Upvotes: 1

Related Questions