GESP 五级 · GESP 202406 C++ 五级 第 1 题

下面 C++ 代码用于求斐波那契数列，该数列第 $1$、$2$ 项为 $1$，以后各项均是前两项之和。函数 fibo() 属于（ ）。

int fibo(int n) {
    if (n <= 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;

    int a = 1, b = 1, next;
    for (int i = 3; i <= n; i++) {
        next = a + b;
        a = b;
        b = next;
    }
    return next;
}

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

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

【考点】循环控制｜迭代算法｜算法分类

🎯 考纲定位（考点定位） 本题考查《GESP 五级 C++ 编程语言》中的"循环控制"与"算法分类"模块。命题人意在卡住考生对"迭代"与"递归""枚举"的混淆——五级考生普遍对 for 循环的语义掌握不够扎实，容易把"循环递推"误判为"枚举"或"递归"。

🧠 解题思维（拆解与通法） 看到代码先抓结构：初始化 a=1,b=1，然后用 for (int i=3; i<=n; i++) 不断执行 next=a+b;a=b;b=next。这是典型的"状态逐步更新"的迭代过程，时间复杂度 O(n)。通法：凡是用循环不断更新几个变量、最后返回结果，就是迭代；函数自调用才是递归；穷举所有可能才是枚举；每一步只选最优局部才是贪心。

🪤 陷阱拆解（命题人的套路） A 枚举算法：枚举是"把所有情况都跑一遍，取最优/符合条件"。代码里 for 只是按序号一步步算，并没有"尝试所有组合"，所以 A 错。 B 贪心算法：贪心是"每一步只选局部最优"。斐波那契递推每一步都是固定的加法，不存在"选择"，所以 B 错。 D 递归算法：递归是"函数自己调用自己"。代码里根本没有 fibo 的自调用，而是用 for 循环，所以 D 错。 最阴险的细节：题目强调"第 1、2 项为 1，以后各项均是前两项之和"，这很容易让人联想到"递归定义"，从而误选 D。但代码实现完全没用递归，只是用循环模拟递归的"状态传递"。如果你只背结论（"斐波那契是递归"），就会掉进这个陷阱。

🔄 反命题思维（教练升华） 命题人视角：如果把 for 改成 while，答案不变，还是迭代；如果把循环体改成 fibo(i-2)+fibo(i-1)，那就变成递归算法，答案会选 D；如果把循环改成穷举所有拆分方式，那就是枚举。刷到类似题，先问自己："这道题是在循环里更新状态，还是在函数里调用自己？"——这是区分迭代与递归的关键。