Return 递归中间步骤的值

Question

得到了一个简单的脚本，旨在确定 x 和 y 之间的路径是否存在。

通过实现，我想检索一些中间值，但在递归调用中迷失了方向。基本上，有人可以帮助区分这两种实现之间的区别吗？为什么他们提供不同的 returns?

快速说明：唯一的区别是标志部分。

# i.e., adj: {1: {2}, 2: {1, 3}, 3: {2, 5}, 4: {5}, 5: {3, 4}, 11: {12}, 12: {11, 15}, 15: {12}}

实施 1

def dfs(adj, x, y, visited=None, flag=[]):
    if visited is None:
        visited = set()
    if x == y:
        flag.append(True)
    if x not in visited:
        visited.add(x)
    for neigh in adj[x]:
        if neigh not in visited:
            dfs(adj, neigh, y, visited, flag)

    return flag

现在：

dfs(adj, 1, 5)

Returns:

[True]

实施 2

def dfs(adj, x, y, visited=None, flag=False):
    if visited is None:
        visited = set()
    if x == y:
        flag = True
    if x not in visited:
        visited.add(x)
    for neigh in adj[x]:
        if neigh not in visited:
            dfs(adj, neigh, y, visited, flag)

    return flag

和：

dfs(adj, 1, 5)

Returns:

False

已编辑

感谢您的回答，我相信它解决了递归调用的参数重置问题。但是对于问题的另一面，我仍然需要一些帮助，即递归调用何时覆盖参数的值并沿途继承到顶部？

让我用上面的例子来详细说明。以下结果是从调试 implementation 1 和 implementation 2 中跟踪的一些 print，根据其完成时间排序。

Intermediate_func       Implementation1   Implementation2    
dfs(adj, 4, 5)           [True]           True  
dfs(adj, 5, 5)           [True]           True  
dfs(adj, 3, 5)           [True]           False  
dfs(adj, 2, 5)           [True]           False 
dfs(adj, 1, 5)           [True]           False

观察到 [True] 一直被复制到 dfs(adj, 1, 5)。按照执行顺序(Implementation 1)，dfs(adj, 1, 5)、dfs(adj, 2, 5)和dfs(adj, 3, 5)被初始化为[]，直到看到dfs(adj, 5, 5)。不知何故，来自 dfs(adj, 5, 5) 的 [True] 值被保留并传递给 dfs(adj, 1, 5)。为什么不能将 Implementation 2 中的 True 值复制到 dfs(adj, 1, 5)？

Answer 1

永远不要使用可变的默认参数。 Python 只创建一次函数对象。这意味着 flag=[] 仅创建一次并使用所有对 dfs 的调用。

将您的第一个实现更改为：

def dfs(adj, x, y, visited=None, flag=None):
    flag = []
    if visited is None:
        visited = set()
    if x == y:
        flag.append(True)
    if x not in visited:
        visited.add(x)
    for neigh in adj[x]:
        if neigh not in visited:
            dfs(adj, neigh, y, visited, flag)

    return flag

现在：

dfs(adj, 1, 5)

Returns:

[]

所以问题是保持 True（实现 1）与重置每个（递归）函数（实现 2）的 False 的列表。将列表重置为空列表会使两个实现等效。

如果要将信息移动到递归调用中，则需要移动返回的标志：

def dfs(adj, x, y, visited=None, flag=False):
    if visited is None:
        visited = set()
    if x == y:
        flag = True
    if x not in visited:
        visited.add(x)
    for neigh in adj[x]:
        if neigh not in visited:
            #  save returned flag here
            flag = dfs(adj, neigh, y, visited, flag)

    return flag

现在：

dfs(adj, 1, 5)

Returns:

True

Return 递归中间步骤的值

Return value of a intermediate step of a recursion

python

recursion

immutability

python-3.x

实施 1

实施 2