Python 中用于递归的可变对象与不可变对象

Question

这个问题的灵感来自阅读 Edd Mann's post on DFS。

据我所知，如果一个可变对象作为函数参数传递，它的值适应递归调用；而如果将不可变对象作为函数参数传递，则其值固定到每个递归调用。

让我举一些例子来说明我的意思，假设输入是

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

可变大小写 visited 是 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]

不可变大小写 visited 是 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,)

不明确的大小写 visited 是 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]

正如您所观察到的，对于模棱两可的情况，可变 list 对象被传递给递归调用，但答案与可变情况下的答案不同。我怀疑这是因为 list 是通过函数参数而不是函数体传递的。

我希望有人能在这两方面帮助我，解释一下幕后发生的事情：

Python 递归
仅可变：通过函数参数传递与通过函数体传递

Answer 1

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

不，这是因为您传递的是从列表添加中创建的新列表，您没有引用它。

在最初的情况下，列表被扩展 in-place（通过 +=），这样在所有递归调用结束时，您的列表将收集所有递归调用的结果。将分配给可变对象的变量视为对内存中某个 expandable/reducible 对象的引用更容易。
```
>>> l = []
>>> id(l)
4317346848
>>> l += [2]
>>> id(l)
4317346848 # same list
```
在不可变的情况下，为每个 'in-place' += 操作创建一个新的元组对象（在这种情况下不是这样）。递归调用的结果收集在全新的元组中，与根调用中的结果无关。这就是为什么您只能从第一个函数调用 (1,).
获得结果的原因
```
>>> c = tuple()
>>> id(c)
4316020816
>>> c += (2,)
>>> id(c)
4317473616 # new tuple
```
模棱两可的情况与第二种情况类似，创建的列表是一个新列表（visited + [neighbor]），与原始的 visited 列表几乎没有关系递归的根调用。
```
>>> id(l+[2])
4317534832 # new list
```

Python 中用于递归的可变对象与不可变对象

Mutable versus Immutable objects for recursion in Python

recursion

immutability

python-3.x