如何递归扩展路径列表并获取所有关联引用？

问题描述 #

我有一个paths列表，需要对列表中的每个路径调用GetReferences()获取引用，再对这些引用递归调用GetReferences()直到没有新引用出现，最终返回初始路径加上所有递归引用的完整列表。

举个例子：A引用B，B引用C和D，初始paths只有A。最终要返回[A, B, C, D]。

现有代码存在问题：用了全局变量导致重复处理，没做去重引发无限循环（比如A和B互相引用的情况），而且递归方式在路径极大会导致栈溢出，无法满足内存和时间效率要求。

解决方案 #

用迭代+集合去重的方式实现，既避免无限循环，又保证效率：

def fetch_all_references(initial_paths):
    # 用集合存已处理的路径，避免重复处理（O(1)查询效率）
    processed = set(initial_paths)
    # 用队列存待处理的路径，广度优先遍历
    queue = list(initial_paths)
    
    while queue:
        current_path = queue.pop(0)  # 从队列头部取元素，FIFO保证广度优先
        try:
            refs = GetReferences(current_path)
            for ref in refs:
                if ref not in processed:
                    processed.add(ref)
                    queue.append(ref)
        except Exception:
            # 处理单个路径获取引用失败的情况，不影响整体流程
            pass
    
    # 把集合转成列表返回，顺序和遍历顺序一致
    return list(processed)

代码说明 #

1. 去重机制：用set存储已处理的路径，每次获取新引用时先检查是否已处理，避免重复调用GetReferences()，同时防止循环引用导致的无限循环。
2. 迭代而非递归：用队列实现广度优先遍历，避免递归深度过大导致的栈溢出问题，更适合处理极大规模的路径列表。
3. 异常处理：单个路径获取引用失败时跳过，不中断整个流程。
4. 效率优化：如果处理超大规模数据，推荐用collections.deque优化队列操作，让头部弹出元素的时间复杂度从O(n)降到O(1)：

优化后的代码：

from collections import deque

def fetch_all_references(initial_paths):
    processed = set(initial_paths)
    queue = deque(initial_paths)
    
    while queue:
        current_path = queue.popleft()
        try:
            refs = GetReferences(current_path)
            for ref in refs:
                if ref not in processed:
                    processed.add(ref)
                    queue.append(ref)
        except Exception:
            pass
    
    return list(processed)

内容的提问来源于stack exchange，提问作者YSLBeezy