GESP 五级 · GESP 202403 C++ 五级 第 6 题

下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）？

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)。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】递归｜递推｜时间复杂度

🎯 考纲定位 GESP 五级算法模块核心考点之一。命题人挖递归指数爆炸的坑，卡住只会背"递归=O(n)"公式的学生。这道题本质是考你懂不懂递归树怎么长，而非背结论。

🧠 解题思维 看到递归函数先画调用树：fib(n) 会同时调用 fib(n-1) 和 fib(n-2)。每层都分叉两次，第 k 层约有 2^k 个节点。总节点数≈2^n，这就是时间复杂度。通法：遇到递归题，先别急着套公式，画几层调用关系看增长规律。

🪤 陷阱拆解 A 选项 O(1) 是常数时间错觉，D 选项 O(log n) 是二分查找的套路，B 选项 O(n) 是迭代版本的复杂度——命题人把迭代和递归混在一起考。最阴险的是让你觉得"只是减个 n，线性调用不就行了"，忽略了每次调用都会再拆两个新调用。

🔄 反命题思维 若改成带记忆化的递归，复杂度会降到 O(n)。刷到这类题先问自己："这是纯递归还是带缓存？"