图论中的递归函数

Question

我最近读了一篇关于 NASA 代码质量规则的文章，其中一个规则是避免递归函数（理解和调试都很复杂）

当我处理如下图表时：

        O
        |
        0
       / \
      0.  0
     / \ / \
    0.  00. 0

我有节点，每个节点（可以）都有多个下一个节点。

当我编写一个函数来遍历这种图时，我通常会创建一个递归函数。 事实上，对于我正在经历的每个节点，我都会计算当前节点所需的内容，然后列出下一个节点并在其上调用我的函数。

这是一种深入的做法。

我想知道是否有一种方法可以通过避免递归来改进这种做法。

我尝试使用 X for 循环函数（然后 X 是最大深度），但它看起来我不太干净。

我考虑过 while 循环，但我通常会避免它。

Python 3.12中的示例：

我有一个与

下一个节点名称相关的节点名称的输入列表：

node_items = [
    {
        "node_name": "A",
        "next_node_names": [
            "B"
        ],
    },
    {
        "node_name": "B",
        "next_node_names": [
            "C", "D",
        ],
    },
    {
        "node_name": "C",
        "next_node_names": [
            "F"
        ],
    },
    ...
]

现在，我常用的递归函数（为了让我在函数中只有 1 个循环才能更清楚）是：

def my_recursive_func(current_node_name: str, node_list) -> str:
    # select the node in the list
    node = next(node for node in node_list if node["name"] == current_node_name)
    # computing something related to node
    output = ...
    # Running on next node 
    for next_node_name on node["next_node_names"]:
        output += my_recursive_function(current_node_name=next_node_name, node_list=node_list)
    return output

你有什么建议吗？

问候，

Answer 1

这很大程度上取决于您实际需要执行的处理类型。例如，如果遍历顺序与计算无关，您可以使用广度优先方法，使用 FIFO 队列。如果深度优先遍历是必要的，您可以实现显式堆栈。或者，如果计算是后序的，那么您可以首先识别树的叶子，对它们进行计算，然后从树中删除它们。然后重复新的一组叶子等。

关于您给出的代码，您应该避免这种情况：

node = next(node for node in node_list if node["name"] == current_node_name) 对节点列表的这种迭代会恶化算法的时间复杂度。相反，首先按节点名称键入数据结构，将其转换为

邻接列表数据结构。

你的例子——用“计算”具体化——然后变成：

def create_adj_list(items):
    adj = {}
    for obj in items:
        adj[obj["node_name"]] = obj["next_node_names"]
        for child in obj["next_node_names"]:
            if child not in adj:
                adj[child] = []
    return adj

def my_recursive_func(current_node_name: str, adj) -> str:
    # computing something related to node
    output = current_node_name + "("
    # Running on next node 
    for next_node_name in adj[current_node_name]:
        output += my_recursive_func(next_node_name, adj)
    return output + ")"


adj = create_adj_list(node_items)
res = my_recursive_func("A", adj)

如果你用显式堆栈来模仿这个，你可能会得到这样的结果：

def my_iterative_func(start_node: str, adj) -> str:
    stack = [[start_node, iter(adj[start_node]), start_node + "("]]
    while True:
        node, child_iter, result = stack[-1]
        child = next(child_iter, None)
        if child is not None:
            stack.append([child, iter(adj[child]), child + "("])
        else:
            stack.pop()
            result += ")"
            if not stack:
                return result
            stack[-1][2] += result