遞迴（Recursion）#

遞迴是一種函式自己呼叫自己的程式設計技巧。從演算法思想來看，遞迴是一種特殊的迴圈，透過函式呼叫的堆疊（Stack）來實作重複執行。

遞迴的本質#

去的過程叫「遞」，回來的過程叫「歸」。遞迴將問題分解為更小規模的子問題，直到達到終止條件，再將結果層層返回。

經典比喻：電影院找座位#

你在電影院想知道自己在第幾排，但太暗看不清。於是你問前面的人，前面的人也問他前面的人，直到第一排的人說「我在第一排」，答案再一層層傳回來。

f(n) = f(n-1) + 1，其中 f(1) = 1

遞迴三條件#

只要同時滿足以下三個條件，就可以用遞迴來解決：

1. 問題可分解為子問題 - 子問題是資料規模更小的同類問題
2. 求解思路完全相同 - 問題與子問題除了資料規模不同，處理方式一樣
3. 存在終止條件 - 必須有停止遞迴的邊界條件

拆解問題的三種方向#

同樣是把大問題拆成子問題，方向不同，得到的演算法形態與複雜度也不同。實務上常見三種拆法：

• 自頂向下（Top-Down）：從原始大問題出發，往下拆成同類的小問題，再讓子問題各自遞迴解決，最後把結果合併。歸併排序就是把陣列對半切開、分別排序再合併；二分查找則是從整個區間往下縮到目標所在的半邊。這是最直覺、也最貼近遞迴本身的拆法。
• 自底向上（Bottom-Up）：反過來，從最小的、可以直接回答的子問題開始，一步步往上組合出更大的答案。這條路常常不需要真的呼叫遞迴，而是用一張表把小答案存起來、依序填出大答案——這正與動態規劃的「填表」思路相通。
• 減半（Half-and-Half）：每一步都把問題規模砍掉一半，於是只需 log n 步就能收斂。二分查找每次丟掉一半區間、快速冪每次把指數折半，都是這種拆法，對應 O(log n) 的時間複雜度。

自頂向下對應的就是「自頂向下的遞迴」，自底向上對應的則是「自底向上的遞推」。能在這兩種方向之間自由切換，是寫好遞迴、分治與動態規劃的共同底層能力，詳見演算法思維總綱的「人腦遞推 vs 機器遞迴」。

什麼時候該想到遞迴：訊號詞#

拿到一道新題時，題目敘述裡常藏著「適合遞迴」的訊號詞。看到下面這幾類字眼，可以先往遞迴的方向想：

• 「計算第 n 個…」「列出前 n 個…」——答案依賴於更小規模的同類答案，天然是遞推／遞迴。
• 「所有的組合 / 排列 / 子集…」——需要逐位做選或不選的決策，正是回溯（遞迴的一種）的主場。
• 「樹 / 圖的走訪」——結構本身就是遞迴定義的（一棵樹由子樹組成），用遞迴寫最自然、也最易讀。

訊號詞只是直覺，大約一半時候準。動手前還要多想一步：遞迴至少會吃掉 O(遞迴深度) 的呼叫堆疊空間，深度太大有堆疊溢位的風險。先評估「改成迭代有多難、會不會爆堆疊」，再決定要不要用遞迴。

遞迴程式碼模板#

flowchart TD
    A[進入遞迴] --> B{1. 終止條件<br/>level > MAX?}
    B -->|是| C[處理結果並返回]
    B -->|否| D[2. 處理當前層邏輯]
    D --> E[3. 下探到下一層<br/>recursion level+1]
    E --> F[4. 清理當前層狀態<br/>回溯恢復]
    F --> G[返回上一層]

    style B fill:#fff3e0
    style C fill:#e8f5e9
    style E fill:#e3f2fd
    style F fill:#fce4ec

fun recursion(level: Int, vararg params: Any) {
    // 1. Recursion Terminator (終止條件) - 最優先編寫
    if (level > MAX_LEVEL) {
        processResult()
        return
    }

    // 2. Process Logic (處理當前層邏輯)
    process(level, params)

    // 3. Drill Down (下探到下一層)
    recursion(level + 1, *params)

    // 4. Reverse State (清理當前層狀態，如需要)
    // 例如：恢復全域變數、回溯法中的路徑重置
}

寫遞迴程式碼的關鍵：寫出遞推公式，找到終止條件。不要試圖用人腦展開每一層遞迴，只需思考當前層與下一層的關係。

經典案例：爬樓梯 ^↗#

假設有 n 個台階，每次可以跨 1 或 2 個台階，問有多少種走法？

遞推公式：

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

fun climbStairs(n: Int): Int {
    if (n == 1) return 1
    if (n == 2) return 2
    return climbStairs(n - 1) + climbStairs(n - 2)
}

遞迴的常見問題#

堆疊溢出（Stack Overflow）#

函式呼叫會使用堆疊來保存臨時變數，遞迴深度過深會導致堆疊溢出。

解決方案：限制遞迴深度

var depth = 0

fun f(n: Int) {
    depth++
    if (depth > 1000) {
        throw RuntimeException("遞迴深度超限")
    }
    // ...
}

重複計算#

以費氏數列為例，計算 f(6) 時，f(4) 會被計算多次。

含有大量重複子問題的樸素遞迴，時間複雜度往往是指數級 O(2ⁿ)。

解決方案：記憶化（Memoization）

val memo = HashMap<Int, Long>()

fun fib(n: Int): Long {
    memo[n]?.let { return it }
    if (n <= 2) return 1
    val result = fib(n - 1) + fib(n - 2)
    memo[n] = result
    return result
}

其他問題#

• 時間效率：函式呼叫本身有開銷
• 空間複雜度：遞迴呼叫需要保存現場資料，空間複雜度為 O(n)

遞迴轉迭代#

所有遞迴理論上都可以改寫為迭代（迴圈），但在樹、圖的走訪中，遞迴提供了更好的可讀性。

fun climbStairsIterative(n: Int): Int {
    if (n == 1) return 1
    if (n == 2) return 2

    var prePre = 1
    var pre = 2
    for (i in 3..n) {
        val current = pre + prePre
        prePre = pre
        pre = current
    }
    return pre
}

實戰技巧#

不要人肉遞迴！ 初學者常嘗試在腦中模擬每一層的執行，這很容易「爆腦」。應關注當前層的邏輯以及與下一層的介面，相信子問題已經被正確解決。