Why is my (local) variable behaving like a global variable?

Question

I have no use for a global variable and never define one explicitly, and yet I seem to have one in my code. Can you help me make it local, please?

def algo(X): # randomized algorithm
    while len(X)>2:
        # do a bunch of things to nested list X
    print(X) 
    # tracing: output is the same every time, where it shouldn't be.
    return len(X[1][1])

def find_min(X): # iterate algo() multiple times to find minimum 
    m = float('inf')
    for i in some_range:
        new = algo(X)
        m = min(m, new)
    return m

X = [[[..], [...]],
     [[..], [...]],
     [[..], [...]]]

print(find_min(X))
print(X) 
# same value as inside the algo() call, even though it shouldn't be affected.

X appears to be behaving like a global variable. The randomized algorithm algo() is really performed only once on the first call because with X retaining its changed value, it never makes it inside the while loop. The purpose of iterations in find_min is thus defeated.

I'm new to python and even newer to this forum, so let me know if I need to clarify my question. Thanks.

update Many thanks for all the answers so far. I almost understand it, except I've done something like this before with a happier result. Could you explain why this code below is different, please?

def qsort(X):
    for ...
        # recursively sort X in place
        count+=1 # count number of operations
    return X, count

X = [ , , , ]
Y, count = qsort(X)
print(Y) # sorted
print(X) # original, unsorted.

Thank you.

update II To answer my own second question, the difference seems to be the use of a list method in the first code (not shown) and the lack thereof in the second code.

Answer 1

As others have pointed out already, the problem is that the list is passed as a reference to the function, so the list inside the function body is the very same object as the one you passed to it as an argument. Any mutations your function performs are thus visible from outside.

To solve this, your algo function should operate on a copy of the list that it gets passed.

As you're operating on a nested list, you should use the deepcopy function from the copy module to create a copy of your list that you can freely mutate without affecting anything outside of your function. The built-in list function can also be used to copy lists, but it only creates shallow copies, which isn't what you want for nested lists, because the inner lists would still just be pointers to the same objects.

from copy import deepcopy

def algo (X):
    X = deepcopy(X)
    ...

Answer 2

When you do find_min(X), you are passing the object X (a list in this case) to the function. If that function mutates the list (e.g., by appending to it) then yes, it will affect the original object. Python does not copy objects just because you pass them to a function.

Answer 3

When you pass an object to a python function, the object isn't copied, but rather a pointer to the object is passed.

This makes sense because it greatly speeds up execution - in the case of a long list, there is no need to copy all of its elements.

However, this means that when you modify a passed object (for example, your list X), the modification applies to that object, even after the function returns.

For example:

def foo(x):
    x.extend('a')
    print x

l = []
foo(l)
foo(l)

Will print:

['a']

['a', 'a']

Answer 4

Python lists are mutable (i.e., they can be changed) and the use of algo within find_min function call does change the value of X (i.e., it is pass-by-reference for lists). See this SO question, for example.