GESP 七级 · GESP 202506 C++ 七级 第 11 题

下面程序的输出为（ ）。

#include <iostream>
using namespace std;
int rec_fib[100];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}
int main() {
    cout << fib(6) << endl;
    return 0;
}

模拟程序执行过程，逐行跟踪变量变化，特别关注循环边界和递归终止条件。

模拟执行时注意：① 循环变量的起始和终止值；② 递归的边界条件；③ 数据类型转换和精度问题。

【考点】递归与记忆化搜索｜数组作为缓存｜斐波那契数列计算

解题思维：看到 fib 函数和全局 rec_fib 数组，立刻想到递归+记忆化。n≤1 是递归基，直接返回。遇到 rec_fib[n]==0 说明该值未计算过，递归求 fib(n-1)+fib(n-2) 并回填。调用 fib(6) 时，会依次触发 fib(5)、fib(4)……每个 n 只算一次，最终得到第 6 个斐波那契数 8。这类题通法：递归结果可复用就全局缓存，数组初始 0 可作"已算"标志。

陷阱拆解：D 项"随机"利用考生对递归执行顺序的误解，以为每次调用都重复计算；B 项 13 是 fib(7) 的值，数字记忆陷阱；C 项 64 是 2⁶，混淆斐波那契与幂次。最阴险的是 rec_fib 检查——若只背结论不理解本质，会误以为无条件递归，导致认为结果不确定。

反命题思维：命题人想考"记忆化是否影响结果"。把 rec_fib 改为局部变量，每次递归都会重新计算，输出仍是 8，但效率指数级下降。刷到类似题，先问自己"这道题到底想验证什么"。