概述#

遞迴問題雖然種類繁多，但大多遵循類似的模式。一個問題是遞迴的良好跡象，是它可以由子問題的解所建構出來。

以下類型的敘述通常是遞迴題的訊號：

• 「設計一個演算法來計算第 n 個…」
• 「寫程式列出前 n 個…」
• 「實作一個方法計算所有…」

根據經驗，人們對「這像遞迴題」的直覺大約有 50% 的準確率。這個直覺很有價值，但同樣要對反方向保持開放——即使最初覺得是遞迴，也可能用迭代解更好。多做練習，識別遞迴問題的能力會越來越強。

How to Approach（如何解題）#

遞迴解由定義上是建立在子問題的解之上的。很多時候，這意味著計算 f(n) 只需在 f(n-1) 的結果上做一些調整。其他情況下，你可能需要先解決前半段資料，再解決後半段，然後合併結果。

將問題分解為子問題的三種常見方式：

Bottom-Up Approach（由下而上）#

通常是最直覺的方式：

• 從最簡單的情況開始（例如只有一個元素的列表）
• 思考如何解兩個元素的問題，再三個，以此類推
• 關鍵：如何在前一個 case 的解的基礎上建構出當前 case 的解

Top-Down Approach（由上而下）#

有時比 Bottom-Up 更抽象，但適合某些問題：

• 思考如何將問題 N 分解為子問題
• 注意子問題之間可能有重疊（這是 Dynamic Programming 的切入點）

Half-and-Half Approach（對半分割）#

除了上述兩種，還可以將資料集對半分割：

• Binary search：在已排序陣列中找元素，先確定在哪一半，再遞迴搜尋
• Merge sort：分別排序兩半，再合併有序的兩半

Recursive vs. Iterative Solutions（遞迴 vs. 迭代）#

遞迴演算法可能非常耗記憶體。每次遞迴呼叫都會在 call stack 上加一層，遞迴深度為 n 時，至少需要 O(n) 的記憶體。

因此，通常更好的做法是以迭代方式實作遞迴演算法。所有遞迴演算法都可以改寫為迭代版本，雖然有時程式碼複雜度會上升。

在一頭埋進遞迴實作之前，先問問自己：改用迭代實作有多難？與面試官討論兩者的 trade-off。

Dynamic Programming & Memoization（動態規劃與記憶化）#

Dynamic Programming（DP）的本質很簡單：找到遞迴演算法中重複計算的子問題，把這些結果快取起來供後續使用。

另一種方式是研究遞迴呼叫的模式，然後改用迭代實作，同樣「快取」之前的結果。

術語說明：有些人把 Top-Down DP 叫做「memoization」，把「dynamic programming」僅用於 bottom-up 的工作。本書不做此區分，兩者都稱為 dynamic programming。

範例：Fibonacci 數列#

以計算第 n 個 Fibonacci 數為例，逐步展示遞迴 → Memoization → Bottom-Up DP 的演進。

純遞迴實作#

int fibonacci(int i) {
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibonacci(i - 1) + fibonacci(i - 2);
}

時間複雜度分析：遞迴樹中每個節點（除了 base case）都有兩個子節點，樹深度為 n，因此約有 O(2^n) 個節點，時間複雜度為 O(2^n)。

許多人誤以為是 O(n) 或 O(n^2)。用遞迴樹來分析遞迴演算法的時間複雜度是非常有用的技巧。

在電腦上實測，計算第 50 個 Fibonacci 數可能需要超過一分鐘。

Top-Down Dynamic Programming（Memoization）#

觀察遞迴樹，fib(3) 被計算了 2 次，fib(2) 被計算了 3 次。為什麼要重複計算？

只要快取每次計算過的 fib(i) 結果即可：

int fibonacci(int n) {
    return fibonacci(n, new int[n + 1]);
}

int fibonacci(int i, int[] memo) {
    if (i == 0 || i == 1) return i;

    if (memo[i] == 0) {
        memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
    }
    return memo[i];
}

時間複雜度：O(n)。每個值只被計算一次，之後直接從 cache 取得（黑盒）。

遞迴樹現在幾乎是一條直線，深度為 n，每個節點最多一個子節點（另一個從 cache 取），共約 2n 個節點，因此為 O(n)。

實際效果驚人：純遞迴計算第 50 個 Fibonacci 數需要一分鐘以上；Memoization 版本可以在幾毫秒內計算到第 10,000 個（當然 int 會早就 overflow）。

Bottom-Up Dynamic Programming#

從已知的 base case 開始，由小到大計算：

int fibonacci(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;

    int[] memo = new int[n];
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i < n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n - 1] + memo[n - 2];
}

進一步優化：發現每次只用到前兩個值，不需要整個陣列：

int fibonacci(int n) {
    if (n == 0) return 0;
    int a = 0;
    int b = 1;
    for (int i = 2; i < n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return a + b;
}

這本質上是將最近兩個 Fibonacci 值存在 a 和 b 中，每次迭代計算下一個值 c = a + b，再更新 (b, c) 到 (a, b)。

雖然用 Fibonacci 這樣簡單的例子來解釋 DP 看起來有點「殺雞用牛刀」，但真正理解這個過程，對解決本章中那些真正困難的 DP 題目至關重要。

本章面試題列表#