递归的性能陷阱与调用栈

递归是算法世界里最优雅也最危险的工具：二叉树、回溯、动态规划全都建立在它之上，但它同时带来栈溢出和重复计算两大陷阱。这篇文章把递归的"骨架"和"成本"一次讲透。

递归三要素

写递归函数前，先想清楚三件事，缺一不可：

1. 参数与返回值：每一层递归需要拿到什么信息、向上返回什么结果。
2. 终止条件：什么情况下直接返回、不再继续下钻。终止条件写错，要么漏解，要么 StackOverflowError。
3. 单层逻辑：每一层做什么操作，怎样把大问题拆成小问题，再用小问题的答案拼出本层答案。

以"反转单链表"为例：

public ListNode reverse(ListNode head) {
    // 要素2：终止条件——空链表或只剩一个节点，天然有序
    if (head == null || head.next == null) return head;
    // 要素3：单层逻辑——先信任递归，反转后面的部分，拿到新头
    ListNode newHead = reverse(head.next);
    // 把当前节点挂到已反转部分的尾部
    head.next.next = head;
    head.next = null;
    return newHead;   // 要素1：返回值是新链表的头
}

初学阶段建议把三要素当检查清单用：写不出来时，逐条问自己"参数是什么、终止在哪、这一层干吗"。

JVM 调用栈与 StackOverflowError

Java 里每次方法调用都会在虚拟机栈上压入一个栈帧（stack frame），里面保存局部变量表、操作数栈、返回地址等。递归的本质就是"自己调用自己"，于是每一层递归都会压一个新栈帧，只有到达终止条件才开始逐层弹出。

关键约束是：栈的容量是有限的。JVM 默认线程栈大小通常在 512KB ~ 1MB，可以用 -Xss 调整。一旦递归深度超过栈的承受能力，就抛 StackOverflowError：

// 深度为 n 的递归求和，n 大到一定程度必然栈溢出
long sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}

在默认配置下，这个方法递归到几万层左右就会溢出（具体数值取决于每帧大小和 JVM 版本）。这解释了刷题时的一个常见现象：代码逻辑正确，但大数据用例爆栈。LeetCode 大多数题目的数据规模把合法递归深度控制在几千到十万以内，用递归解树和回溯问题通常安全，但"线性深度"的递归（如链表递归遍历、超长数组递归分治）就要警惕。

降低栈风险的常规手段：

• 改成迭代（见文末"递归转迭代"）。
• 减小递归深度：比如分治时把"先处理一半"改成平衡划分。
• 尾递归在部分语言里会被优化成循环，但 JVM 目前不做尾调用优化，指望"写成尾递归就不溢出"在 Java 里是不成立的。

重复计算：斐波那契的教训

栈溢出是"深度"问题，重复计算是"宽度"问题，后者对性能的杀伤更大。用斐波那契数列做对照实验：

版本一：朴素递归

// 时间 O(2^n)：每个节点分裂成两个子问题
// 空间 O(n)：递归栈深度
public long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

画一下调用图就能看出问题（以 fib(5) 为例，缩进表示一层调用）：

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) → fib(1), fib(0)
│   │   └── fib(1)
│   └── fib(2) → fib(1), fib(0)      ← fib(2) 算了两遍
└── fib(3)
    ├── fib(2) → fib(1), fib(0)      ← fib(3) 算了两遍
    └── fib(1)

fib(3)、fib(2) 被反复重算，而且越往下重复越密集。递归树上节点总数呈指数增长，整体复杂度 O(2ⁿ)：n = 50 时就要算上百亿次，直接超时。

版本二：记忆化递归

// 时间 O(n)：每个 fib(k) 只真正计算一次
// 空间 O(n)：memo 数组 + 递归栈
public long fibMemo(int n, long[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];   // 查缓存，算过就直接用
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}
// 调用：fibMemo(n, new long[n + 1])

只加了一个数组做缓存，每个子问题从"重复指数次"变成"恰好一次"，复杂度从 O(2ⁿ) 直接降到 O(n)。这个"算过就存"的思路就是记忆化，也是后续动态规划思想的雏形——DP 本质上就是"带缓存的递归"的迭代版本。

如何估算递归复杂度：递归树

递归的复杂度没法像循环那样直接数次数，通用方法是画递归树，然后算：总成本 = 树上节点数 × 单个节点的成本。三种典型形态：

拿二叉树遍历验证一下：树高 logn（平衡时），每个节点处理 O(1)，节点总数 n → 总复杂度 O(n)。拿归并排序验证：递归树每层总工作量 O(n)（合并成本），共 logn 层 → O(nlogn)。熟练之后，看到递归函数就能在脑中把这棵树搭出来。

递归转迭代的思路

凡是递归都能改写成迭代，只是难度不同。三种常见手法：

1. 直接换循环：问题本质是线性递推时（求和、斐波那契、DP），直接用循环 + 变量滚动即可。
2. 显式栈模拟：递归靠虚拟机栈，那就自己用 Deque 维护状态。二叉树的前中后序迭代遍历、回溯的非递归写法都属于这类。
3. 队列替代（BFS 化）：把深度优先改成层序处理，用 Queue 逐层出队入队，顺带避免深递归。

斐波那契的迭代版本只有几行：

// 时间 O(n)，空间 O(1)，既不爆栈也不重复算
public long fibIter(int n) {
    if (n <= 1) return n;
    long prev = 0, cur = 1;
    for (int i = 2; i <= n; i++) {
        long next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

实战建议：先写递归（好想好写），确认正确后再评估栈深与重复计算，必要时才改迭代。二叉树、回溯类题目递归是首选；线性深度的题目优先迭代。

易错点清单

• 终止条件覆盖不全，导致无限递归 → StackOverflowError。
• 递归函数里每次都 new 集合对象，时间和空间双重浪费，应复用传入的缓冲区。
• 误以为"写成尾递归 JVM 会优化"——Java 没有尾调用优化。
• 只测小样例，没发现指数级重复计算，大数据用例超时。
• 估算复杂度时只算了单层逻辑，忘了乘节点总数。

对应 LeetCode 题目

参考

• 代码随想录 · 算法基础专题