GESP 五级 · GESP 202506 C++ 五级 第 24 题

函数 puzzle 定义如下，则调用 puzzle(7) 程序会无限递归。

int puzzle(int n) {
    if (n == 1) return 1;
    if (n % 2 == 0) return puzzle(n / 2);
    return puzzle(3 * n + 1);
}

递归问题关注两点：① 递归边界（终止条件）；② 递归关系（递推公式）。分析时展开前几步即可看出规律。

注意递归深度过大会导致栈溢出。递归必须包含终止条件，否则造成无限递归。

【考点】递归调用｜函数终止条件｜模拟执行

GESP五级考查递归函数的执行流程，命题人借3n+1的经典序列，卡住学生“以为奇数必增大”的直觉。

从puzzle(7)开始逐次模拟：7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1。该过程与Collatz猜想路径一致，最终必达n==1的终止条件，递归栈清空返回1，全程无循环。

错误选项A利用"3n+1奇数必增”思维定式，却忽略了偶数n/2会骤降；更阴险的是未验证n==1的终止条件——若n=0会陷入puzzle(0)循环。命题人把“序列是否终止”偷换为“是否无限递归”，专坑只背结论不模拟的学生。

反推：若题干改为"puzzle(27)是否终止”，答案不变；但若n=0，代码将陷入无限递归。刷到递归题先问：base case真的能拦住所有路径？