Python递归生成全排列时append路径结果全部相同是什么原因？

你给出的递归全排列代码如下：

res = []
A = [1,2,3]

def permute(idx, path):
    if idx >= len(A):
        # base case
        print(path)
        res.append(path)
        return 
    for i in range(idx, len(A)):
        path[i],path[idx] = path[idx], path[i]
        permute(idx+1, path)
        path[i],path[idx] = path[idx], path[i]

permute(0,A)
print(res)

• Python中列表属于可变对象，代码中所有递归分支操作的path都是指向初始A列表内存地址的同一个引用，没有生成新的列表对象。
• 触发base case时print(path)输出的是当前时间点该内存地址上的列表内容，所以能看到正确的排列结果。
• 直接执行res.append(path)时，存入res的只是path的内存引用，并不是当前列表的快照。后续回溯过程中对path的交换修改会同步影响所有已经存入res的引用指向的内容。等递归完全结束后，path会被回溯为初始的[1,2,3]，所以res中所有引用最终都指向这个内容。
• 你修改为res.append(list(path))或者res.append(path[:])后，相当于在base case触发时创建了当前path的浅拷贝，生成了新的独立的列表对象存入res，后续对原path的修改不会影响这些已经存入的拷贝，因此结果正常。

• 优先用回溯模式（原地修改+操作后回滚状态）：你当前使用的「交换元素→递归→回滚交换」的写法就是最优实践，不需要每次递归都传递新的完整列表，所有操作都在同一个可变对象上完成，仅在需要持久化存储结果（也就是base case存入结果列表）时做一次拷贝即可，相比每次递归传新列表的写法，能大幅减少不必要的内存开销和对象创建耗时。
• 避免滥用全局变量存储结果：可以将结果列表作为递归函数的入参传递，或者用嵌套闭包的方式封装递归逻辑，外层函数初始化结果列表后返回，避免全局变量被其他逻辑意外修改，示例写法如下：

def permute(arr):
    res = []
    def backtrack(idx):
        if idx >= len(arr):
            res.append(arr.copy())
            return
        for i in range(idx, len(arr)):
            arr[i], arr[idx] = arr[idx], arr[i]
            backtrack(idx+1)
            arr[i], arr[idx] = arr[idx], arr[i]
    backtrack(0)
    return res

print(permute([1,2,3]))

• 如果不需要极致的性能，也可以在递归传参时直接生成新列表，省去回滚步骤，写法更简单不易出错，适合数据量小的场景：

def permute(arr, path=None):
    if path is None:
        path = []
    res = []
    if not arr:
        return [path]
    for i in range(len(arr)):
        res += permute(arr[:i] + arr[i+1:], path + [arr[i]])
    return res

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