递归会重复算 · 考级冲刺

递归写起来漂亮，但有个大坑：同一个子问题会被重复计算很多遍。斐波那契数列最典型：

$f (n) = f (n - 1) + f (n - 2), f (1) = f (2) = 1$

int fib(int n) {
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);   // 看着很美，其实很慢
}

问题在哪？算 fib(5) 要算 fib(4) 和 fib(3)，而 fib(4) 又要算一遍 fib(3)……同一个 fib(3) 被反复展开。调用次数随 $n$ 指数级膨胀，大约是 $O (2^{n})$ ， $n$ 到 40 多就慢得跑不动了。

改用递推——从小往大一步步推，每个值只算一次：

int fib(int n) {
    int a = 1, b = 1;                 // f(1), f(2)
    for (int i = 3; i <= n; i++) {
        int c = a + b;                // 当前项
        a = b; b = c;                 // 向前挪一格
    }
    return b;
}

这样只需 $O (n)$ 时间、 $O (1)$ 空间，快得多。

结论：能递推就别用朴素递归。如果非要用递归，就把算过的结果存进数组（记忆化），下次直接查表，也能降到 $O (n)$ 。考试里凡是“子问题重叠”的题，递推或记忆化往往是正解。