C / C++ / 系统课时

递归函数为什么能够返回

递归函数为什么能够返回

递归调用看起来像“函数还没执行完又调用自己”,容易让人误以为前一层会被覆盖。实际上,每次调用都会创建独立的调用帧,保存本层参数、局部变量和返回位置;到达终止条件后,这些调用帧再按相反顺序逐层恢复。

学习目标

  • 理解每次递归调用为何拥有独立的参数和局部变量
  • 跟踪从递归深入到逐层返回的完整执行顺序
  • 能判断一个递归函数是否具备可达的终止条件

调用帧保存了什么

函数被调用时,运行时需要记住“这次调用属于哪一层”。概念上,一个调用帧至少要保存本次调用的参数、局部状态以及函数结束后应继续执行的位置。递归只是让同一个函数同时存在多份尚未结束的调用帧。

因此,调用 sum_to(3) 后再进入 sum_to(2),并不会把上一层的 n == 3 改成 2。两层拥有各自独立的 n;上一层只是暂时停在递归调用处,等待下一层返回结果。

递归调用帧的压栈与逐层返回

跟踪一次完整递归

下面的程序在进入每一层时打印参数,并在下层返回后打印本层结果。局部变量 partial 只有在对应调用帧恢复执行时才会得到本次下层调用的返回值。

c
#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;
}

预期输出

text
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),或者没有覆盖当前输入的终止条件,调用帧就会持续增加,最终可能耗尽调用栈。递归是否正确,首先要检查“能否停下”,其次才是返回值计算是否正确。

递归之所以能够返回,本质上是每次调用都有独立现场,而且运行时会按栈顺序保存与恢复这些现场。只要终止条件可达,最深一层先给出结果,外层就能依次继续完成尚未执行的部分。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

递归函数为什么能够返回

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通