GESP 六级 · GESP 202312 C++ 六级 第 8 题

下面的 fiboA() 和 fiboB() 两个函数分别实现斐波那契数列，该数列第 $1$、第 $2$ 项值为 $1$，其余各项分别为前两项之和。下面有关说法错误的是（ ）。

int fiboA(int n)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return 1;
    else
    {
        return fiboA(n - 1) + fiboA(n - 2);
    }
}

int fiboB(int n)
{
    if ((n == 0) || (n == 1)) {
        fiboB[n] = n;
        return n;
    }
    else {
        if (fiboB[n] == 0) {
            fiboB[n] = fiboB(n - 1) + fiboB(n - 2);
        }
        return fiboB[n];
    }
}

这题表面考函数写法，实则考复杂度意识。拿到题先看调用树：fiboA 每次都要把问题拆成两个子问题，中间层会重复算无数次；fiboB 用数组把算过的值存起来，下次直接取。记住：代码行数短不代表快，指数级时间复杂度才是致命伤。

很多同学看到 fiboA 代码只几行，就下意识觉得它快，选了 D，这是典型的直觉陷阱。另外，有人分不清记忆化递归和纯递归的区别，以为 fiboB 里那个判断条件只是个小优化，其实它把重复计算彻底消除了。还有人会把时间复杂度和空间复杂度搞混，认为 fiboB 用了数组就慢，忽略了递归调用栈的深度问题。

【考点定位】 这道题出自 GESP 六级《算法与程序设计》模块，核心考查的是递归实现与动态规划（记忆化搜索）的对比，以及算法时间复杂度的直观理解。命题人特意选了斐波那契数列这个经典案例，因为它在两种写法下的表现差异极其悬殊，是区分“会写递归”和“懂算法效率”的绝佳试金石。

【概念拆解：人话讲清楚两个函数】 先看 fiboA： 这是一个纯粹的递归函数。它的逻辑很简单：如果 n 是 0 或 1，直接返回 1；否则，返回 fiboA(n-1) + fiboA(n-2)。 关键点在于：它没有任何缓存机制。当你调用 fiboA(5) 时，它会去算 fiboA(4) 和 fiboA(3)；而算 fiboA(4) 时，它又会去算 fiboA(3) 和 fiboA(2)。你会发现，fiboA(3) 被算了两次，fiboA(2) 被算了三次……这种重复计算在 n 变大时是指数级爆炸的。

再看 fiboB： 这个函数利用了全局数组 fiboB 来存结果。逻辑是：如果 n 是 0 或 1，直接赋值并返回；否则，先检查 fiboB[n] 是否已经算过（这里用 0 表示未计算，因为斐波那契数列第 0 项定义为 1，但为了区分“没算过”和“算出来是 0”，通常会把初始值设为 -1 或 0 并配合判断，题目里用 0 判断未计算）。如果没算过，就递归算出结果并存入数组；如果算过了，直接返回数组里的值。 这就是动态规划里的“记忆化搜索”写法。它把重复计算变成了 O(1) 的查表操作。

【命题人怎么挖坑：为什么 D 是错的】 选项 A 说 fiboA 用递归，这没错，一眼就能看出来。 选项 B 说 fiboB 用动态规划，也没错，它确实通过数组缓存了中间结果，符合动态规划的核心思想。 选项 C 说 fiboA 在 N 较大时有大量重复计算，这也是对的，刚才分析的调用树就是铁证。

那么问题出在 D 上。D 说“由于 fiboA 代码较短，其执行效率较高”。 这就是命题人设下的直觉陷阱。很多初学者看到代码行数少，就默认它快。但算法效率不看代码长短，看的是时间复杂度。 fiboA 的时间复杂度是 O(2^N)（近似），而 fiboB 是 O(N)。 当 N=10 时，fiboA 大概要跑几千次加法；当 N=20 时，fiboA 就要跑一百多万次；当 N=30 时，fiboA 几乎要跑一亿次，这时候哪怕你的电脑再快，也跑不完。而 fiboB 无论 N 多大，都只需要跑 N 次。 所以，代码短不代表效率高，反而因为没做缓存，效率极低。D 选项把“代码短”和“效率高”强行关联，显然是错误的。

【思考心法：拿到题先想什么】 遇到这种对比题，别急着看选项，先自己推一下： 1. 识别模式：fiboA 是纯递归，fiboB 是带数组缓存的递归。 2. 推导复杂度：纯递归通常指数级，带缓存的通常是线性级。 3. 找反例：让 N 变大，看哪个会崩。fiboA 在 N 稍大就会超时，fiboB 不会。 4. 对照选项：哪个说法违背了这个规律，就是错的。

【避坑指南】

• 别被代码行数迷惑：短代码可能逻辑简单但效率低，长代码可能冗余但效率高。
• 别忽略初始值陷阱：fiboB 里用 0 判断未计算，如果题目里斐波那契数列第 0 项定义为 0，那这个判断就错了。但本题定义第 0 项为 1，所以 0 是安全的未计算标记。
• 别混淆空间和时间：fiboB 用了数组，空间复杂度是 O(N)，但时间复杂度降到了 O(N)，这是用空间换时间的典型做法，不能因为它用了数组就说它慢。

【考频与趋势】 动态规划是近年来 GESP 和 CSP 的绝对热点。题库共考过 120 题，覆盖 9 个考试级别。逐年分布来看，2023 年考了 14 题，2024 年猛增到 24 题，2025 年更是达到了 25 题，2026 年预计也有 30 题。这说明动态规划在考试中的比重越来越大，尤其是 GESP 六级（考了 38 题）和七级（29 题）是重灾区。 递推（79 题）和简单动态规划（94 题）也频繁出现，尤其是 2023-2026 年，每年都有十几到二十几题。

【未来预测】 基于数据，未来几年动态规划相关题目会继续保持高频，尤其是结合斐波那契、爬楼梯、背包问题等经典模型。命题人可能会继续用“代码短 vs 效率高”这种反直觉的选项来挖坑，或者考察记忆化递归与普通递归的细微差别（比如数组初始化、边界条件）。另外，随着题目难度提升，可能会出现更复杂的 DP 状态设计，但基础概念（如本题的缓存思想）始终是必考内容。暂无足够依据预测具体新题型，但“反直觉效率对比”这一套路大概率还会继续。