GESP 六级 · GESP202609 C++ 六级 第 25 题

下列递归程序能得到正确的斐波那契数，其时间复杂度和空间复杂度都是 $O(n)$。

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

看到递归题先画调用树。斐波那契的递归树是二叉树，深度为n，但节点数呈指数增长。时间复杂度看总调用次数，空间复杂度看栈帧最大层数。

易错点在于把递归调用次数当成时间复杂度，把栈深度当成空间复杂度。斐波那契的递归树是二叉树，深度为n，但节点数呈指数增长。时间复杂度看总调用次数，空间复杂度看栈帧最大层数。

1. 考纲定位

本题考查《GESP 六级 C++ 大纲》中递归算法与复杂度分析模块。命题人放这道题，就是要卡住那些只会"套模板写递归"的考生——他们能写出正确的斐波那契代码，但完全不懂复杂度怎么算。

2. 解题思维

第一步：识别递归结构

fib(n) 调用 fib(n-1) 和 fib(n-2)

这是典型的二叉递归树。每个非叶子节点产生 2 个子调用。

第二步：画小数据验证

序列 1,1,3,5,9,15... 这不是等差也不是等比，但明显是指数级增长。

第三步：数学推导

设 T(n) 为 fib(n) 的调用次数：

• T(0) = T(1) = 1
• T(n) = 1 + T(n-1) + T(n-2)

展开：

• T(n) = 1 + T(n-1) + T(n-2)
• = 1 + [1 + T(n-2) + T(n-3)] + T(n-2)
• = 2 + 2T(n-2) + T(n-3)

继续展开，最终得到 T(n) = 2^n - 1。

第四步：空间复杂度

递归调用栈的最大深度是多少？

• fib(n) → fib(n-1) → fib(n-2) → ... → fib(0)

最坏路径长度 = n，所以空间复杂度是 O(n)。

第五步：对照选项

题目说"时间复杂度和空间复杂度都是 O(n)"。

• 时间：O(2^n) ≠ O(n)
• 空间：O(n) ✓

结论：B 正确。

3. 陷阱拆解

选项 A 的陷阱：命题人利用考生"递归=线性"的直觉误区。很多学生看到"每次减 1"就以为复杂度是 O(n)，完全忽略了递归树的分支爆炸。

最阴险的细节：题目问的是"时间复杂度和空间复杂度都是"，这是一个合取命题。只要有一个不成立，整个命题就为假。空间复杂度 O(n) 是对的，但时间复杂度 O(2^n) 是错的，所以答案选 B。

4. 反命题思维

如果改题，可以变成：

• "下列程序时间复杂度是 O(2^n) 吗？" → 答案 A
• "下列程序空间复杂度是 O(n) 吗？" → 答案 A
• "下列程序是 O(n) 时间复杂度的吗？" → 答案 B

或者换一种考法：

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

这题完全一样，因为只是把返回值写成了局部变量，不影响调用次数。

再或者改成：

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

加个 static int count = 0; 在每次调用时 count++，最后返回 count。这题就变成了"求调用次数"，答案还是 O(2^n)。