GESP 八级 · GESP 202409 C++ 八级 第 15 题

下面 fibonacci 函数的时间复杂度为（ ）。

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

洛谷注：本题原题无正确选项，洛谷上做了调整。

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

判断题中注意"一定""总是""所有""唯一"等绝对化表述通常是错误的。但也要结合具体知识点判断。

【考点】递归复杂度分析｜斐波那契数列｜递推关系求解

🎯 考纲定位 本题卡在GESP大纲"递归与分治"模块的进阶要求上，命题人专攻考生对递归树规模感知的盲区。绝大多数人看到递归就以为是O(n)，却忽略了调用次数呈指数级爆炸的本质。

🧠 解题思维 递归树里每个节点都会再拆成两个子节点，深度为n，总节点数≈F(n+1)。直接套用斐波那契通项公式F(n)≈φ^n/√5（φ=(1+√5)/2），即可得出时间复杂度为O(φ^n)。这是处理纯递归结构的通用招数：数调用次数=解递推式=代入通项。

🪤 陷阱拆解 选项A和C都是对递归的惯性误判——以为"每层只调用一次"就是O(n)。选项D把递归树当成二分查找的平衡树，完全曲解了调用结构。最阴险的是B项的φ^n，这是斐波那契数列的标准增长量级，但很多人只记得O(2^n)的粗略上界，却忽略底数φ≈1.618才是精确渐近值。

🔄 反命题思维 若给函数加记忆化，复杂度瞬间跌落为O(n)；若改用矩阵快速幂，则能压到O(log n)。刷到递归题先问：调用次数递推式是什么？别被递归的优雅骗了，数节点才是硬道理。