C / C++ / 系统课时

终止条件写错会发生什么

终止条件写错会发生什么

递归函数一旦缺少可达的终止条件,调用就会不断创建新的栈帧,最终耗尽栈空间。本课用可控示例观察“不收敛”的递归怎样增长,并总结写终止条件时最关键的检查方法。

学习目标

  • 解释终止条件与递归规模收敛之间的关系
  • 区分“没有终止条件”和“终止条件永远到不了”两类错误
  • 能用递归参数的变化方向判断是否存在栈耗尽风险

递归为什么必须收敛

每次函数调用都会在调用栈中留下一个栈帧,用来保存参数、局部变量和返回位置。普通函数返回后栈帧会被释放;递归只有在最深层先返回后,外层调用才有机会逐层退出。

因此,一个可靠的递归必须同时满足两个条件:存在明确的终止条件,并且每次递归调用都让问题规模朝终止条件靠近。只写出 if (n == 0) 并不够,如果后续调用让 n 越来越远,条件仍然永远不会触发。

正确收敛与错误递归的栈变化对比

两类最常见的终止错误

第一类是根本没有终止条件。下面是片段示例,它故意省略退出分支,依赖调用者传入整数参数;不要实际运行。

c
void countdown_wrong(int n) {
    printf("%d\n", n);
    countdown_wrong(n - 1);
}

无论 n 变成什么值,函数都会继续调用自己。第二类更隐蔽:代码里有终止条件,但递归参数朝错误方向变化。

c
int factorial_wrong(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial_wrong(n + 1);
}

这个片段同样不要运行。若从正整数开始,n 会不断增大,永远到不了 0。真实程序随后可能因平台和运行环境不同出现栈溢出、段错误、访问冲突或进程被终止,不能依赖某一种固定报错形式。

用可控程序观察不收敛

为了不真的把栈耗尽,可以增加一个“诊断上限”,只模拟错误方向的前几层调用,再与正确收敛的递归比较。

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

预期输出

text
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,而要沿着每一条递归分支追踪“规模度量”。对整数递归可以观察参数变大还是变小,对数组区间可以观察区间长度,对树递归可以观察是否进入更小的子树。

还要确认终止判断发生在继续递归之前,并覆盖最小输入。若函数有多个递归分支,每个分支都必须保证规模收敛;只要有一条分支可以无限延伸,仍然可能耗尽栈空间。

递归错误最值得警惕的信号不是“调用次数很多”,而是问题规模没有单调接近一个可达的基本情况。把这件事检查清楚,比单独盯着终止条件那一行更可靠。

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

目录与阅读设置

阅读设置

17

记录一个想法

终止条件写错会发生什么

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

登录哪都通