Python functions and empty strings [duplicate]

Question

Possible Duplicate:
“Least Astonishment” in Python: The Mutable Default Argument

Edit: This has nothing to do with recusion and is merely the mutable default argument feature: "Least Astonishment" and the Mutable Default Argument

Many thanks

I'm using python 2.7.2 on a win7 64bit machine and have a recursive function that acts on an lxml element, the function looks like this:

def recursive_search(start, stack = []):
    for element in start.getchildren():
        if condition1(element):
            stack = recursive_search(element, stack)
        elif condition2(element)
            stack.append(element)
        else:
            pass
    return stack

When I call the function for the first time with:

output = recursive_search(starting_element)

It works fine and I get what I expect but if I call it again with precisely the same command I get twice what I expect, as if i've called:

output += recursive_search(starting_element)

or as if the stack were a global variable. If I call it a third time I get 3 times the output etc. etc.

If I call:

output = recursive_search(starting_element, [])

Then I can call this as many times as I like and I don't get the anomalous behavour.

Likewise if I modify the function such that it reads:

def recursive_search(start, stack = []):
    if stack == []:
        stack = []
    for element in start.getchildren():
        if condition1(element):
            stack = recursive_search(element, stack)
        elif condition2(element)
            stack.append(element)
        else:
            pass
    return stack

then I can call:

output = recursive_search(starting_point)

as many times as I like and again not get the anomalous behaviour.

My question is: what is going on - is this a bug or is there a rule I dont know about when passing empty strings into recursive functions in python?

Answer 1

When you use a mutable value for a default argument, you only get a single instance of that default. If your function modifies it, that's what will get passed on the next invocation of the function.

There's at least one reference to this in the Python documentation itself: http://docs.python.org/release/2.5.2/ref/function.html. See the section "Default parameter values are evaluated when the function definition is executed".

Answer 2

@Mark already explained it, so here's a solution.

def recursive_search(start, stack = None):
    if stack is None:
        stack = []
    for element in start.getchildren():
        if condition1(element):
            stack = recursive_search(element, stack)
        elif condition2(element)
            stack.append(element)
        else:
            pass
    return stack

The difference is when using a default parameter [] is evaluated once. When it's in the body of the function, a new list is created each call.

---

Some variations would be,

stack = stack or []

# or
if not stack: 
    stack = []

The difference is an empty list will always be replaced with a new list. This means if you pass a variable containing an empty list, the function will not change it when you use these variations.

When you compare it to None, it will only be replaced if stack contains None. I suppose this method is safer.