边界不能少

写递归的第一件事，就是想清楚“什么时候该停”——这就是边界条件，也叫递归出口。少了它，函数会无限地调用自己，一层层往下套，直到把调用栈占满，程序崩溃（栈溢出）。

看这个漏了边界的阶乘：

int fact(int n) {
    return n * fact(n - 1);   // 危险：永远停不下来
}

fact(3) 调 fact(2)，调 fact(1)、fact(0)、fact(-1)……越走越远，根本回不来。

加上边界就对了：

int fact(int n) {
    if (n == 0) return 1;      // 边界：0 的阶乘是 1
    return n * fact(n - 1);    // 递归：n! = n × (n-1)!
}

求 $n$ 的阶乘，边界就是 $0!=1$（写成 $n\le 1$ 时返回 1 也行）。有了它，递归展开到 $n=0$ 就掉头往回算，逐层交回答案。

检查递归对不对，就盯两点：

• 边界写了没，且递归确实一步步逼近边界（参数在往边界方向变小）；
• 别写出“边界永远碰不到”的情况，比如求偶数阶乘却每次减 2，起点是奇数就跳过了 0。

一句口诀：先写出口，再写递推。