递归终止条件

一句话理解

终止条件是递归不再往下调用的出口。

为什么要学

没有出口就会无限递归，RE 或 TLE。

讲解

通常处理最小规模：n=0、空数组、走到终点。要写在递归调用之前。

出口可以有多个。先写出口，再写递归，是好习惯。

例子

int f(int n) {
    if (n <= 1) return 1; // 出口
    return f(n - 1) + f(n - 2);
}

n<=1 直接返回，不再调用自己。

常见错误

• 出口写错成 n==0，但有人从 1 调到负数。用 n<=1 更稳。
• 出口放在递归调用后面，永远走不到。