python 的 visual studio 调试器中的递归堆栈帧具有相同的值

Question

我试图在 python 中对我制作的图 class 进行深度优先递归搜索。由于某些未知原因，我未能通过断言级别的测试：AssertionError: None not found in [[1, 2, 4, 6], [1, 2, 4, 7, 6]]，我理解该错误的含义，我不打算直接询问算法，而是询问我注意到的其他事情。

使用 VS Code python 调试器，我决定检查运行中的代码，我注意到每次新调用都会将新堆栈帧推入堆栈（见图），它们共享相同的值'visited'（集合）和 'path'（列表）实例（完全出乎意料且令人困惑）。我添加了一个 callnumber 虚拟变量作为健全性检查，以确保我正确使用了调试器，我做到了。

我不知道为什么我没有早点抓住它，特别是因为我一直在用 C 和内存管理做很多事情。这些对象显然被放在堆上并通过引用传递，因此并不是真正独立的实例，对吧？

有什么方法可以制作这些基于堆栈的变量吗？我知道不推荐这样做，因为存在堆栈溢出的风险（没有双关语）并且不能很好地使用 space.

既然我明白了发生了什么，我想知道你是否有一些关于我如何使这个算法运行的指示（这次是双关语），因为这种方法因为它是基于堆的而不起作用？我不需要解决它，只是一些提示或线索，可以产生更深层次思考的东西。

顺便说一句，我一直在努力提高阅读和理解文档的能力。实际上，我喜欢将文档作为我的第一个访问对象，但是当我 google 为 python 做一些事情时，与其他语言不同，它们总是接近随机教程的底部。我刚才去了官方 page on built in types 并搜索了诸如堆或内存之类的词 for list 和 dict ，但我没有找到任何地方解释这些对象存在的位置，它们如何增长或调整大小等，尽管它可能非常明显对于有经验的程序员来说是隐含的，但无论如何这是我的代码

class Graph:
    def __init__(self):
        self.vertices = {}
    def add_vertex(self, vertex_id):
        self.vertices[vertex_id] = set()
    def add_edge(self, v1, v2):
        self.vertices[v1].add(v2)
    # more functions

    def dfs_recursive(self, starting_vertex, destination_vertex, visited = set(), path=[]):
        """
        Return a list containing a path from
        starting_vertex to destination_vertex in
        depth-first order.

        This should be done using recursion.
        """
        result = None
        path.append(starting_vertex)
        visited.add(starting_vertex)
        if starting_vertex == destination_vertex:
            return path
        for neighbor in self.vertices[starting_vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                result = self.dfs_recursive(neighbor, destination_vertex, visited, path, callnumber+1)
        return result

编辑：由于 rioV8 的输入解决了算法。这是我的代码

    def dfs_recursive(self, starting_vertex, destination_vertex, visited = None, path=None, callnumber=1):

        path = path or []
        visited = visited or set()
        path.append(starting_vertex)
        visited.add(starting_vertex)
        if starting_vertex == destination_vertex:
            return path
        for neighbor in self.vertices[starting_vertex]:
            if neighbor not in visited:
                result = self.dfs_recursive(neighbor, destination_vertex, visited.copy(), path[:], callnumber+1)
                if result is not None and result[-1] == destination_vertex:
                    return result
        return None

Answer 1

不要使用可修改对象作为函数默认参数。

它们是在函数编译时创建的，而不是在函数调用时创建的。并在每次调用时重复使用。

使用 None 并在函数内部创建可修改对象。

并在递归调用时复制可修改项。

def dfs_recursive(self, starting_vertex, destination_vertex, visited=None, path=None):
    visited = visited or set()
    path = path or []
    # rest of function
    result = self.dfs_recursive(neighbor, destination_vertex, visited.copy(), path[:], callnumber+1)

python 的 visual studio 调试器中的递归堆栈帧具有相同的值

Recursive stacks frames have identical values in visual studio debugger for python

python

debugging

callstack

visual-studio-code