C / C++ / 系统课时
终止条件写错会发生什么
终止条件写错会发生什么
递归函数一旦缺少可达的终止条件,调用就会不断创建新的栈帧,最终耗尽栈空间。本课用可控示例观察“不收敛”的递归怎样增长,并总结写终止条件时最关键的检查方法。
学习目标
- 解释终止条件与递归规模收敛之间的关系
- 区分“没有终止条件”和“终止条件永远到不了”两类错误
- 能用递归参数的变化方向判断是否存在栈耗尽风险
递归为什么必须收敛
每次函数调用都会在调用栈中留下一个栈帧,用来保存参数、局部变量和返回位置。普通函数返回后栈帧会被释放;递归只有在最深层先返回后,外层调用才有机会逐层退出。
因此,一个可靠的递归必须同时满足两个条件:存在明确的终止条件,并且每次递归调用都让问题规模朝终止条件靠近。只写出 if (n == 0) 并不够,如果后续调用让 n 越来越远,条件仍然永远不会触发。

两类最常见的终止错误
第一类是根本没有终止条件。下面是片段示例,它故意省略退出分支,依赖调用者传入整数参数;不要实际运行。
void countdown_wrong(int n) {
printf("%d\n", n);
countdown_wrong(n - 1);
}无论 n 变成什么值,函数都会继续调用自己。第二类更隐蔽:代码里有终止条件,但递归参数朝错误方向变化。
int factorial_wrong(int n) {
if (n == 0) {
return 1;
}
return n * factorial_wrong(n + 1);
}这个片段同样不要运行。若从正整数开始,n 会不断增大,永远到不了 0。真实程序随后可能因平台和运行环境不同出现栈溢出、段错误、访问冲突或进程被终止,不能依赖某一种固定报错形式。
用可控程序观察不收敛
为了不真的把栈耗尽,可以增加一个“诊断上限”,只模拟错误方向的前几层调用,再与正确收敛的递归比较。
#include <stdio.h>
void trace_wrong_direction(int n, int depth, int max_depth) {
printf("wrong depth=%d, n=%d\n", depth, n);
// 诊断保护只用于演示,真实错误递归通常没有这层保护。
if (depth == max_depth) {
printf("stop: diagnostic guard reached\n");
return;
}
trace_wrong_direction(n + 1, depth + 1, max_depth);
}
void countdown(int n) {
printf("countdown n=%d\n", n);
// 先判断终止条件,再继续缩小问题规模。
if (n == 0) {
return;
}
countdown(n - 1);
}
int main(void) {
trace_wrong_direction(3, 0, 3);
countdown(3);
return 0;
}预期输出
wrong depth=0, n=3
wrong depth=1, n=4
wrong depth=2, n=5
wrong depth=3, n=6
stop: diagnostic guard reached
countdown n=3
countdown n=2
countdown n=1
countdown n=0前半段的参数持续远离可能的终点,只是被人工保护条件截断;后半段每次让 n 减一,最终触发 n == 0,随后所有栈帧都能正常返回。
写终止条件时检查三件事
检查递归是否安全时,不要只看有没有 if,而要沿着每一条递归分支追踪“规模度量”。对整数递归可以观察参数变大还是变小,对数组区间可以观察区间长度,对树递归可以观察是否进入更小的子树。
还要确认终止判断发生在继续递归之前,并覆盖最小输入。若函数有多个递归分支,每个分支都必须保证规模收敛;只要有一条分支可以无限延伸,仍然可能耗尽栈空间。
递归错误最值得警惕的信号不是“调用次数很多”,而是问题规模没有单调接近一个可达的基本情况。把这件事检查清楚,比单独盯着终止条件那一行更可靠。