Python pass by object reference value

Question

I'm trying to write an algorithm in python to print out all paths from the root of a (binary) tree to each leaf. Here's my code:

def fb_problem(node, curr_trav):
    curr_trav = curr_trav + [node]

    if node.left is None and node.right is None:
        for path_node in curr_trav:
            print path_node.data 
        print "XXX"

    if node.left is not None:
        fb_problem(node.left, curr_trav)
    if node.right is not None:
        fb_problem(node.right, curr_trav)

fb_problem(root, [])

I keep a list of nodes in the current traversal, and when I've reached a leaf, I print out the list. I'm misunderstanding something about the way python passes objects though. I thought that as each recursive call completes and is popped off the stack, the original curr_trav variable would not be affected by what the recursive call did. However, it seems as if the line

curr_trav += [node]

Is mutating the original list. The += operator returns a new list, as opposed to .append(), which actually mutates the original object. So shouldn't this call just be reassigning the name given to the object in the function, not mutating the original object? When I change the line to something like

t_trav = curr_trav += [node]

Everything works fine, but I don't understand what the problem with the original line was. Please let me know if my question is unclear.

Answer 1

Your understanding of += is not quite correct. All operators in Python are really just shortcuts. For example, a + b is a.__add__(b) if a has an __add__ method. If a does not, it is b.__radd__(a). If b doesn't have that method, an error is raised. Usually, a += b behaves quite like a = a + b, but in the case of mutable objects, it usually doesn't. That is because a += b is a.__iadd__(b) if a has the __iadd__ method. If a does not, it is the same as a = a.__add__(b). If a doesn't have that either, it is the same as a = b.__radd__(a). Since lists do have the __iadd__ method, the actual list object is changed instead of redefining curr_trav.

Answer 2

With python it is neither by value or reference. It is a combination of both, and depends on the type of object being passed into the function. For example if a mutable type such as dict, list etc is passed in it will pass the reference. Whereas with a immutable type such as a str it will be by value. A good read on this subject is by Jeff Knupp.

The issue with your original code curr_trav += [node] is that it is adding the values of [node] to curr_trav and setting the reference to the new list. Because it passes the reference for curr_trav it will be changed through each subsequent iteration.