Python递归中可变对象与不可变对象的行为差异探究

嘿，我来帮你把DFS递归里可变和不可变参数的行为差异讲明白！这确实是递归里很容易踩坑的点，尤其是处理像visited这种跟踪状态的变量时。

1. 可变对象场景（visited 为 list） #

因为list是可变对象，当你把它作为参数传入递归函数时，所有递归调用共享的是同一个list的引用——也就是说，你在某一层递归里修改它（比如append），所有其他引用这个list的地方都会看到变化。

举个代码例子：

def dfs(node, visited=[]):
    visited.append(node)
    # 假设递归终止条件是收集3个节点
    if len(visited) == 3:
        return visited
    return dfs(node + 1, visited)

print(dfs(1))  # 输出: [1, 2, 3]

返回结果：最终得到的是一个累积了所有递归步骤节点的列表，因为每一层递归都在同一个list上做修改，没有创建新的对象。

2. 不可变对象场景（visited 为 tuple） #

tuple是不可变对象，你无法直接修改它的内容——每次“修改”其实都会创建一个新的tuple。所以当你把tuple作为递归参数时，每一层递归拿到的都是一个全新的对象，不会和其他递归栈的参数互相干扰。

代码示例：

def dfs(node, visited=()):
    # 创建新的tuple，原tuple不受影响
    visited = visited + (node,)
    if len(visited) == 3:
        return visited
    return dfs(node + 1, visited)

print(dfs(1))  # 输出: (1, 2, 3)

返回结果：虽然最终也是累积的节点序列，但每一层递归的visited都是独立的。如果你的DFS有分支（比如遍历图的多个邻接节点），不同分支的visited不会互相污染，这在需要跟踪多条独立路径时特别有用。

3. 模糊场景（visited 为 list，易踩坑的情况） #

这个场景通常是指没有正确处理可变list参数导致的意外行为，最常见的就是使用可变对象作为函数默认参数，或者在递归分支中共享同一个list却没做隔离。

比如这个容易踩坑的代码：

def dfs(node, visited=[]):
    if node in visited:
        return
    visited.append(node)
    # 递归遍历相邻节点（这里用+1和-1模拟）
    dfs(node + 1)
    dfs(node - 1)

# 第一次调用
dfs(1)
# 第二次调用，默认参数的list已经被上次调用修改过了！
dfs(0)
print(visited)  # 输出可能是 [1,2,3,0,-1,-2,...]，完全不符合预期

返回结果：因为默认参数的list是函数定义时创建的全局对象，多次调用函数会复用同一个list，导致状态混乱；如果是在多分支递归中，同一个list会被所有分支修改，导致无法正确跟踪单条路径的节点。

本质总结 #

• 可变对象（list、dict等）：传递的是对象引用，递归中修改会影响所有引用该对象的地方，适合需要全局共享状态的场景，但要注意分支污染的问题。
• 不可变对象（tuple、str、int等）：传递的是对象引用，但修改会创建新对象，每个递归栈的参数都是独立的，适合需要跟踪独立路径状态的场景。

内容的提问来源于stack exchange，提问作者GabrielChu