遞歸求組合算法深度解析：代碼註釋、調用棧圖解與返回流程詳解

網上流傳的一段 Java 遞歸求組合代碼讓許多初學者「繞暈頭」。本文通過詳細的代碼註釋、內存調用棧圖解、關鍵 return 流程追蹤，徹底拆解其運行機制，助你攻克遞歸難關。

原始代碼（已補全缺失部分）

public class CombinationRecursion {
    private static char[] a = { 'a', 'b', 'c' }; // 數據源

    public static void main(String[] args) {
        select(2); // 求長度為 2 的組合
    }

    private static void select(int k) {
        char[] result = new char[k]; // 存放當前組合
        subselect(0, 1, result, k);  // 從 head=0, index=1 開始
    }

    private static void subselect(int head, int index, char[] r, int k) {
        // head: 可選元素起始下標
        // index: 當前要填充的 result 位置 (1-based)
        // 循環條件：i < a.length + index - k  保證剩餘元素足夠填滿 result
        for (int i = head; i < a.length + index - k; i++) {
            if (index < k) {
                // 還沒填滿：選擇 a[i]，遞歸填下一位
                r[index - 1] = a[i];
                System.out.println("i=" + i + ";index=" + index + " (遞歸深入)");
                subselect(i + 1, index + 1, r, k);
            } else if (index == k) {
                // 填滿最後一位：輸出一個組合
                r[index - 1] = a[i];
                System.out.println("i=" + i + ";index=" + index + " (輸出組合) -> " + new String(r));
                // 注意：這裡原代碼還有 subselect(i+1, index+1, r, k)，會導致 index>k 進入 else 返回
                // 實際只需輸出即可，無需再遞歸
            } else {
                // index > k：理論上不應執行到這，因循環條件限制
                System.out.println("++ (異常返回)");
                return; // 結束當前 subselect 調用
            }
        }
        // for 循環結束，隱式返回上層調用
    }
}

關鍵點圖解：以 select(2) 為例

調用樹與 result 狀態變化

main -> select(2)
  -> subselect(head=0, index=1, r=[_,_], k=2)
      i=0: r[0]='a'
        -> subselect(head=1, index=2, r=['a',_], k=2)
            i=1: r[1]='b' -> 輸出 "ab"
            i=2: r[1]='c' -> 輸出 "ac"
        返回
      i=1: r[0]='b'
        -> subselect(head=2, index=2, r=['b',_], k=2)
            i=2: r[1]='c' -> 輸出 "bc"
        返回
      i=2: 循環條件 i < 3+1-2=2 不滿足，結束
  返回

return 流程本質

return 只是結束「當前函數調用」，將控制權交還給「調用它的那一行代碼的下一行」。

• 遞歸深入時：每層 subselect 都是獨立的棧幀，擁有自己的 head, index, i。
• 輸出組合後：當前層 for 循環繼續下一個 i，或循環結束隱式 return 回上層。
• 上層收回控制權：繼續執行調用 subselect 之後的代碼（此處無代碼，繼續自己的 for 循環）。

類比：閱讀一本書（主調用），看到註腳跳轉到附錄（遞歸調用），讀完附錄合上（return），繼續讀正文下一行。

常見誤區澄清

1. 循環條件 i < a.length + index - k：保證從 i 開始的剩餘元素數量（a.length - i）足夠填滿 result 剩餘位置（k - index + 1）。即 a.length - i >= k - index + 1 → i <= a.length + index - k - 1。
2. 原代碼 index==k 分支多調用一次 subselect：會導致 index = k+1 進入 else 打印 "++" 並返回，屬冗餘邏輯，不影響結果但增加棧深度。
3. 數組 r 為引用傳遞：所有遞歸層共用同一個 result 數組，通過 index 定位寫入位置，回溯時自動覆蓋，無需顯式清理。

遞歸學習建議

• 畫調用樹，標註參數、局部變量、返回點。
• 用 IDE 斷點調試，觀察調用棧、變量變化。
• 從簡單案例（如階乘、斐波那契）入手，建立「遞歸 = 縮小問題規模 + 基線條件 + 合併結果」的思維模型。

理解了這個組合生成遞歸，你就掌握了「回溯法」的核心模板，可輕鬆擴展至全排列、子集、N 皇后等經典問題。