从递归到递推 · 考级冲刺

同一个问题，常有两种算法方向。递归是“从大问题往小问题问”：要算 $f (n)$ ，就先去问 $f (n - 1)$ 、 $f (n - 2)$ ，一层层往下，直到最小的已知情况（边界）才返回。递推反过来，“从小往大算”：先摆好最小的答案，再用循环一步步推出更大的。

以斐波那契为例， $f (n) = f (n - 1) + f (n - 2)$ ：

// 递归：从大往小问，会重复计算，指数级慢
int f(int n) {
    if (n <= 2) return 1;
    return f(n-1) + f(n-2);
}

// 递推：从小往大算，一遍循环，O(n)
int g(int n) {
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;   // 由前两个推出当前
        a = b; b = c;
    }
    return b;
}

朴素递归会把 $f (n - 2)$ 等子问题重复算很多遍，退化成指数级 $O (2^{n})$ ；递推每个值只算一次， $O (n)$ ，还省掉了递归的栈空间。所以能改成递推时，通常更快、更省内存。