Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite
1

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" in Python: 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?

share|improve this question
5  
Well, the mutable default argument again... –  Sven Marnach Jan 13 '12 at 16:04
 
Yes, nothing to do with recursive functions. –  Daniel Roseman Jan 13 '12 at 16:06
 
aha, thank you. –  Clyde Fare Jan 13 '12 at 16:06

marked as duplicate by Daniel Roseman, larsmans, Daenyth, Wooble, Toon Krijthe Jan 13 '12 at 21:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

up vote 4 down vote accepted

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".

share|improve this answer
up vote 3 down vote

@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.

share|improve this answer
 
its not recommended to use if stack == None, use if stack is None instead (more about it) –  juliomalegria Jan 13 '12 at 17:09
 
@julio, thanks. It's fixed now. Nice link too. I never thought of that :) –  FakeRainBrigand Jan 13 '12 at 17:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.