一起动脑筋 · 先看一个小故事
女孩用三张任务卡画出递归，向下时叠上新卡，返回时拿走顶卡。
把过程摊开来看
- 进入 f(3)栈多一张
- 进入 f(2)再多一张
- 进入最小任务停止增加
- 返回一张一张取走
每一层普通递归调用都需要记住返回位置，以及本层仍要使用的信息。
栈顶是当前执行的层，下面的是等待中的层。观察栈的高度，就能看到递归有多深。
看见调用，也看见返回
任务卡从左到右表示从栈底到栈顶。最右边是当前正在执行的一层。
f(3)
这一层要算 3 × f(2)，先等待 f(2)。
f(3) 等待f(2)
这一层要算 2 × f(1)，再新增一层。
f(3) 等待f(2) 等待f(1) 等待f(0) = 1
f(0) 直接返回 1，不再新增调用。
f(3) 等待f(2) 等待f(1) = 1
计算 1 × 1，得到 1 并返回。
f(3) 等待f(2) = 2
计算 2 × 1，得到 2 并返回。
f(3) = 6
计算 3 × 2，得到 6。本次调用完成。
01从 f(3) 开始看
void f(int n) {
if (n == 0) {
return;
}
f(n - 1);
}调用 f(3) 后，会继续调用 f(2)、f(1)、f(0)。
02调用栈怎样一层层增加？
第 1 步
→f(3)
第 2 步
→f(2)
f(3)
第 3 步
f(1)
f(2)
f(3)
再调用 f(0) 时，还会继续增加一层。
03每一层的 n 是同一个变量吗？
不是。每个函数调用都有自己的形参对象。
f(3)
n = 3
f(2)
n = 2
f(1)
n = 1
f(0)
n = 0
这些调用同时活跃时，各自都保留自己的状态。
04为什么上一层要“等”下一层？
当 f(3) 调用 f(2) 时，f(3) 还没有结束。
它必须等 f(2) 完成并返回后，才能继续执行调用语句之后的代码。
05到达基本情况以后发生什么？
f(0) 直接 return↑回到 f(1)↑回到 f(2)↑回到 f(3)
这时调用栈开始从最上层逐层减少。
06调用栈示意图是真实内存的精确照片吗？
不是。它是非常重要的程序执行模型，也是常见实现方式。
具体栈帧中放哪些内容、怎样对齐、哪些变量放寄存器，都由编译器、平台 ABI 和优化决定。
你已经知道了什么
- 递归的每一次调用都有独立调用状态。
- 常见实现会把活跃调用组织在调用栈中。
- 每层递归有自己的参数和局部变量。
- 更深层调用完成后，才能回到上一层继续。
- 达到基本情况后，调用会按相反顺序逐层返回。
下一篇：递归是怎样一层一层返回的？
轮到你来试一试
一层卡片返回时，应拿走底部还是顶部？
想好了吗？点开看解释
顶部。底部还有尚未完成的调用，必须等上面的结果回来。