5.6 递归入门

前置知识：方法、调用栈和循环

预计时间：25 分钟

完成标志：能写出基线、递归步骤、进度度量和输入边界

“别把每根枝条当成新问题。定义怎么处理一棵树，再让同一个方法处理子树。”

递归是方法直接或间接调用自己

阶乘定义：

0! = 1
n! = n × (n - 1)!，n > 0

static long factorial(int value) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value: " + value);
    }
    if (value > 20) {
        throw new ArithmeticException("factorial exceeds long: " + value);
    }
    if (value == 0) {
        return 1L;
    }
    return Math.multiplyExact(value, factorial(value - 1));
}

三个部分缺一不可：

部分	阶乘例子	要证明什么
输入域	0 <= value && value <= 20	域外输入怎样失败
基线	value == 0	不再递归且结果正确
递归步骤	factorial(value - 1)	子问题更小，最终到达基线

只写基线还不够。若递归步骤传入 value + 1，永远不会靠近 0。需要一个严格下降、下界明确的进度度量。

手动画出 factorial(4)

factorial(4)
4 × factorial(3)
4 × 3 × factorial(2)
4 × 3 × 2 × factorial(1)
4 × 3 × 2 × 1 × factorial(0)
4 × 3 × 2 × 1 × 1 = 24

向下阶段创建调用，触底后逐层返回。每层还保留自己的 value 和“等子调用回来再乘”的工作。

数值边界与递归边界不同

long 只能保存到 20!。下面的输入检查直接拒绝大于 20 的值并抛 ArithmeticException，避免巨大输入先耗尽调用栈；Math.multiplyExact 则继续检查每次乘法。即使调用栈还能继续，结果类型也已经装不下。

System.out.println(factorial(20));
// System.out.println(factorial(21)); // 数值溢出

需要更大阶乘可使用 BigInteger，但输入和时间仍要限制。

循环版本通常更适合线性问题

static long factorialLoop(int value) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value: " + value);
    }
    if (value > 20) {
        throw new ArithmeticException("factorial exceeds long: " + value);
    }
    long result = 1L;
    for (int factor = 2; factor <= value; factor++) {
        result = Math.multiplyExact(result, factor);
    }
    return result;
}

两个版本时间都是 O(n)。递归版有 O(n) 活动调用深度，循环版使用固定数量的局部状态。Java 不保证尾调用消除，因此线性计数通常优先循环。

递归更自然的场景通常具有递归结构：语法树、目录树、组合结构、分治区间。即使如此，也要评估最大深度、循环引用和资源失败。

看似树形的数据可能包含回路

对象图、符号链接和依赖图可能回到已经访问的节点。仅有“叶子节点基线”不足以保证结束，还需 visited 集合、深度限制或领域保证。

static void visit(Node node, Set<Node> visited) {
    if (!visited.add(node)) {
        return;
    }
    for (Node child : node.children()) {
        visit(child, visited);
    }
}

这是结构示意，Node 和 Set 会在后续章节展开；假设节点和子节点集合都非 null，并且访问期间图结构不变。visited 的相等规则也要符合业务：按对象身份访问和按业务标识去重可能是两种需求。

专业速查

检查项	问题
输入域	负数、空值、超大输入怎样处理
基线	是否覆盖最小合法结构
进度	每步是否严格靠近基线
深度	最坏调用深度是否可控
数值	结果类型是否先溢出
图结构	是否可能成环或重复访问

离开这一页前

用 factorial(4) 标出输入域、基线、递归步骤和严格下降的进度度量，再分别说明 21 阶乘为什么先遇到数值边界、对象图为什么还需要访问记录。对线性问题，还要能解释循环版如何用固定数量的局部状态完成同一计算。

→ 下一步：递归的栈、重复计算与尾调用