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

下面 C++ 代码用于求斐波那契数列，该数列第 1、2 项为 1，以后各项均是前两项之和。下面有关说法错误的是（ ）。

int fiboA(int N)
{
    if (N == 1 || N == 2)
        return 1;
    return fiboA(N - 1) + fiboA(N - 2);
}
int fiboB(int N)
{
    if (N == 1 || N == 2)
        return 1;
    int last2 = 1, last1 = 1;
    int nowVal = 0;
    for (int i = 2; i < N; i++)
    {
        nowVal = last1 + last2;
        last2 = last1;
        last1 = nowVal;
    }
    return nowVal;
}

这题考递归与循环的时间复杂度对比。拿到题先看两版代码：fiboA 是递归，fiboB 是迭代。别被代码量骗了，递归看似简洁，实则每次调用又拆成两次，形似二叉树，总调用次数呈指数增长；迭代只是用两个变量滚动更新，循环次数线性。记住：代码行数少≠效率高，命题人专挖这个坑。

最容易错选 C。很多考生觉得递归代码短、逻辑直观，就误以为它效率更高，忽略了递归过程中大量重复计算同一子问题的事实。也有考生混淆递归与循环的调用次数，以为递归也是 O(n)。其实递归版计算 fiboA(20) 时，调用次数远超百万，而迭代版只需 18 次左右。命题人就是利用这种直觉偏差，让只懂语法不懂复杂度的学生掉进陷阱。

【考点】递归与循环｜时间复杂度｜空间复杂度

1. 考纲定位 GESP 五级 C++ 算法模块核心考点。命题人卡住的是“递归与循环的复杂度意识”——多数考生只懂语法，不懂递归会指数爆炸。

2. 解题思维 看到两版代码，先定位函数：fiboA 是递归，fiboB 是迭代。递归版直接映射数学定义 F(n)=F(n-1)+F(n-2)，但每次调用又拆成两次调用，形如二叉树；迭代版用两个变量滚动更新前两项，循环次数即 N-2 次，复杂度线性。

3. 陷阱拆解

• 选项 A：正确，递归与循环对应无误
• 选项 B：正确，递归直观但迭代是程序实现
• 选项 C：陷阱！代码量少≠效率高。fiboA 每次调用又产生两子调用，形如二叉树，总调用次数≈2^N，N=20 时超百万次，效率远低于线性迭代
• 选项 D：正确，代码稍长但效率高

4. 反命题思维 若把 fiboA 改成记忆化递归（加缓存），效率会接近线性；若把 fiboB 循环改成递归但加缓存，也能优化。刷到类似题先问：命题人想考我递归的指数爆炸，还是迭代的常数空间？

5. 考频与趋势 图形结构：题库共考过 213 题，覆盖 6 个考试级别（2021-2026）；逐年分布：2021 年 1 题、2023 年 32 题、2024 年 61 题、2025 年 56 题、2026 年 40 题、null 年 23 题；分赛事：GESP 七级 78 题、GESP 八级 73 题、GESP 五级 31 题、GESP 六级 26 题、CSP 提高级 3 题、CSP 入门级 2 题 图的基本概念：题库共考过 281 题，覆盖 11 个考试级别（2007-2026）；逐年分布：2007 年 1 题、2008 年 2 题、2009 年 2 题、2010 年 2 题、2011 年 3 题、2013 年 3 题、2014 年 2 题、2015 年 2 题、2016 年 1 题、2017 年 3 题、2018 年 1 题、2019 年 2 题、2020 年 1 题、2021 年 4 题、2022 年 3 题、2023 年 36 题、2024 年 61 题、2025 年 58 题、2026 年 71 题、null 年 23 题；分赛事：GESP 八级 85 题、GESP 七级 85 题、GESP 五级 36 题、GESP 六级 27 题、CSP 提高级 13 题、NOIP 普及组 初赛 12 题、NOIP 提高组 初赛 10 题、CSP 入门级 7 题、GESP 三级 3 题、GESP 一级 2 题、GESP 二级 1 题 组合数学：题库共考过 110 题，覆盖 4 个考试级别（2023-2026）；逐年分布：2023 年 16 题、2024 年 35 题、2025 年 38 题、2026 年 12 题、null 年 9 题；分赛事：GESP 八级 58 题、GESP 六级 26 题、GESP 五级 18 题、GESP 七级 8 题 排列组合基础：题库共考过 147 题，覆盖 8 个考试级别（2007-2026）；逐年分布：2007 年 1 题、2008 年 1 题、2009 年 2 题、2010 年 1 题、2014 年 2 题、2016 年 1 题、2017 年 1 题、2019 年 4 题、2020 年 5 题、2021 年 4 题、2022 年 2 题、2023 年 19 题、2024 年 40 题、2025 年 43 题、2026 年 12 题、null 年 9 题；分赛事：GESP 八级 58 题、GESP 六级 26 题、GESP 五级 18 题、CSP 提高级 15 题、CSP 入门级 13 题、GESP 七级 8 题、NOIP 提高组 初赛 7 题、NOIP 普及组 初赛 2 题

6. 预测 暂无足够依据预测未来可能怎么考。