遞歸函數棧幀演變圖解：以冪集生成遞歸為例

問題代碼 (冪集遞歸)

void GetPowerSet(int i, SqList A, SqList& B) {
    if (i >= A.length) { Output(B); return; }
    int x = A.data[i];
    int k = B.length;
    B.data[k] = x;   // 選擇：加入當前元素
    B.length++;
    GetPowerSet(i+1, A, B); // 遞歸進入：處理下一個元素
    B.length--;      // 回溯：撤銷選擇
    GetPowerSet(i+1, A, B); // 遞歸進入：不選當前元素
}

棧幀演變過程 (A={1,2,3})

初始調用: GetPowerSet(0, A, B={})
│
├─ 選 1: B={1} → GetPowerSet(1, A, B={1})
│   ├─ 選 2: B={1,2} → GetPowerSet(2, A, B={1,2})
│   │   ├─ 選 3: B={1,2,3} → GetPowerSet(3) → Output({1,2,3}) ← 返回
│   │   └─ 不選 3: B={1,2}   → GetPowerSet(3) → Output({1,2})   ← 返回
│   │   返回到層級 2 (i=2 結束)
│   └─ 不選 2: B={1} → GetPowerSet(2, A, B={1})
│       ├─ 選 3: B={1,3} → Output({1,3})
│       └─ 不選 3: B={1}   → Output({1})
│       返回到層級 1 (i=1 結束)
└─ 不選 1: B={} → GetPowerSet(1, A, B={})
    ├─ 選 2: B={2} → ...
    └─ 不選 2: B={} → ...
        ├─ 選 3: {3}
        └─ 不選 3: {} (空集)

關鍵認知：棧幀的「壓入/彈出」對應「選擇/回溯」

為何第二次輸出符合預期？

第一次遞歸返回時，執行 `B.length--` 將 `B` 恢復為「未選當前元素」的狀態。此時棧幀仍在同一層級，局部變數 `i`、`x`、`k` 保持不變。第二次遞歸以此已回溯的狀態為起點，探索「不選」分支，因此輸出正確。

棧幀記憶體佈局 (簡化)

棧頂 (最新)                    棧底 (main)
┌─────────────────────────┐
│ GetPowerSet(i=3)        │ ← 輸出 {1,2,3} 返回
├─────────────────────────┤
│ GetPowerSet(i=2)        │ ← 執行 B.length-- 回溯
├─────────────────────────┤
│ GetPowerSet(i=1)        │ ← 等待第二次遞歸返回
├─────────────────────────┤
│ GetPowerSet(i=0)        │ ← 最初調用點
├─────────────────────────┤
│ main()                  │
└─────────────────────────┘

迭代版對比 (顯式棧)

void GetPowerSetIter(SqList A) {
    struct Frame { int i; int state; }; // state: 0=進入, 1=已選回溯, 2=完成
    Stack st;
    SqList B = {0};
    st.push({0, 0});
    while (!st.empty()) {
        Frame& f = st.top();
        if (f.i >= A.length) { Output(B); st.pop(); continue; }
        if (f.state == 0) { // 選擇分支
            B.data[B.length++] = A.data[f.i];
            f.state = 1;
            st.push({f.i+1, 0});
        } else if (f.state == 1) { // 回溯後，不選分支
            B.length--;
            f.state = 2;
            st.push({f.i+1, 0});
        } else { // 兩分支皆完
            st.pop();
        }
    }
}

顯式棧版本將隱式調用棧物質化，更易理解狀態機本質。