2. 递归的调用栈：函数调用时栈帧如何变化？
好，咱们接着聊递归。上一章我讲了递归的数学基础，说白了就是「自己调用自己」。但很多同学学递归，卡就卡在「到底怎么调用的」这个问题上。
你想想看，一个函数还没执行完，又调了自己一遍。那之前没算完的那些数据放哪了？CPU 怎么知道该回到哪里继续算？
嗯，答案就在——调用栈。
2.1 栈帧是什么？
每个函数被调用时，系统会为它分配一块内存区域，叫栈帧。栈帧里存了啥？
- 函数的局部变量
- 函数的参数
- 返回地址（函数执行完后该跳回哪）
- 一些寄存器的值
我刚开始学 C 语言时，总觉得「栈帧」是个很玄的概念。后来有一次调试一个递归程序，用 GDB 看了 backtrace，才恍然大悟——原来就是一层一层叠上去的「任务卡片」。
核心理解：每次函数调用，系统就压入一个栈帧。函数返回时，弹出栈帧。后进先出。
2.2 递归调用时栈帧如何变化？
咱们拿一个最简单的例子——计算阶乘。
int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}假设我们调用 factorial(3)。你猜栈帧怎么变？
我画了一张图，帮你把「递」和「归」的过程看清楚。
2.3 「递」与「归」的本质
从这张图你能看到什么？
「递」就是压栈。每次调用自己，就把当前的状态（参数、返回地址）压到栈顶。一层一层往下走，直到遇到基准条件。
「归」就是弹栈。基准条件返回后，上一层拿到结果，继续计算，然后弹出自己的栈帧。一层一层往上走，直到回到最初的调用点。
我的个人习惯：调试递归时，我喜欢在纸上画这种栈帧图。画一遍，比看十遍代码都管用。你试试看。
2.4 一个常见的坑：栈溢出
递归虽好，但别贪多。我遇到过不少同学写递归，一写就是几万层。结果呢？
栈空间是有限的。每个栈帧大概占几十到几百字节。如果递归深度太大，栈空间用完了，程序就崩了——栈溢出。
我曾经踩过的坑：有一次写一个目录遍历程序，用递归遍历文件系统。结果目录嵌套太深，递归了几千层，程序直接 Segmentation Fault。后来改成迭代 + 显式栈才解决。
所以，递归深度超过几百上千层时，你就要警惕了。要么改用迭代，要么考虑尾递归优化（后面章节会讲）。
2.5 递归 vs 迭代：栈帧对比
咱们用表格对比一下，递归和迭代在栈帧使用上的区别：
| 特性 | 递归 | 迭代 |
|---|---|---|
| 栈帧数量 | 随递归深度增加 | 固定（通常 1 个） |
| 内存占用 | O(n)，n 为递归深度 | O(1) |
| 代码可读性 | 高（问题自然分解） | 中等（需要手动管理状态） |
| 适用场景 | 树、图、分治、回溯 | 线性遍历、累加 |
说白了，递归是用空间换代码的简洁性。迭代是用代码的复杂度换空间效率。没有谁绝对好，看场景选。
2.6 小结
这一章我们聊了调用栈和栈帧的变化。核心就三句话：
- 每次函数调用，压入一个栈帧
- 递归的「递」就是一层层压栈
- 递归的「归」就是一层层弹栈
理解了这个，递归就不再是黑魔法了。下一章咱们会聊递归的三种经典模式，到时候你再看代码，脑子里就能自动浮现出栈帧的变化图了。