5.7 递归的栈、重复计算与尾调用

前置知识：递归基线与调用栈

预计时间：35 分钟

完成标志：能计算调用深度、识别重复子问题并说明 Java 尾调用边界

活动调用深度决定栈空间阶

factorial(4) 在最深处同时有 5 个阶乘调用：4、3、2、1、0。输入 n 的活动深度为 O(n)，因此概念上的辅助栈空间为 O(n)。具体字节数和触发 StackOverflowError 的 n 没有可移植常量。

JIT 可能内联普通方法，但 Java 语言和 JVM 规范不保证把任意递归改成常量栈。不要用某次机器实验得到“安全递归深度”。

朴素 Fibonacci 重复计算

static long fibonacciSlow(int value) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value");
    }
    if (value <= 1) {
        return value;
    }
    return Math.addExact(fibonacciSlow(value - 1),
            fibonacciSlow(value - 2));
}

fibonacciSlow(5) 会多次计算 fibonacciSlow(3)、fibonacciSlow(2)。调用数量按指数增长，常写作 O(2ⁿ) 的上界；更紧的增长与黄金比例有关。不要在教程里声称某个 n “一定需要几十秒”，硬件、JIT 和实现会改变时间。

long 还有独立边界：F(92) 可表示，F(93) 超出有符号 long。算法优化不会扩大结果类型。

记忆化消除重复子问题

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

static BigInteger fibonacci(int value) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value");
    }
    Map<Integer, BigInteger> cache = new HashMap<>();
    cache.put(0, BigInteger.ZERO);
    cache.put(1, BigInteger.ONE);
    return fibonacci(value, cache);
}

static BigInteger fibonacci(int value,
                            Map<Integer, BigInteger> cache) {
    BigInteger known = cache.get(value);
    if (known != null) {
        return known;
    }
    BigInteger result = fibonacci(value - 1, cache)
            .add(fibonacci(value - 2, cache));
    cache.put(value, result);
    return result;
}

每个 n 只完整计算一次，算术操作次数降到 O(n)，缓存有 O(n) 个条目，递归栈有 O(n) 层；这不是总字节数均为 O(n) 的承诺。BigInteger 避免固定宽度溢出，但数字越大，单次加法成本也会增长，因此不能把总位运算成本简单写成严格 O(n)。F(n) 的位数为 Θ(n)，缓存前 n 项的大整数值合计需要 Θ(n²) 位；循环版只保留固定数量的大整数，但这些数自身也会变长。

缓存放在单次调用中，避免静态可变 Map 跨请求无限增长和并发竞争。生产场景还要设置容量、生命周期与键空间边界。

线性 Fibonacci 直接迭代通常更简单：

static BigInteger fibonacciLoop(int value) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value");
    }
    BigInteger previous = BigInteger.ZERO;
    BigInteger current = BigInteger.ONE;
    for (int index = 0; index < value; index++) {
        BigInteger next = previous.add(current);
        previous = current;
        current = next;
    }
    return previous;
}

尾递归是语法位置，不是 Java 优化保证

static long sumTail(int value, long accumulator) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value");
    }
    if (value == 0) {
        return accumulator;
    }
    return sumTail(value - 1,
            Math.addExact(accumulator, value));
}

递归调用是方法正常路径的最后动作，称为尾位置。支持尾调用消除的实现可复用帧，但 Java SE 17 不要求这样做，常用 HotSpot 行为也不能作为语言契约。这个 Java 方法仍应按 O(n) 栈深评估。

不要把原因简化成某个已移除或弃用的安全机制，也不要说 C++ 在 -O2 下“一定优化”。C++ 尾调用优化同样受编译器、ABI、调试和代码形状影响。Scheme 等语言规范对 proper tail calls 有不同保证，需逐语言查契约。

对 Java 的线性尾递归，明确循环通常更可靠：

static long sumLoop(int value) {
    if (value < 0) {
        throw new IllegalArgumentException("negative value");
    }
    long result = 0L;
    for (long current = 1; current <= value; current++) {
        result = Math.addExact(result, current);
    }
    return result;
}

循环计数器这里用 long，避免 value == Integer.MAX_VALUE 时 int 计数器加一回绕。不过数十亿次循环仍不适合作为任意输入的服务接口，调用方需要限制工作量。

显式栈把深度控制移到堆对象

迭代 DFS 可用 ArrayDeque 保存待处理节点。它避免 JVM 调用栈深度限制，但不是“无限”：显式栈仍占堆内存，也要处理容量、重复节点和异常。

专业速查

问题	结论
递归空间	按最大同时活动调用深度计算
朴素 Fibonacci	指数级重复调用；还受结果类型限制
记忆化	消除重复，但增加缓存、生命周期和并发问题
Java 尾递归	语言/JVM 不保证常量栈优化
显式栈	深度移到堆管理，不代表无限资源
性能结论	用输入规模、复杂度和测量，不用固定秒数

离开这一页前

画出 fibonacciSlow(5) 中重复出现的子问题，再比较记忆化与循环版的缓存、调用深度和大整数成本。最后说明三件事：F(93) 超出 long，Java 17 不保证尾调用消除，显式栈只是把资源压力移到堆而不是获得无限空间。

递归加餐到这里结束，下一页用一组完整实验复查方法、重载和调用栈。

→ 下一步：方法综合实验