递归：本质、栈帧与尾递归

什么是递归？

递归（Recursion）的本质是函数调用自身来将大问题分解成相同结构的小问题。

核心思想：把规模为 n 的问题，转化为规模更小（通常为 n-1 或 n/2）的同类问题，直到触达边界条件（Base Case）。

递归三要素

递归与栈帧

每一次函数调用都会在调用栈上开辟一个栈帧（Stack Frame），存储：

• 当前函数的局部变量
• 返回地址
• 参数

factorial(4)
  └─ factorial(3)
       └─ factorial(2)
            └─ factorial(1)
                 └─ factorial(0) → 返回 1
            ← 1 * 1 = 1
       ← 2 * 1 = 2
  ← 3 * 2 = 6
← 4 * 6 = 24

栈溢出（StackOverflow） 原因：递归深度过大，栈帧耗尽栈内存。Java 默认栈大小约 512KB1MB，大约支持 100010000 层递归。

递归模板

// 通用递归模板
public ReturnType recursion(params) {
    // 1. 终止条件（必须放最前面）
    if (baseCase) {
        return baseValue;
    }
    // 2. 递归调用（问题规模缩小）
    ReturnType sub = recursion(smallerParams);
    // 3. 合并子问题结果（后序处理）
    return merge(sub, currentData);
}

经典例子

斐波那契数列

// 朴素递归 - O(2^n) 时间，O(n) 空间（栈深度）
public int fib(int n) {
    if (n <= 1) return n;           // base case
    return fib(n - 1) + fib(n - 2); // 递推
}

// 记忆化递归 - O(n) 时间，消除重复子问题
public int fib(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];  // 命中缓存
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

二叉树的最大深度

// 天然递归：树的结构本身就是递归定义的
public int maxDepth(TreeNode root) {
    if (root == null) return 0;           // base case：空树深度为 0
    int left  = maxDepth(root.left);      // 左子树深度
    int right = maxDepth(root.right);     // 右子树深度
    return Math.max(left, right) + 1;     // 当前层 +1
}

尾递归优化

尾递归：递归调用是函数体中的最后一个操作，没有后续计算。

// 非尾递归：return n * factorial(n-1); 还需要乘法
// 尾递归：把"待做的工作"通过参数传递下去
public int factorial(int n, int acc) {
    if (n == 0) return acc;
    return factorial(n - 1, n * acc);  // 最后一步只有递归调用
}
// 调用：factorial(5, 1)

尾递归在支持尾调用优化（TCO） 的语言（Scheme、Kotlin、Scala）中不需要额外栈帧。Java 不支持 TCO，但可以手动改写为循环。

递归 → 迭代改写

任何递归都可以用显式栈模拟：

// 递归版先序遍历
void preorder(TreeNode root) {
    if (root == null) return;
    visit(root);
    preorder(root.left);
    preorder(root.right);
}

// 迭代版（显式栈）
void preorderIter(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        visit(node);
        stack.push(node.right); // 右先压（后处理）
        stack.push(node.left);  // 左后压（先处理）
    }
}

复杂度分析

核心算法考点

1. 写出递归的终止条件——最容易漏
2. 分析时间复杂度——特别是多路递归
3. 记忆化剪枝——将递归优化为 O(n)
4. 改写为迭代——栈溢出规避
5. 相信递归公式——写递归时不要在脑海中"展开"递归，信任递推关系即可