微軟 C 語言筆試題深度解析：遞歸與循環的滿二叉樹模型

題目重現

#include 
int a = 0, count = 0;

void MysteryFunc(int b) {
    if (b == 0) {
        count++;
        printf("%d:%d\n", count, a);
    }
    a = a + b;
    for (int i = b - 1; i >= 0; --i)
        MysteryFunc(i);
}

void main() {
    MysteryFunc(5);
    printf("\n%d\n", a);
}

問題：輸出結果為何？

核心觀察

1. count 僅在 b==0 時遞增，實際上是葉節點計數器，輸出格式為 葉節點序號:當前a值。
2. a 為全局累加器，每次調用 MysteryFunc(b) 時加 b。
3. 遞歸結構：MysteryFunc(b) 會依次調用 MysteryFunc(b-1) 到 MysteryFunc(0)，形成樹狀調用。

遞歸樹結構分析

以 MysteryFunc(2) 為例：

MysteryFunc(2)
├─ a+=2 (a=2)
├─ i=1: MysteryFunc(1)
│   ├─ a+=1 (a=3)
│   ├─ i=0: MysteryFunc(0) → 輸出 count=1, a=3
│   └─ 返回
├─ i=0: MysteryFunc(0) → 輸出 count=2, a=3
└─ 返回

發現規律：每個節點 b 產生 b 個子節點 b-1, b-2, ..., 0。這構成一棵滿二叉樹（非嚴格二叉，但每個節點的子節點數等於其值）。

前序遍歷累加模型

程式執行順序為前序遍歷（根→左→右）。每次訪問節點時執行 a += b。葉節點（b==0）觸發輸出，此時 a 為從根到該葉的路徑上所有節點 b 值之和。

完整輸出推導

對於 MysteryFunc(5)，樹高 5，葉節點 16 個（2^(5-1)）。輸出序列：

1:15
2:15
3:16
4:16
5:19
6:19
7:20
8:20
9:26
10:26
11:27
12:27
13:30
14:30
15:31
16:31
31  ← 最後主函數輸出 a 最終值

數學驗證

最終 a 為所有節點 b 值之和。滿二叉樹中，值為 k 的節點出現次數為 2^(5-k)（根 5 出現 1 次，4 出現 2 次，... 0 出現 16 次）。

總和 = 5×1 + 4×2 + 3×4 + 2×8 + 1×16 + 0×16
     = 5 + 8 + 12 + 16 + 16 + 0 = 57  ← 等等，與 31 不符！

修正：實際樹非滿二叉，而是每個節點 b 生成 b 個子節點。節點分佈：

• 5: 1 個
• 4: 1 個（5 的子節點）
• 3: 2 個（5 和 4 的子節點）
• 2: 4 個
• 1: 8 個
• 0: 16 個（葉）

總和 = 5×1 + 4×1 + 3×2 + 2×4 + 1×8 + 0×16
     = 5 + 4 + 6 + 8 + 8 = 31  ✓

遞歸函數數學定義

設 S(b) 為調用 MysteryFunc(b) 過程中 a 的總增量：

S(0) = 0
S(b) = b + Σ_{i=0}^{b-1} S(i)   (b > 0)

計算：S(1)=1, S(2)=2+1+0=3, S(3)=3+3+1+0=7, S(4)=4+7+3+1+0=15, S(5)=5+15+7+3+1+0=31。

迭代優化實現（O(n) 時間 O(1) 空間）

int a = 0;
int S[6] = {0};  // S[b] 存儲 MysteryFunc(b) 的增量
for (int b = 1; b <= 5; b++) {
    S[b] = b;
    for (int i = 0; i < b; i++) S[b] += S[i];
}
a = S[5];  // 31

結語

此題考察遞歸樹建模、前序遍歷累加、數學歸納推導三重能力。關鍵在於識別「每個節點生成值為 0~b-1 的子節點」這一生成規則，並將全局變量 a 的累加過程映射為樹的前序遍歷路徑和。掌握「畫樹→找規律→寫遞推→優化迭代」的通用解題框架，可應對各類遞歸循環混合筆試題。