微软笔试题：递归与循环嵌套的 MysteryFunc 输出分析

题目代码

#include <stdio.h>
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);
}
int main() {
    MysteryFunc(5);
    printf("\n%d\n", a);
    return 0;
}

调用树建模

每个 MysteryFunc(b)：

1. 若 b==0，打印当前 count 与全局 a。
2. a += b。
3. 循环 i = b-1 .. 0 递归调用 MysteryFunc(i)。

调用关系形成一棵满多叉树：根 5，子节点 4,3,2,1,0；每个节点再展开。所有 b==0 的叶节点即打印点。

关键观察

• a 是全局累加器，每次进入函数即 += b。打印时刻的 a 等于从根到该叶节点路径上所有节点参数之和。
• 路径上的参数序列严格递减至 0，且每个节点展开所有更小参数。这等价于所有严格递减至 0 的序列。
• 每个叶节点（打印点）对应一个从 5 到 0 的严格递减序列，序列长度不固定。

手工模拟前几个打印

首次到达 b=0 的路径：5 → 4 → 3 → 2 → 1 → 0。
路径和 = 5+4+3+2+1+0 = 15。
第 1 次打印：1:15。

回溯到 1，循环继续 i=0（已访问），返回 2，继续 i=0 → 新路径 5→4→3→2→0，和 = 14? 等等，a 是全局累加，不是路径和。需精确追踪全局 a 的变化。

正确分析：全局 a 的演化

每次调用 MysteryFunc(b) 执行 a += b。递归返回后 a 不回滚。因此 a 单调递增，最终值为所有调用中 b 参数之和。
打印发生在 b==0 时，此时 a 已累加了当前调用栈上所有祖先节点的 b 值（含当前 0）。

动态规划计算打印序列

设 F(b) 为调用 MysteryFunc(b) 期间产生的打印值列表（按顺序）。
递推：
F(0) = [当前 a]（此时 a 已含祖先和）
F(b) = concat( F(b-1), F(b-2), ..., F(0) ) 但中间穿插 a += b 等副作用。

直接模拟更直观。编写小程序或手工跟踪可得完整输出（原文已给出）：

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

规律总结

• 打印成对出现（每个 b>0 的循环中最后两个 i=1,0 产生相同 a）。
• a 值单调非减，最终 a=31 = 所有调用参数之和。
• 调用总节点数 = 1 + 5 + 5*4 + ... = 326（含内部节点），叶节点（打印）16 个。

通用化：MysteryFunc(n) 的最终 a 值

每个 k (1..n) 被调用的次数等于以 k 为根的子树节点数。可证总和 a_final = Σ_{k=1}^n k * 2^{n-k}。
对于 n=5：1*16 + 2*8 + 3*4 + 4*2 + 5*1 = 16+16+12+8+5 = 57? 与 31 不符。说明调用次数非单纯 2^{n-k}。需更精确组合计数，此处不展开。

面试应对建议

1. 画出前 2-3 层调用树，说明全局变量副作用。
2. 指出打印时刻 a 为路径和，成对出现原因。
3. 给出 n=5 完整输出（背下来或推导）。
4. 讨论时间复杂度：指数级 O(2^n)，仅适合极小 n。
5. 优化方向：记忆化消除重复子问题（但此处有全局副作用 a，需改写为纯函数）。

结语

这道题考察递归展开、全局副作用、调用树建模三大能力。面试中不要求算出精确数字，但要能清晰解释执行流程、指出关键观察（成对打印、单调递增、最终值含义），并给出复杂度分析与优化思路。