GESP 七级 · GESP 七级样题（C++ 组） 第 2 题

下面定义的函数用来求斐波那契数列的 $F(n)$，其中 $n \leq 10$，描述正确的是（ ）。 

斐波那契数列：f(1)=f(2)=1，f(n)=f(n-1)+f(n-2)。递归实现简单但效率低（O(2^n)），循环实现O(n)。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】数组｜递归｜记忆化

🎯 考纲定位：本题考查数组与递归/迭代结合的状态保存，属于 GESP 七级"算法基础"模块。命题人卡住的是考生对"状态保存"与"递归终止条件"概念混淆的弱点。

🧠 解题思维：n≤10 递归深度有限，不会栈溢出。代码中数组 f 显然用于缓存中间结果（记忆化），避免重复计算。递归终止条件通常是 n=0 或 n=1 直接返回 f[0] 或 f[1]，而不是数组元素本身。所以 B 正确，A 错。C 倍增法用于快速幂或矩阵快速幂，n 这么小没必要，且代码未体现。D 算法能正常结束，错。

🪤 陷阱拆解：

• A 选项把"终止条件"偷换成"数组元素"，利用考生对递归底层的模糊认知。
• C 选项用"倍增法"制造混淆，因为斐波那契确实有倍增写法，但题目代码明显是线性记忆化。
• D 选项利用 n≤10 的边界，让考生误以为递归会栈溢出，实则不会。
• 最阴险的是 A 的绝对化表述"是递归终止条件"，命题人故意让考生只背"递归需要终止条件"而不区分"条件"与"值"，掉进去就选错。

🔄 反命题思维：

• 若把 n 改成 10^9，答案会变，倍增法才必要，C 可能正确。
• 若把数组改成动态规划（自底向上），B 依然成立但 A 更错。
• 若去掉数组，改用纯递归，D 可能正确（栈溢出）。
• 刷到类似题，先问"命题人想考我什么"：是考状态保存、递归终止条件、还是倍增法？