Python DFS 递归函数保留上一次调用的值

Question

如果标题有误导性，我很抱歉，但我无法以任何其他方式表达。
我正在尝试实现 bfs 和 dfs 以记住一些概念，但是代码的递归版本会出现奇怪的行为。

这是正在发生的事情：

def rec_dfs(g, start_node, visited=[]):
    visited.append(start_node)
    for next_node in g[start_node]:
        if next_node not in visited:
            rec_dfs(g, next_node, visited)
    return visited

graph2={'A': ['B', 'C', 'D'],
       'B': ['A', 'E', 'F'],
       'C': ['A', 'F'],
       'D': ['A'],
       'E': ['B'],
       'F': ['B', 'C']}

rec_dfs(graph2, "A") #['A', 'B', 'E', 'F', 'C', 'D']               OK
rec_dfs(graph2, "A") #['A', 'B', 'E', 'F', 'C', 'D', 'A']          NOK
rec_dfs(graph2, "A") #['A', 'B', 'E', 'F', 'C', 'D', 'A', 'A']     NOK

它应该总是 return 第一种情况，但是当我调查时我可以看到第二个调用已经 "visited" 填充。

如果我像这样调用函数：

rec_dfs(graph2, "A", []) #['A', 'B', 'E', 'F', 'C', 'D']  OK
rec_dfs(graph2, "A", []) #['A', 'B', 'E', 'F', 'C', 'D']  OK
rec_dfs(graph2, "A", []) #['A', 'B', 'E', 'F', 'C', 'D']  OK

它工作得很好...
如果有人能解释为什么会发生这种行为，以及是否有办法避免这种情况，我将不胜感激。

谢谢！

Answer 1

您正在使用 visited 数组作为可变默认参数，根据 http://code.activestate.com/recipes/577786-smarter-default-arguments/.

，它在定义时基本上只初始化为一个空数组一次

在每次后续调用 rec_dfs() 期间，如果 visited 数组未明确重新初始化，它将在后续每次函数调用期间保持其状态。

Python DFS 递归函数保留上一次调用的值

Python DFS recursive function retaining values from previous call

python

recursion

graph

breadth-first-search

microsoft-distributed-file-system