Mutable versus Immutable objects for recursion in Python

Question

This question is inspired by reading Edd Mann's post on DFS.

As far as I can tell, if a mutable object is passed as a function parameter, its value is adaptive to recursive calls; while if an immutable object is passed as a function parameter, its value is fixed to every recursive call.

Let me get some examples to illustrate what I mean, suppose the input is

adj_list = {1: {2, 3}, 2: {1, 4}, 3: {1, 5}, 4: {2, 5}, 5: {3, 4}}

Mutable case visited is a list:

def dfs(adj_list, s, visited=None):
    if visited is None:
        visited = []
    visited += [s]
    for neighbor in adj_list[s]:
        if neighbor not in visited:
            dfs(adj_list, neighbor, visited)

    return visited

Returns:

[1, 2, 4, 5, 3]

Immutable case visited is a tuple:

def dfs(adj_list, s, visited=None):
    if visited is None:
        visited = tuple()
    visited += (s,)
    for neighbor in adj_list[s]:
        if neighbor not in visited:
            dfs(adj_list, neighbor, visited)

    return visited

Returns:

(1,)

Ambiguous case visited is a list:

def dfs(adj_list, s, visited=None):
    if visited is None:
        visited = [s]
    for neighbor in adj_list[s]:
        if neighbor not in visited:
            dfs(adj_list, neighbor, visited + [neighbor])

    return visited

Returns:

[1]

As you may observe, for the ambiguous case, mutable list object is passed along to recursive calls, but the answer wasn't the same as that in mutable case. I suspect it's because the list is passed via function parameter not the function body.

I was hoping someone could help me with these two aspects, explain a bit of what happened behind the scene:

• Mutable vs Immutable (parameter) for Python recursions
• Mutable only: passing via function parameters vs passing via function body

Answer 1

I suspect it's because the list is passed via function parameter not the function body.

No, it's because you're passing a new list created from the list addition, which you have no reference to.

1. In the original case, the list is extended in-place (via +=), such that at the end of all the recursive calls, your list would have collected the results from all the recursive calls. It is easier to think of a variable assigned to a mutable object as a reference to some expandable/reducible object in memory.

   >>> l = []
   >>> id(l)
   4317346848
   >>> l += [2]
   >>> id(l)
   4317346848 # same list
   

2. In the immutable case, a new tuple object is created for each 'in-place' += operation (not so in place in this case). The results of the recursive calls are collected in entirely new tuples, unrelated to that in the root call. That's why you only get the result from the first function call (1,).

   >>> c = tuple()
   >>> id(c)
   4316020816
   >>> c += (2,)
   >>> id(c)
   4317473616 # new tuple
   

3. The Ambiguous case is similar to the second in that, the list created is a new list (visited + [neighbor]) which has little to with the original visited list from the root call of your recursion.

   >>> id(l+[2])
   4317534832 # new list