递归函数的优化调用栈

Question

我有一个可以生成相邻成员的节点，通过

node.create_adj_list()

，我需要用递归函数处理树或图，但我对内存效率有一些疑问。每个节点都有一个我需要收集的解决方案列表。

说我有这段代码，一个DFS搜索：

total_solutions = []

def handle_node(node):
  for solution in find_solutions(node):
    total_solutions.append(solution)
  for adj_node in node.create_adj_list():
    handle_node(adj_node)

如果我在父节点上调用

handle_node

，据我所知会发生什么：

1. 我们的父节点存在于内存中
2. 我们为该节点生成解决方案
3. 我们生成相邻节点的存在性，将它们存储在内存中
4. 我们以 DFS 方式向下递归树

如果我们的树是这样的：

     O
    / \
   O   O
  / \
 O   O

当我们递归遍历树时，我们从树的最左边部分开始，然后向下进行 DFS。但是当我们沿着这个分支向下移动时，我们也从那个分支生成每个节点的子节点，并将它们存储在内存中。这是否意味着我们在内存中存储 O(m*n)，其中

m

是树的深度，

n

是孩子的平均数量？

这看起来效率很低，因为我们不需要将所有这些子节点存储在内存中，我们应该只能够将深度存储在内存中。

我应该如何解决这种情况，使我的代码不会在内存中存储不必要的东西？

我最初的想法是

create_adj_list()

方法可能不好。