GESP 五级 · GESP 202512 C++ 五级 第 23 题

以下 fib 函数计算第 $ n $ 项斐波那契数（$ fib(0)=0 $，$ fib(1)=1 $），其时间复杂度为 $ O(n) $。

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

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

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

【考点】递归复杂度分析｜时间复杂度阶数

递归调用树每层节点数翻倍，$T(n)=T(n-1)+T(n-2)+O(1)$，展开后总调用次数是$\frac{1}{2}(2^{n+1}-1)$，呈指数增长而非线性。$fib(5)$会触发15次调用，$fib(20)$超200万次——指数级复杂度在$n$稍大时立刻爆炸。

命题人把递归的调用次数和输入规模混为一谈。选项A利用"看到n就认为是线性"的惯性思维，忽略了$O(2^n)$才是指数级。更阴险的是把时间复杂度偷换成"计算量"，让人误以为"算得快"就是"复杂度低"。任何递归分支数≥2且无记忆化的，都是指数级。

如果题目改成"带记忆化的递归"，复杂度确实会降为$O(n)$。但原题明确是纯递归，因此必须按指数级判断。刷到这类题先问：有没有重复子问题？没有的话就是指数级，有的话才可能是线性。