元数据卡

• 前置知识：递归入门（第5章）、调用栈（第5章）
• 预计时间：15 分钟
• 阅读模式： 高度专注
• 完成标志：能画出递归调用栈变化过程，理解尾递归思想

本章分层

• 必读：递归调用栈过程与空间开销、尾递归思路
• 选读：树递归的重复计算问题、记忆化
• 进阶：尾递归原理

第四幕：递归的调用栈——一层一层往下搭

运行 factorialRecur(4) 时调用栈是这样的：

main
 └─ factorialRecur(4)
     ├─ 4 需要 4 * factorialRecur(3)
     │   └─ factorialRecur(3)
     │       ├─ 3 需要 3 * factorialRecur(2)
     │       │   └─ factorialRecur(2)
     │       │       ├─ 2 需要 2 * factorialRecur(1)
     │       │       │   └─ factorialRecur(1)
     │       │       │       └─ return 1  ← 到底了！
     │       │       └─ return 2 * 1 = 2
     │       └─ return 3 * 2 = 6
     └─ return 4 * 6 = 24  ← 最终结果

每一层都压着一个栈帧，因为 n * factorialRecur(n-1) 返回后还要和 n 做乘法。这些栈帧直到递归"触底"后才能开始释放。

空间复杂度：O(n)。递归深度多少，栈帧就压多少层。这就是为什么递归太深会 StackOverflowError。

第五幕：树递归与重复计算的代价

斐波那契数列：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   （n ≥ 2）

直接翻译成递归：

public class Fib {
    public static void main(String[] args) {
        System.out.println("F(10) = " + fib(10));
        System.out.println("F(30) = " + fib(30));
        System.out.println("F(45) = " + fib(45));  // 等着，会很久
    }

    static long fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }
}

预期输出：

F(10) = 55
F(30) = 832040
F(45) = 1134903170  // 这里开始卡了，可能要几十秒

fib(3) 被算了两次。fib(2) 被算了三次。复杂度 O(2ⁿ)——指数级，n=45 时约 18 亿次递归。

解决方案之一：记忆化（memoization）

把算过的结果存下来，下次直接拿：

import java.util.HashMap;
import java.util.Map;

public class FibMemo {
    static Map<Integer, Long> cache = new HashMap<>();

    static long fib(int n) {
        if (n <= 1) return n;
        if (cache.containsKey(n)) return cache.get(n);  // 算过了就拿

        long result = fib(n - 1) + fib(n - 2);
        cache.put(n, result);  // 存起来
        return result;
    }

    public static void main(String[] args) {
        System.out.println("F(100) = " + fib(100));  // 瞬间
    }
}

有了记忆化，树递归从 O(2ⁿ) 降到了 O(n)。

第六幕：尾递归——编译器帮我优化？

先看一个现象：

// 普通递归
static long sumRecur(int n) {
    if (n <= 1) return 1;
    return n + sumRecur(n - 1);  // 返回后还要做加法
}

执行 sumRecur(4)：

sumRecur(4) 需要 4 + sumRecur(3) → 压栈等结果
 sumRecur(3) 需要 3 + sumRecur(2) → 压栈等结果
 sumRecur(2) 需要 2 + sumRecur(1) → 压栈等结果
 sumRecur(1) return 1 → 弹出
 return 2 + 1 = 3 → 弹出
 return 3 + 3 = 6 → 弹出
return 4 + 6 = 10 → 弹出

四层栈帧全压着，不能释放。

现在看尾递归：

// 尾递归版本
static long sumTail(int n, long acc) {
    if (n <= 1) return acc + 1;
    return sumTail(n - 1, acc + n);  // 返回的就是递归调用的结果
}

执行 sumTail(4, 0)：

sumTail(4, 0) → 需要 sumTail(3, 0+4=4)
 sumTail(3, 4) → 需要 sumTail(2, 4+3=7)
 sumTail(2, 7) → 需要 sumTail(1, 7+2=9)
 sumTail(1, 9) → return 9+1=10
 return 10
 return 10
return 10

还是压了四层栈啊？区别在于语义：sumTail 的递归调用是最后一个动作，结果直接被返回。理论上——当前栈帧不需要保留。编译器可以把当前栈帧替换成下一层栈帧，而不是往上压新的一层。

如果优化了：

sumTail(4, 0) → 栈帧变成 sumTail(3, 4)
              → 栈帧变成 sumTail(2, 7)
              → 栈帧变成 sumTail(1, 9)
              → 返回 10

一个栈帧用到结束。 空间复杂度从 O(n) 降到 O(1)。这就是尾递归优化（TCO）。

现实情况： Java 不支持 TCO（安全模型限制）。Python 不支持（Guido 认为丢掉栈跟踪使调试更困难）。C++ 支持（-O2/-O3 下自动做）。函数式语言（Scheme、Scala、Kotlin）TCO 是必备功能。了解尾递归思想，写 Java 和 Python 基本用不上，但学函数式语言时是重要武器。

旅人笔记

递归调用会压 n 层栈帧，空间复杂度 O(n)。尾递归把递归调用放在最后一步，理论上可优化到 O(1)。树递归有重复计算问题，记忆化可解决。记住：递归的空间代价是调用栈，指数级递归需要记忆化。

→ 下一站：练习

理论学了够多了。现在是时候动手了——方法和递归的练习题已经准备好了，从热身的阶乘到挑战的二分搜索，还有排障题等你来修。