递归：从基础概念到供应链BOM和组织树处理

递归是一种函数直接或间接调用自身的编程方式。它适合处理天然具有层级结构的问题，例如树、目录、菜单、组织架构、BOM 物料清单。递归代码通常简洁，但如果缺少终止条件或层级过深，容易造成死循环或栈溢出。

整体流程

递归处理流程

递归的两个条件

写递归必须明确两个条件：

  1. 终止条件：什么时候停止继续调用。
  2. 递推关系：当前问题如何拆成更小的同类问题。

最经典的阶乘示例：

1
2
3
4
5
6
public int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

n <= 1 是终止条件，factorial(n - 1) 是递推关系。

供应链例子：BOM 物料树

制造和供应链系统中经常有 BOM。一个成品由多个半成品组成，半成品又由原材料组成，这就是典型树结构。

1
2
3
4
5
public class BomNode {
    private String materialCode;
    private int quantity;
    private List<BomNode> children;
}

计算一个成品需要多少原材料，可以递归遍历：

1
2
3
4
5
6
7
8
9
10
11
12
public void collectMaterial(BomNode node, int multiplier, Map<String, Integer> result) {
    int requiredQty = node.getQuantity() * multiplier;

    if (node.getChildren() == null || node.getChildren().isEmpty()) {
        result.merge(node.getMaterialCode(), requiredQty, Integer::sum);
        return;
    }

    for (BomNode child : node.getChildren()) {
        collectMaterial(child, requiredQty, result);
    }
}

这段代码表达的是：如果当前节点已经是叶子物料，就汇总数量；否则继续处理子节点。

防止循环依赖

业务数据不一定天然正确。BOM 里如果出现 A 包含 B，B 又包含 A，递归就会无限执行。生产代码必须加访问路径检查：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void collectMaterial(BomNode node,
                            int multiplier,
                            Map<String, Integer> result,
                            Set<String> path) {
    if (!path.add(node.getMaterialCode())) {
        throw new BizException("BOM存在循环依赖: " + node.getMaterialCode());
    }

    int requiredQty = node.getQuantity() * multiplier;
    if (node.getChildren() == null || node.getChildren().isEmpty()) {
        result.merge(node.getMaterialCode(), requiredQty, Integer::sum);
    } else {
        for (BomNode child : node.getChildren()) {
            collectMaterial(child, requiredQty, result, path);
        }
    }

    path.remove(node.getMaterialCode());
}

path 保存当前递归路径，不是全局已访问集合。这样既能识别当前链路上的循环，又不会误伤其他分支复用同一个物料的正常情况。

递归的风险

递归常见风险有三类：

  1. 没有终止条件，导致无限递归。
  2. 层级过深，导致 StackOverflowError。
  3. 重复计算，导致性能指数级下降。

如果层级可能非常深，可以改成显式栈。显式栈不仅要保存节点，还要保存从父节点累积下来的数量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
record BomFrame(BomNode node, long multiplier) {}

Map<String, Long> result = new HashMap<>();
Deque<BomFrame> stack = new ArrayDeque<>();
stack.push(new BomFrame(root, 1L));
while (!stack.isEmpty()) {
    BomFrame frame = stack.pop();
    BomNode current = frame.node();
    long requiredQty = Math.multiplyExact(current.getQuantity(), frame.multiplier());

    if (current.getChildren() == null || current.getChildren().isEmpty()) {
        result.merge(current.getMaterialCode(), requiredQty, Math::addExact);
        continue;
    }

    for (BomNode child : current.getChildren()) {
        stack.push(new BomFrame(child, requiredQty));
    }
}

示例使用 Math.multiplyExact 和 Math.addExact 主动暴露数量溢出。真实 BOM 还应校验单位换算、替代料、生效日期和损耗率；涉及小数数量时应使用 BigDecimal，不能用整数示例直接承载生产计算。

如果存在大量重复子问题，可以使用缓存或动态规划。

小结

递归适合表达层级结构。供应链系统里的 BOM、仓库库区库位树、组织权限树、菜单树都适合用递归建模。生产代码中必须补上终止条件、循环依赖检查、最大深度限制和异常处理，否则递归很容易从优雅实现变成线上风险。