组合模式中递归遍历要注意哪些问题？

简化版

组合模式常用递归遍历树结构，要注意递归深度、性能、重复计算、环形引用、父子关系一致性和异常节点处理。真实项目中大树遍历可能需要迭代写法、缓存、分页加载或环检测。

详细版

递归遍历常见风险：

树太深导致栈溢出；
节点太多导致遍历耗时高；
每次计算都递归，造成重复计算；
错误父子关系形成环；
删除或移动节点导致父子关系不一致；
遍历过程中修改 children 引发并发问题；
远程懒加载子节点导致 N+1 调用。

优化方式：

限制树深度；
用迭代遍历替代递归；
对统计结果做缓存；
构建树时做环检测；
大树分层加载；
明确遍历期间是否允许修改。

完整版教学

一、递归遍历为什么常见

组合模式的结构天然递归。

public void operation() {
    for (Component child : children) {
        child.operation();
    }
}

这种写法简单直观，非常适合树不深、节点不多的场景。

但工程里树可能很大，递归就会带来问题。

二、递归深度问题

如果树非常深：

A -> B -> C -> ... -> N

递归调用层数太多可能导致栈溢出。

这时可以用栈模拟递归：

Deque<Component> stack = new ArrayDeque<>();
stack.push(root);

while (!stack.isEmpty()) {
    Component node = stack.pop();
    node.operation();
    for (Component child : node.children()) {
        stack.push(child);
    }
}

迭代写法更适合极深树。

三、重复计算问题

例如目录大小：

root.size();

每次都递归计算所有子节点。

如果树很大，而且频繁调用 size()，性能会很差。

可以考虑缓存：

节点大小缓存
子节点变化时向上失效

但缓存会引入一致性问题，需要设计失效机制。

四、环形引用问题

理论上的树不应该有环。

但业务数据可能出错：

A 的父节点是 B
B 的父节点是 C
C 的父节点又是 A

递归遍历会无限循环。

构建树时要做环检测，遍历时也可以维护 visited 集合：

Set<Long> visited = new HashSet<>();

发现重复节点就终止或报错。

五、大树懒加载问题

有些树节点的 children 来自数据库或远程服务。

如果遍历时每个节点都查一次，就会出现 N+1 问题。

更好的方式可能是：

一次查出节点列表再组树；
按层批量加载；
前端分页展开；
对热点树做缓存。

组合模式不等于每次递归都实时查库。

六、常见误区与追问

遍历必须同时考虑深度、重复与环。链式深度达到10000层时递归调用可能栈溢出，应改用显式栈；DAG 中同一节点被两条路径引用时，要区分“按路径计算”还是“按节点去重”。检测环应使用当前递归路径集合，防止把合法共享误判为环。

检查维度	判定依据
路径集合	检测当前路径上的回边
全局 visited	避免重复处理，但会改变 DAG 语义

记忆钩子：先定义遍历语义——按节点、按边还是按路径——再选择 visited 策略。

误区：树结构永远不需要环检测。 外部数据或错误装配可能破坏树不变量。
追问：为什么显式栈更安全？ 它把深度存到堆结构中，可控制内存并避免调用栈上限。
误区：缓存子树结果一定正确。 结果若依赖访问者权限、路径或外部参数，缓存键必须包含这些上下文。
追问：懒加载遍历如何避免 N+1？ 批量预取相邻层或按分页边界加载，避免每个节点单独查询。
追问：遍历中节点修改怎么办？ 可采用快照、版本号或禁止并发修改，并明确一致性保证。

七、加强记忆

组合模式天然适合递归，但递归不是免费的。树深要防栈溢出，树大要防性能问题，数据异常要防环，频繁统计要考虑缓存，远程加载要防 N+1。

简化版

详细版