GESP 四级 · GESP 202506 C++ 四级 第 12 题

下述斐波那契数列计算的时间复杂度是（ ）。

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

答案D。斐波那契数列：1,1,2,3,5,8,13,... 递推式F(n)=F(n-1)+F(n-2)，是递归算法的经典例子。

仔细审题，注意限定词和否定词。用排除法缩小选项范围。

【考点】递归 | 时间复杂度分析

🎯 考纲定位 考查递归实现的时间复杂度，GESP四级算法模块核心考点。命题人专门在此处设卡，检验考生对递归调用树规模的直观感知——多数学生会误以为递归深度n决定复杂度，却忽略了分支指数级扩散。

🧠 解题思维 解题关键：画出递归调用树。每个节点代表一次fibonacci调用，根节点fibonacci(n)分裂为左子树fibonacci(n-1)和右子树fibonacci(n-2)，深度为n，每层节点数呈指数增长。计算总节点数即得时间复杂度（每个节点执行常数时间操作）。对于fibonacci(n)，调用次数等于斐波那契数F_{n+1}，其渐近行为为O(2^n)。

🪤 陷阱拆解 陷阱拆解：A选项陷阱在于混淆"递归深度"与"调用次数"，误将树高当作节点总数；C选项源于对递推式误读，以为n^3是三次递推；最阴险的是D选项，命题人利用考生对"斐波那契=动态规划=O(n)"的刻板印象，故意给出未优化的递归代码，诱使用DP经验直接跳过分析。若考生只背结论，会误选A或C，因为两者都看似"合理"。

🔄 反命题思维 反命题思维：若将递归改为带记忆化的动态规划，时间复杂度立降为O(n)；若增加fibonacci(n-3)项，复杂度变为O(3^n)；若改为迭代实现，复杂度仍为O(n)。刷到此类题先问：代码是否重复计算？有没有缓存？命题人想让你判断"朴素递归"与"优化递归"的区别。