GESP 四级 · GESP 202409 C++ 四级 第 24 题

以下代码用递推法求斐波那契数列的第 $n$ 项，时间复杂度为指数级。

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    int f0 = 0; // F(0)
    int f1 = 1; // F(1)
    int current;

    for (int i = 2; i <= n; i++) {
        current = f0 + f1; // F(n) = F(n-1) + F(n-2)
        f0 = f1;
        f1 = current;
    }

    return current;
}

答案B。在循环中遍历数组并累积结果时，注意累加变量的初始值和每次循环的更新方式。

for循环体可能一次都不执行！这是和while循环一样的"先判断后执行"机制。

【考点】递推优化｜时间复杂度分析｜变量复用

---

1. 🎯 考纲定位 GESP 四级 编程 模块，命题人卡住的是"递推=指数级"的刻板印象。四级大纲要求掌握递推思想，但多数学生把"递推法"等同于递归，直接套用递归的时间复杂度结论。这题就是专门考你：会不会真正读代码，而不是只会背结论。

---

2. 🧠 解题思维 看到代码先不急着判断，先数循环次数。循环从 i=2 到 i≤n，一共执行 n-1 次，每次只做了常数级操作（两变量相加、赋值）。时间复杂度 O(n)，线性级。

通法：判断时间复杂度，核心是数循环层数 + 每层操作数。递归题看递归树深度与分支数，循环题看循环迭代次数与内层操作。四级递推题大多可以优化成 O(n) 甚至 O(1)，关键看是否用到了「滚动变量」。

---

3. 🪤 陷阱拆解 A 选项正确，是典型"望文生义"陷阱——看到"递推"就自动联想到斐波那契递归的 O(2^n)。命题人故意用「递推法」这个词，因为递推既可以是递归也可以是迭代。

阴险细节：函数里根本没有递归调用，只有 for 循环。滚动变量 f0、f1 复用，每次迭代只保留上一、上上两项，空间 O(1)。如果你只背"递推是指数级"，就会掉进这个坑。

---

4. 🔄 反命题思维 如果把循环改成递归：

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

那答案就变 A 了——递归版本确实是 O(2^n)。

刷到这类题，先问自己：代码里到底有没有递归调用？循环迭代了多少次？ 别被名词牵着走，直接看控制流。