元数据卡
- 前置知识：方法（第5章）、调用栈（第5章）、循环（第4章）
- 预计时间：45 分钟
- 核心难度：
- 阅读模式： 高度专注
- 可选跳过：如果时间有限，可跳过"尾递归"和"互递归"部分；这是第5章的深入补充
- 完成标志：能手写出至少两种递归模式（线性递归、树递归），理解递归与循环的差异，知道尾递归的思路
本章分层
- 必读：基准情况（base case）与递归推进（recursive case）、递归调用栈过程与空间开销、递归 vs 循环的适用场景
- 选读：树递归的重复计算问题、分治思想的递归表达
- 深水区：尾递归原理（虽然 Java 不做 TCO）、记忆化（memoization）
本章不会要求你掌握
- 尾递归优化在底层 JVM 的实现细节（Java 不支持）
- 互递归在工程中的实际应用（极少数解析器场景）
你在哪
上完方法课，你绕到铁匠铺后院透透气，发现老陈站在那棵歪脖子树下朝你招手。
铁匠铺的后院里，老陈师傅指着一棵歪脖子树。
"爬到树顶，把最上面的那个果子扔下来。"
你仰头一看——树枝一层层分叉，每一层的分叉又生出更多分叉。你找到主树干，爬上第一根树枝，然后是第二根，第三根……到了某一层，你发现前面的路分成了两条。你选了右边那根，爬到顶，拿到果子，扔下来。然后你得退回来，从左边那根再爬上去。
"不对，"老陈说，"你不是在爬树——你是在重复同一个动作：在每根树枝上，先找到所有子树枝，对每个子树枝做同样的事。"
这就是递归。上一章学会了方法调方法，但有一个局面你还没面对：方法能不能调用自己？
你的任务
阶乘、斐波那契、二叉树、文件目录遍历、快速排序——这些问题的共同点是什么？
它们的结构是自相似的：一个大问题和它的小版本长得一模一样。学会递归就是学会识别这种自相似性，然后用最少的代码解决最复杂的问题。
这章会带你走过从"循环实现"到"递归实现"的思维转变。你会看到什么时候递归是绝杀，什么时候它是个陷阱。你还将看到编译器工程师们想了什么办法来弥补递归的性能代价——以及这个办法为什么在实践中很少用到。
遭遇战 → 获得技能
第一幕：从阶乘说起——递归的呼吸
阶乘（factorial）：5! = 5 × 4 × 3 × 2 × 1 = 120。
你先用循环写一遍——这是你已经会的：
public class Factorial {
public static void main(String[] args) {
System.out.println("5! = " + factorialLoop(5));
System.out.println("10! = " + factorialLoop(10));
}
static long factorialLoop(int n) {
long result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
}语言：Java 21 如何运行：javac Factorial.java && java Factorial预期输出：
5! = 120
10! = 3628800现在，停一下。观察阶乘的规律：
5! = 5 × 4 × 3 × 2 × 1
= 5 × (4 × 3 × 2 × 1)
= 5 × 4!
4! = 4 × (3 × 2 × 1) = 4 × 3!发现了吗？阶乘的定义本身是递归的：
n! = n × (n-1)! （当 n > 1 时）
1! = 1 （基准情况）数学定义长什么样，代码就长什么样：
static long factorialRecur(int n) {
if (n <= 1) {
return 1; // 基准情况（base case）：递归的终点
}
return n * factorialRecur(n - 1); // 递归情况：n! = n × (n-1)!
}完整代码：
public class Factorial {
public static void main(String[] args) {
System.out.println("循环: 5! = " + factorialLoop(5));
System.out.println("递归: 5! = " + factorialRecur(5));
System.out.println("递归: 10! = " + factorialRecur(10));
}
static long factorialLoop(int n) {
long result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
static long factorialRecur(int n) {
if (n <= 1) return 1;
return n * factorialRecur(n - 1);
}
}预期输出：
循环: 5! = 120
递归: 5! = 120
递归: 10! = 3628800递归版只有三行核心逻辑。没有循环变量，没有累加器，没有 i++。递归是在表达"是什么"，不是"怎么做"。
运行 factorialRecur(4) 时调用栈是这样的：
main
└─ factorialRecur(4)
├─ 4 >= 1, 需要 4 * factorialRecur(3)
│ └─ factorialRecur(3)
│ ├─ 3 >= 1, 需要 3 * factorialRecur(2)
│ │ └─ factorialRecur(2)
│ │ ├─ 2 >= 1, 需要 2 * factorialRecur(1)
│ │ │ └─ factorialRecur(1)
│ │ │ └─ return 1 ← 到底了！
│ │ └─ return 2 * 1 = 2
│ └─ return 3 * 2 = 6
└─ return 4 * 6 = 24 ← 最终结果两个关键部件：
| 部件 | 作用 | 如果忘了写 |
|---|---|---|
| 基准情况（base case） | 告诉递归"停在这里" | 无限递归 → StackOverflowError |
| 递归情况（recursive case） | 让问题变得更小，逼近基准 | 不会发生——因为你没写它也会无限递归（等等，那确实是同一个问题） |
🐍 Python 差异：
pythondef factorial(n: int) -> int: if n <= 1: return 1 return n * factorial(n - 1) print(f"5! = {factorial(5)}") # 输出: 5! = 120 print(f"1000! = {factorial(1000)}") # 💥 RecursionError: maximum recursion depth exceededPython 的递归栈默认深度限制是 1000。超过就抛
RecursionError—— 这不是栈溢出（内存不够），是 Python 自己的安全限制。你可以用sys.setrecursionlimit(10000)调大，但不推荐。Java 默认可以到 1000-2000 层（取决于栈大小），但也能调。
第二幕：递归 vs 循环——你该用哪个？
这不是"谁更好"的问题。这是"哪个工具适合哪个场景"的问题。
能用循环解决的问题，优先用循环。
| 对比 | 循环 | 递归 |
|---|---|---|
| 代码行数 | 多（需要管理循环变量） | 少（直接表达数学定义） |
| 性能 | 快（没有函数调用开销） | 慢（每次递归 = 一次方法调用） |
| 内存 | O(1) | O(n)（压 n 层栈帧） |
| 可读性 | 线性思维 | 自相似思维 |
| 适用场景 | 线性遍历、顺序操作 | 树状结构、分治、数学定义 |
来一个直观对比：
public class Compare {
public static void main(String[] args) {
int n = 10_000_000;
long start = System.nanoTime();
long sumLoop = sumLoop(n);
long end = System.nanoTime();
System.out.println("循环: " + sumLoop + " (" + (end - start) / 1_000_000 + "ms)");
// 递归就算了，1000万层栈帧，你的电脑会哭
// long sumRecur = sumRecur(n); // 💥 试试？
}
static long sumLoop(int n) {
long sum = 0;
for (int i = 1; i <= n; i++) sum += i;
return sum;
}
static long sumRecur(int n) {
if (n <= 1) return 1;
return n + sumRecur(n - 1); // 优雅但脆弱——栈空间有限
}
}结论：处理 1000 万个数，循环轻松跑完。递归——跑到第几千层就炸了。
但你不是总在做线性遍历。有些问题，自然的表达方式就是递归：
遍历一个文件夹（树状结构）：
import java.io.File;
public class ListFiles {
public static void main(String[] args) {
listAllFiles(new File("."), 0);
}
static void listAllFiles(File dir, int depth) {
File[] files = dir.listFiles();
if (files == null) return;
for (File file : files) {
// 打印缩进
for (int i = 0; i < depth; i++) System.out.print(" ");
System.out.println(file.getName());
// 如果是目录，递归进去
if (file.isDirectory()) {
listAllFiles(file, depth + 1);
}
}
}
}语言：Java 21 如何运行：在当前项目目录下运行 javac ListFiles.java && java ListFiles预期输出（你的项目目录）：
.
src
main
java
...如果你用循环写目录遍历，你需要自己维护一个栈（或队列）去模拟递归。可以做到，但代码量会翻倍，而且读代码的人需要想一会儿才能看懂"哦这是在做深度优先遍历"。而递归版本，读的人一眼就知道："它在递归地遍历目录。"
另一个经典例子：解析数学表达式。 (3 + 5) × (2 + 8 / 4)——你可以用栈做，但递归写一个表达式求值器，代码结构和它的语法树结构是天然对应的。
何时用递归：当你的数据本身就是递归结构（树、图、嵌套列表、XML/JSON）。 何时用循环：当你的数据是线性序列（数组、链表遍历）。
💡 老陈的折中：有些时候，循环 + 自己的显式栈是最佳方案——你有递归的表达力，又有循环的性能控制。那个显式栈其实就是在模仿 JVM 的调用栈，只不过你自己的栈在堆内存里，更可控。
第三幕：树递归与重复计算的代价
💡 前置预告：树递归和记忆化（memoization）是数据结构与算法（DSA）卷和动态规划（DP）卷的重要前置。 本章只做概念引入——在 Vol 2 中你会系统学习如何分析和优化它们。
斐波那契数列：
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 // 这里开始卡了，可能要几十秒跑 F(45) 时发生了什么？
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \
fib(2) fib(1) ...
/ \
fib(1) fib(0)fib(3) 被算了两次。fib(2) 被算了三次。 整个计算树里，同一棵子树被反复重新计算。
复杂度是多少？O(2ⁿ)——指数级。n=45 时大约 18 亿次递归。你电脑不卡才怪。
循环版本：
static long fibLoop(int n) {
if (n <= 1) return n;
long a = 0, b = 1;
for (int i = 2; i <= n; i++) {
long next = a + b;
a = b;
b = next;
}
return b;
}复杂度：O(n)。n=100 瞬间出结果。
这就是递归的经典陷阱：树递归的重复计算。你优雅的三行代码，隐藏着指数级的时间成本。
解决方案之一：记忆化（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)); // 瞬间
}
}预期输出：
F(100) = 354224848179261915075 // 对不起 Java 的 long 溢出哦，long 不够装 F(100)。换成 BigInteger 就行了。但这不是重点——重点是有了记忆化，树递归从 O(2ⁿ) 变成了 O(n)。
🐍 Python 差异：
Python 有内置的
functools.lru_cache装饰器，一行实现记忆化：pythonfrom functools import lru_cache @lru_cache(maxsize=None) def fib(n: int) -> int: if n <= 1: return n return fib(n-1) + fib(n-2)Java 没有这种内置的装饰器模式，你得手动写
HashMap缓存——但这对你来说是好事，因为你能看到缓存到底做了什么。
第四幕：互递归——两个人互相推锅
📎 附录性质：互递归在工程中很少出现，属于概念了解即可的附录内容。
递归不只是"方法调自己"。也可以是"方法A调方法B，方法B又调方法A"。
经典的例子：判断一个整数是奇数还是偶数，不用 % 操作符。
public class MutualRecur {
public static void main(String[] args) {
System.out.println("7 是奇数？" + isOdd(7));
System.out.println("7 是偶数？" + isEven(7));
System.out.println("42 是偶数？" + isEven(42));
}
static boolean isEven(int n) {
if (n == 0) return true;
return isOdd(n - 1);
}
static boolean isOdd(int n) {
if (n == 0) return false;
return isEven(n - 1);
}
}预期输出：
7 是奇数？true
7 是偶数？false
42 是偶数？true调用过程（isEven(3)）：
isEven(3) → isOdd(2) → isEven(1) → isOdd(0) → return false
← false
← false
← false
← false互递归在现实中不多见，但它展示了递归的核心思想在不同姿态下的应用：
- 两个方法互相依赖——每个都把问题变小一点
- 总有一个基准情况来终止
你以后可能会在状态机（特别是解析器中）遇到这种模式——状态A的处理函数调用状态B的处理函数，反之亦然。
📎 附录性质：尾递归优化是编译原理的概念。Java 不支持 TCO，此处只做知识拓展。
第五幕：尾递归——编译器帮我优化？
先看一个现象：
// 普通递归
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 → 弹出每一层都压着一个栈帧，因为 n + sumRecur(n-1) 的结果不是立刻返回的——它还要和 n 做加法。这些栈帧不能释放。
现在看尾递归：
// 尾递归版本
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 的 return 语句中，递归调用是最后一个动作，而且它的结果被直接返回。这意味着——在理论上——当前栈帧不需要保留了。等你从递归调用返回后，只是把这个返回值再往上传。编译器可以优化它：直接把当前栈帧替换成下一层栈帧，而不是往上压新的一层。
如果优化了，执行变成了：
sumTail(4, 0) → 栈帧变成 sumTail(3, 4)
→ 栈帧变成 sumTail(2, 7)
→ 栈帧变成 sumTail(1, 9)
→ 返回 10一个栈帧用到结束。 时间复杂度不变，但空间复杂度从 O(n) 降到了 O(1)。这就是尾递归优化（Tail Call Optimization, TCO）。
它不仅能用在递归上。任何"最后一步是函数调用并直接返回"的场景，理论上都可以做尾调用优化。
现实情况：
Java：不支持 TCO。 原因复杂——主要是 Java 的安全模型（
SecurityManager需要在调用栈上记录谁调了谁）和中间文件（字节码）层面的限制。虽然 JVM 某些实现可以优化"同方法"的尾递归（叫尾递归消除），但 JLS 不要求，Oracle JDK 默认也不做。Python：不支持 TCO。 Guido van Rossum 明确拒绝了 TCO——他认为"丢掉栈跟踪信息"会让 Python 更难调试，而且会"让你的代码依赖于一个编译器实现细节"。
C++：支持（编译器实现细节）。 现代 GCC/Clang 在
-O2或-O3优化级别下会自动做尾调用优化。你可以写return sumTail(n-1, acc+n);，D 会变成循环。函数式语言（Scheme, Haskell, Scala）： TCO 是语言的必备功能。函数式编程没有循环，递归是唯一的"重复"手段——递归的效率不能是灾难级的。
所以：了解尾递归的思想，写 Java 和 Python 时基本用不上。但如果你以后去写 Scala、Kotlin 或函数式语言，它会成为一个重要的武器。
🏔 深入冒险：分治思想的递归表达
第六幕：分而治之（Divide and Conquer）
递归不只是用来替代循环的。它是一个更强大的思想工具——分治。
分治三步走：
- 分解：把大问题分成两个（或多个）规模更小的子问题
- 解决：递归地解决每个子问题（基准情况直接解决）
- 合并：把子问题的解合并成大问题的解
经典的例子：数组求和——分治版：
public class DivideSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
System.out.println("总和 = " + sum(arr, 0, arr.length - 1));
}
static int sum(int[] arr, int left, int right) {
if (left == right) {
return arr[left]; // 基准情况：只有一个元素
}
int mid = (left + right) / 2;
int leftSum = sum(arr, left, mid);
int rightSum = sum(arr, mid + 1, right);
return leftSum + rightSum;
}
}预期输出：
总和 = 36你看到分治和线性递归的区别了吗？
sum(0,7)
/ \
sum(0,3) sum(4,7)
/ \ / \
sum(0,1) sum(2,3) sum(4,5) sum(6,7)
/ \ / \ / \ / \
sum(0) sum(1) sum(2) sum(3) sum(4) sum(5) sum(6) sum(7)计算次序不是 1+2+3+4…的顺序相加，而是先把数组砍成两半，每一半再砍成两半……砍到只剩一个元素，开始往上合并。
为什么分治有用？
复杂度分析更直接。
sum的分治版本，每层处理两个子问题，每层工作O(1)（加个法），深度是log₂n→ 总复杂度还是O(n)。但注意——这里没有节省时间，它在展示模式。很多高效算法天然是分治的：
- 归并排序：把数组砍成两半，分别排序，再合并
- 快速排序：选一个基准，把数组分成"小于基准"和"大于基准"两部分，递归排序
- 二分搜索：每次砍掉一半
- 二叉树搜索：每次走左或走右砍掉一半
分治天生并发。到了第14章，你可以把
sum(arr, left, mid)和sum(arr, mid+1, right)放在两个线程上跑。分治的"子问题互不依赖"是它天然并行的根源。
** C++ 差异：**
cpp`#include <iostream>` `#include <vector>` `#include <algorithm>` `#include <numeric>` `#include <execution>` // C++17, 需要 TBB int main() { `std::vector<int> arr = {1,2,3,4,5,6,7,8};` // 顺序 auto sum1 = std::reduce(arr.begin(), arr.end(), 0); // 并行 auto sum2 = std::reduce(std::execution::par, arr.begin(), arr.end(), 0); std::cout << "顺序: " << sum1 << "\n"; std::cout << "并行: " << sum2 << "\n"; }C++17 的
std::reduce默认使用分治思想，并且你可以在它的标准库实现里看到一个"砍两半递归"的模式。而且 C++ 有标准化的并行算法——这是 Java 标准库没有的（需要自己去线程池里搞）。
常见陷阱
陷阱一：递归写久了，你所有问题都想用递归
// ❌ 你的冲动
static String repeat(String s, int n) {
if (n <= 0) return "";
return s + repeat(s, n - 1);
}
// ✅ 老实写
static String repeat(String s, int n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(s);
return sb.toString();
}重复拼接字符串这种线性任务，循环简洁高效。递归反而复杂化。
经验法则：如果你的问题是线性的（走一遍列表、重复 N 次），用循环。如果你的问题是树状的（目录、表达树、决策树），用递归。
陷阱二：忘记基准情况——死循环的远房亲戚
// ❌ 你写了这样的代码
static int divide(int a, int b) {
return 1 + divide(a - b, b); // 假设 a >= b
// 基准情况在哪？没有人知道。
}修好了是这样的：
static int divide(int a, int b) {
if (a < b) return 0; // 基准：减不动了
return 1 + divide(a - b, b);
}陷阱三：递归太深了
你写了一个漂亮的递归程序，在测试时一切正常。然后在生产数据上——StackOverflowError。
不是因为你的代码有 bug。是栈空间不够了。
常见的兜底方案：
- 转循环——最可靠。能用循环就用循环。
- 增大栈空间——
java -Xss2m YourProgram，临时解决问题，但治标不治本。 - 手动栈——把递归换成循环 + 显式栈——保留递归的逻辑清晰性，但把栈移到堆内存里。
import java.util.*;
public class ManualStack {
// 用显式栈模拟递归的目录遍历
static void listAllFilesIterative(File root) {
Stack<File> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
File dir = stack.pop();
File[] files = dir.listFiles();
if (files == null) continue;
for (File file : files) {
System.out.println(file.getPath());
if (file.isDirectory()) {
stack.push(file); // 手动压栈，替换递归
}
}
}
}
public static void main(String[] args) {
listAllFilesIterative(new File("."));
}
}这不是递归，这是迭代。 但你看到了吗——逻辑结构和递归版本几乎一样，区别在于你在自己操控栈（在堆上），不受 JVM 调用栈大小的限制。
P.S.
File已过时，应使用java.nio.file.Files和Path。但这章的例子里File直观易懂，先让它服役。
陷阱四：递归加缓存（记忆化），还是递归加循环？
斐波那契的记忆化版本已经很好了。但在实际工程里，你还需要更务实的选择：
- 如果问题规模已知且不大：递归就递归，省事
- 如果问题规模大：考虑循环或手动栈
- 如果你需要所有中间结果（比如求所有前缀和）：循环自不必说
通关挑战
- 🗡 热身（5 分钟，必做）
- 用递归写一个方法
int pow(int base, int exp)，计算base^exp。比如pow(2, 5) = 32。 - 用递归写一个方法
int sumDigits(int n)，计算各位数字之和。比如sumDigits(123) = 1+2+3 = 6。 - 用递归写
void countdown(int n)，倒计时输出n, n-1, ..., 1, 0, 发射！。
- 挑战（30 分钟，选做）
二分搜索：给定已排序数组
{1, 3, 5, 7, 9, 11, 13, 15}，用递归实现二分查找，返回目标值的索引。如果没找到返回-1。文件搜索器：写一个程序，递归遍历整个项目目录，找到所有文件名包含关键词的文件（比如包含
"recursion"的.java文件）。打印出它们的完整路径。斐波那契性能测试：写一个
Benchmark程序，分别测试普通递归版、记忆化递归版、循环版计算F(40)的时间。- 输出格式：
F(40) = 102334155
普通递归: 1234ms
记忆化递归: 0ms
循环: 0ms- 观察
用 -Xss 参数调大调用栈，看看递归阶乘最多能算到 n 是多少。比如 java -Xss2m Factorial 100000。
public class FactorialMax {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
try {
System.out.println(n + "! 计算中...");
long result = factorial(n);
System.out.println("成功！结果位数: " + String.valueOf(result).length());
} catch (StackOverflowError e) {
System.out.println("💥 栈溢出！n = " + n + " 太大了");
}
}
static long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
}- 排障
// 这段代码试图判断 "一个字符串是不是回文"，但有问题
// 比如 isPalindrome("racecar") 应该返回 true
// 它现在运行时会在某些输入上崩溃。找到原因并修复。
public class Palindrome {
public static boolean isPalindrome(String s) {
if (s.length() <= 1) return true;
if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
return isPalindrome(s.substring(0, s.length() - 1)); // bug 在这里
}
public static void main(String[] args) {
System.out.println(isPalindrome("racecar")); // 期望 true
System.out.println(isPalindrome("hello")); // 期望 false
System.out.println(isPalindrome("a")); // 期望 true
}
}提示：看
return语句里的递归子调用——它减少了字符串吗？减少了哪一头？回文的定义是"从两边往里比较"，你只砍了一头，会无限循环吗？
验收标准
- 你能手写一个简单的递归函数（阶乘、求和、文件遍历）
- 你能正确解释递归的"基准情况"和"递归情况"的关系
- 你能画出
factorialRecur(4)的调用栈变化过程 - 你能区分"可以用递归"和"应该用递归"（线性 vs 树状）
- 你知道什么情况下递归会栈溢出
- 你知道尾递归的原理（虽然 Java 用不上）
- 你能解释分治的三步：分解、解决、合并
常见卡点
"跑模拟递归太烧脑，跟踪不下去。" 找一支笔。画出调用栈的每一帧——把方法名、参数值、还没算完的表达式写下来。画着画着就通了。每次遇到递归卡住，就用"画栈法"。
"我写了一个递归，但不知道它为什么能工作。" 把递归想象成"我信任更小的版本能解决更小的问题"——只要你有基准情况，并且在每一步都让问题变得更小，它就会收敛到基准情况。这叫"递归信念"（recursive leap of faith）。先信了，写出来测试，再回头理解它为什么对。
"为什么递归比循环慢那么多？" 每次递归调用 = 创建栈帧 + 压栈 + 上下文切换 + 执行 + 弹栈。一个 add 方法调用在纳秒级别。循环的 j++ 在同一个栈帧内，没有这些开销。如果递归深度 10, 000 层，你就多承担了 10, 000 次函数调用的开销。
"记忆化是把双刃剑吗？" 是的。它用空间换时间——你的缓存可能会无限增长。如果输入空间是连续的（比如 n 从 1 到 10^6），缓存会变得很大。所以在实际工程中，如果 n 可以非常大，考虑循环或迭代 DP，而不只是递归 + 缓存。
现在不需要理解
- 为什么 Java 不做尾递归优化（涉及安全模型和 JVM 规范的历史原因）
- 归并排序和快速排序的具体实现（第2卷会深度讲解）
- 递归在函数式编程中的核心地位（第9卷的语言深度会讲）
- 循环展开和循环不变量的编译器优化
- 阿克曼函数——纯粹的理论递归，工程价值低
旅人笔记
递归 = 方法调用自己。核心是两点：基准情况（停止）和递归情况（靠近基准）。递归天然适合树状结构，但线性问题优先用循环。尾递归=递归调用是最后一步（Java 不优化它，但知道它很重要）。分治=把大问题砍成小问题，合并小答案成大答案。记住：递归是思维工具，不只是编程技巧。
→ 下一站预告
从单兵作战到拆解任务，你已经掌握了一个程序的基本结构——变量、条件、循环、方法和递归。但你要处理的数据越来越多了。一个人的剑谱要记，十个人的也要记吗？一百个人的呢？下一章，我们打开数组的门——它不会给你更方便的变量命名，但让你用数字下标就能走遍整个数据集合。