Different behaviors of a Python list in a recursive function

Question

I'm learning to write recursive functions in Python, and find a list can have different behaviors depending on whether I choose to use res.append(new_loc) or res + [new_loc].

For example,

def solver(counter,res):
    
    print("Entering the solver:",res)
    if len(res) >= 4:return 
    counter += 1 

    res.append(counter) 

    solver(counter,res)
    print("inner solver returned:",res)
    counter += 1 
    res.append('haha%i'% counter)
   
solver(0,[])

This gives me the output

Entering the solver: []
Entering the solver: [1]
Entering the solver: [1, 2]
Entering the solver: [1, 2, 3]
Entering the solver: [1, 2, 3, 4]
inner solver returned: [1, 2, 3, 4]
inner solver returned: [1, 2, 3, 4, 'haha5']
inner solver returned: [1, 2, 3, 4, 'haha5', 'haha4']
inner solver returned: [1, 2, 3, 4, 'haha5', 'haha4', 'haha3']

The list res acts like a recorder, and saves all the values.

However, if I change the solver function a little bit

def solver(counter,res):
    
    print("Just entering the solver:",res)
    if len(res) >= 4:return 
    counter += 1 
    
    solver(counter,res+[counter])
    
    print("inner solver returned:",res)
    counter += 1 
    res.append('haha%i'% counter)
       
solver(0,[])

The output becomes

Just entering the solver: []
Just entering the solver: [1]
Just entering the solver: [1, 2]
Just entering the solver: [1, 2, 3]
Just entering the solver: [1, 2, 3, 4]
inner solver returned: [1, 2, 3]
inner solver returned: [1, 2]
inner solver returned: [1]
inner solver returned: []

In this case, why res.append('haha%i'% counter) is not working?

Does this answer your question? [Why can a function modify some arguments as perceived by the caller, but not others?](https://stackoverflow.com/questions/575196/why-can-a-function-modify-some-arguments-as-perceived-by-the-caller-but-not-oth) — Jan Wilamowski, Jan 06 '22 at 02:41

shriakhilc · Accepted Answer · 2022-01-06T03:24:54.630

res + [counter] creates a new list and you are not assigning that to res, just passing it as a method parameter. Even though res is mutable, this operation does not mutate the original object.

Each recursive method call has a separate list, which is why the "entering" print statement is fine, but the "inner" statement doesn't have the correct values. The modifications were not passed back up the chain.

On the other hand, using append() or extend() will mutate the original object. As seen in the docs about Mutable Sequence operations, res += [counter] would be the equivalent to extend(), because it reassigns the new list to res.

An easy way to visualize this is to test the value of your original list after the call:

inp_list = []
solver(0, inp_list)
print(inp_list)

Output 1 will be [1, 2, 3, 4, 'haha5', 'haha4', 'haha3', 'haha2'] because all your methods modify the same list, the one that you originally passed. This will work with append(), extend() and +=.

Output 2 will be ['haha2'], because only your initial solver() call modifies this list. The recursive calls do not affect it at all.

Different behaviors of a Python list in a recursive function

1 Answers1