在 Python 中编写需要访问变量的递归方法的最有效方法是什么？

Question

我对 Python 还很陌生，想实现一些图算法只是为了练习。所以我以迭代和递归的方式实现了深度优先搜索，它们工作得很好。但是在我在网上找到的示例中，我看到了递归 DFS 的不同方法，这些方法似乎具有不同的内存使用情况。问题是总体上哪个更好。

我认为它们具有相同的时间复杂度，但我不知道如何衡量内存使用情况。其中之一应该符合python编程约定。

from collections import deque


class Graph:

    def __init__(self, n, vlist, directed=False):
        self.size = n
        self.adjlist = [[0 for _ in range(n)] for __ in range(n)]
        for x in vlist:
            self.adjlist[x[0]][x[1]] = 1
        if not directed:
            for x in vlist:
                self.adjlist[x[1]][x[0]] = 1

    # iterative DFS
    def idfs(self, start=0):
        discovered = [False for _ in range(self.size)]
        stk = deque()
        stk.append(start)
        while len(stk) > 0:
            v = stk.pop()
            if not discovered[v]:
                discovered[v] = True
                print(f"Discovered: {v}")
                for x in range(self.size):
                    if self.adjlist[v][x] == 1:
                        # print(f"x{x}")
                        stk.append(x)

    # recursive dfs style 1 with 2 methods
    def rdfs1(self, start=0):
        self.discovered = [False for _ in range(self.size)]
        self.rdfs1util()
        print("end")
        del(self.discovered)

    def rdfs1util(self, v=0):
        self.discovered[v] = True
        print(f"Discovered: {v}")
        for x in range(self.size):
            if self.adjlist[v][x] == 1:
                if not self.discovered[x]:
                    self.rdfs1util(x)

    # recursive dfs style 2
    def rdfs2(self, start=0):
        discovered = [False for _ in range(self.size)]

        def rdfsi(v):
            discovered[v] = True
            print(f"Discovered: {v}")
            for x in range(self.size):
                if self.adjlist[v][x] == 1:
                    if not discovered[x]:
                        rdfsi(x)
        rdfsi(start)
        print("end")

    # recursive dfs style 3
    def rdfs3(self, discovered, start=0):
        discovered[start] = True
        print(f"Discovered: {start}")
        for x in range(self.size):
            if self.adjlist[start][x] == 1:
                if not discovered[x]:
                    self.rdfs3(discovered, x)

    def bfs(self):
        pass

    def spf(self, vid):
        pass

    def view(self):
        for i in range(self.size):
            x = [j for j in range(self.size) if self.adjlist[i][j] > 0]
            if x is not None:
                print(str(i)+" : "+" ".join(map(str, x)))


######################
v = 8
e = [(0, 5), (5, 3),
     (0, 1), (1, 2), (6, 2), (0, 3), (2, 6), (3, 5), (3, 6), (4, 7)]
graph1 = Graph(v, e)
graph1.view()

print("iterative dfs:")
graph1.idfs()
print("__")
print("recursive dfs1:")
graph1.rdfs1()
print("__")
print("recursive dfs2:")
graph1.rdfs2()
print("__")
print("recursive dfs3:")
visits = [False for _ in range(v)]
graph1.rdfs3(visits)