Python - understand the scope of the variable pass to a recursive function

Question

I have a recursive function with an array as the parameter that stores the path as I travel a grid, from (0, 0) to (x, y), and I have to skipped some points that are defined as "unavailable"

I implement my function like this

unAvailablePoint = [(1, 2), (3, 0), (0, 3), (2, 3), (0, 1)]

def steppable(point):
    return point not in unAvailablePoint

def travel(x, y, path, visited):
    if x >= 0 and y >= 0 and steppable((x, y)):
        if (x, y) in visited:
            return visited[(x, y)]
        success = False
        if (x, y) == (0, 0) or travel(x-1, y, path, visited) or travel(x, y-1, path, visited):
            path = path + [(x, y)] #the path will remain empty even after the recursive call have done some changes to the path
            success = True
        visited[(x, y)] = success
        return success
    return False

path = []
visited = {}
travel(3, 3, path, visited)
print(path) //[]

As I print out the path at the end, it seems the path is still empty. This is not what I expected as a Python novice. Any suggestion would be helpful

Well, your travel function returns only True/False, so path changes stay in scope of that recursion step. — Fejs
– Fejs, Commented Nov 24, 2016 at 6:55
It's this is different in Java, which allows you to modify the parameter as the recursive step goes. As it back tracks, the caller should be able to get the updated value for the parameter that pass to the children recursive step? — Kesong Xie
– Kesong Xie, Commented Nov 24, 2016 at 7:00

omri_saadon · Accepted Answer · 2016-11-24 07:18:38Z

3

Try to append to the path and not initialize it every iteration of the recursion:

path.append( (x,y) ) #the path will remain empty even after the recursive call have done some changes to the path

instead of:

path = path + [(x, y)] #the path will remain empty even after the recursive call have done some changes to the path

This way, you are not initialize the list each iteration, so it will not be a local variable to the function.

edited Nov 24, 2016 at 7:18

answered Nov 24, 2016 at 6:58

omri_saadon

10.7k8 gold badges36 silver badges58 bronze badges

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

4 Comments

Kesong Xie Over a year ago

It works. But why will we re-initialize the list as we use path = path + [(x, y)]?

omri_saadon Over a year ago

Because the path = path + [(x, y)] is in the function, when you did this you made path as a local variable to the travel function. when you use append, you make sure that path is not initialized inside the function so he will not be a local variable to the function. @KesongXie

MarianD Over a year ago

Another solution: path += [(x, y)]

Kesong Xie Over a year ago

I see. I think the difference why path = path + [(x,y)] won't work while path += [(x,y)] should fully depend on how the + and += operator being overloaded. The first one should return a new list object, why the second one would modify the existing path variable.

Collectives™ on Stack Overflow

Python - understand the scope of the variable pass to a recursive function

1 Answer 1

4 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Related