使用BFS生成树时递归调用陷入死循环，求解决思路

• 已访问集合传递方式错误：如果递归时直接传递同一个已访问集合的引用，而非为每个分支创建独立副本，会导致回溯时无法正确恢复访问状态。比如某个分支标记位置A为已访问，递归返回后未移除标记，其他分支会误以为A不可走；或者不同分支互相干扰，重复处理同一位置，最终陷入循环。正确做法是每次递归调用时传递已访问集合的副本（复制当前集合后再添加当前节点位置），确保各分支访问记录互不影响。

• BFS与递归逻辑冲突：BFS是层级遍历的广度优先策略，而递归天然是深度优先（DFS）执行方式。如果getMoves递归逻辑未严格按层级推进——比如处理单个节点时直接递归到深层，而非处理完当前层级所有节点再进入下一层——很容易出现重复遍历同一层级节点的情况，进而引发死循环。用递归实现BFS需额外维护层级信息，确保每一轮递归只处理当前层级的所有节点，再统一进入下一层。

• 已访问集合更新时机错误：如果生成子节点后才将当前节点加入已访问集合，会导致递归过程中再次回到当前节点。正确顺序是：进入当前节点时，先将其加入已访问集合，再生成所有合法子节点（过滤已访问和棋盘外位置），最后递归处理子节点。

• 递归终止条件缺失：除找到目标位置的情况，还要考虑“当前层级无可行走子节点”的终止条件。如果某个分支已无路可走，但递归函数未判断该情况并返回，可能会在空节点上反复递归，导致死循环。

以下是逻辑修正的伪代码示例：

def bfs_recursive(current_level, visited, target):
    # 终止条件1：找到目标路径
    for node in current_level:
        if node.pos == target:
            return node.path
    # 终止条件2：当前层级无节点，无路可走
    if not current_level:
        return None
    # 准备下一层级节点
    next_level = []
    for node in current_level:
        # 复制已访问集合，避免分支间干扰
        new_visited = visited.copy()
        new_visited.add(node.pos)
        # 生成合法子节点（过滤已访问和棋盘外位置）
        for move in generate_knight_moves(node.pos):
            if move not in new_visited and is_on_board(move):
                next_level.append(TreeMoves(pos=move, path=node.path + [move]))
    # 递归处理下一层级
    return bfs_recursive(next_level, new_visited, target)

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