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
