C / C++ / 系统课时
递归函数为什么能够返回
递归函数为什么能够返回
递归调用看起来像“函数还没执行完又调用自己”,容易让人误以为前一层会被覆盖。实际上,每次调用都会创建独立的调用帧,保存本层参数、局部变量和返回位置;到达终止条件后,这些调用帧再按相反顺序逐层恢复。
学习目标
- 理解每次递归调用为何拥有独立的参数和局部变量
- 跟踪从递归深入到逐层返回的完整执行顺序
- 能判断一个递归函数是否具备可达的终止条件
调用帧保存了什么
函数被调用时,运行时需要记住“这次调用属于哪一层”。概念上,一个调用帧至少要保存本次调用的参数、局部状态以及函数结束后应继续执行的位置。递归只是让同一个函数同时存在多份尚未结束的调用帧。
因此,调用 sum_to(3) 后再进入 sum_to(2),并不会把上一层的 n == 3 改成 2。两层拥有各自独立的 n;上一层只是暂时停在递归调用处,等待下一层返回结果。

跟踪一次完整递归
下面的程序在进入每一层时打印参数,并在下层返回后打印本层结果。局部变量 partial 只有在对应调用帧恢复执行时才会得到本次下层调用的返回值。
#include <stdio.h>
int sum_to(int n) {
printf("enter n=%d\n", n);
if (n == 0) {
printf("base n=0 return=0\n");
return 0;
}
// 当前调用暂停在这里,等待更深一层返回。
int partial = sum_to(n - 1);
int result = n + partial;
// 返回时使用的 n、partial、result 都属于当前这一层。
printf("return n=%d result=%d\n", n, result);
return result;
}
int main(void) {
int result = sum_to(3);
printf("final=%d\n", result);
return 0;
}预期输出
enter n=3
enter n=2
enter n=1
enter n=0
base n=0 return=0
return n=1 result=1
return n=2 result=3
return n=3 result=6
final=6前四行说明调用不断深入;遇到 n == 0 后不再递归,而是立即返回。随后输出顺序反过来,说明调用帧按“后调用、先返回”的顺序恢复,这正是栈的行为。
返回不是重新调用
当 sum_to(0) 返回 0 时,程序不会重新从 sum_to(1) 的函数开头执行。它会恢复 sum_to(1) 这一层,并从先前暂停的 int partial = sum_to(n - 1); 之后继续。
这一层算出 result == 1 后再返回给 sum_to(2);同样的过程不断向外展开,最终回到最初的 sum_to(3)。因此,递归的“返回链”依赖的是保存好的调用现场,而不是重新执行已经走过的入口路径。
终止条件决定能不能回来
递归函数必须存在终止条件,而且递归参数必须朝终止条件推进。本例每次都把 n 减一,所以从非负整数出发最终一定能到达 n == 0。
如果递归调用写成 sum_to(n + 1),或者没有覆盖当前输入的终止条件,调用帧就会持续增加,最终可能耗尽调用栈。递归是否正确,首先要检查“能否停下”,其次才是返回值计算是否正确。
递归之所以能够返回,本质上是每次调用都有独立现场,而且运行时会按栈顺序保存与恢复这些现场。只要终止条件可达,最深一层先给出结果,外层就能依次继续完成尚未执行的部分。