CSP-S 提高级 · CSP 2025 提高级第一轮 第 14 题

斐波那契数列的定义为 $F(0)=0$, $F(1)=1$, $F(n)=F(n-1)+F(n-2)$。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的，而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这种巨大差异的根本原因是？

这题是送分题，别整那些虚头巴脑的。直接抓住核心：为什么递归算得慢？因为同一个子问题被反复算了很多遍。把这点想透了，其他选项全是干扰，根本不用纠结。

学生最容易掉进选项 A 的陷阱，觉得递归慢是因为栈开销大或者操作系统限制了深度。其实栈开销只是常数因子，哪怕栈无限深，只要子问题重复算，总时间依然是指数级的。命题人就是喜欢用这种‘看似合理实则无关’的干扰项来考你是否真正理解时间复杂度的本质。

考点直击

这道题考查的是时间复杂度分析与递归算法特性，核心在于区分“常数因子影响”和“量级影响”。

概念大白话

• 重叠子问题：递归过程中，同一个子问题被重复计算多次。比如算 F(5) 时要算 F(3)，算 F(4) 时又要算 F(3)，F(3) 就被算了两次。
• 时间复杂度：描述算法运行时间随输入规模 n 增长的趋势。指数级 O(2^n) 意味着 n 每加 1，时间翻倍；线性级 O(n) 意味着时间随 n 等比例增长。

命题人怎么挖坑

命题人很狡猾，选项 A 说“栈开销过大”，选项 B 说“系统限制深度”。这两个都是常数因子层面的问题。就算你忽略栈开销（假设栈无限），或者用尾递归优化把栈压到最小，朴素递归算 F(n) 的时间依然是指数级的。所以 A 和 B 都是干扰项，目的是看你是否把“栈”和“计算次数”混为一谈。

思考心法：拿到题先想什么

1. 先算次数：朴素递归 F(n) 的调用次数满足 T(n) = T(n-1) + T(n-2) + 1，近似于 2^n。这是指数爆炸的根源。 2. 再看存储：DP 用数组存结果，每个子问题只算一次，总次数 O(n)。 3. 对比差异：指数 vs 线性，差异巨大。根本原因只能是“重复计算没被利用”，即重叠子问题。

避坑指南

• 别被“栈开销”忽悠：栈开销是 O(n)，相对于 O(2^n) 可以忽略不计。
• 别纠结“系统限制”：系统限制通常导致程序崩溃，而不是让复杂度从指数变线性。
• 记住：重叠子问题是递归慢的根源，记忆化是解决它的钥匙。

考频与趋势

从题目关联知识点数据看：

• 递归函数是高频考点，共考过 115 题，覆盖全部考试级别。其中 CSP 提高级考过 9 题，GESP 五级 35 题，NOIP 提高组初赛 10 题，分布非常广。
• 记忆化搜索共考过 5 题，CSP 提高级考过 1 题，说明“递归 + 记忆化”是必考组合。
• 动态规划共考过 120 题，CSP 提高级考过 6 题，GESP 六级 38 题，NOIP 普及组初赛 2 题，是重中之重。

预测

基于数据，CSP 提高级在“递归/DP”类题目上历来稳定出题，2025 年已有 15 题涉及递归函数，2026 年预测仍会保持高频。未来大概率继续以“朴素递归 vs 记忆化/DP”的对比为题，考察学生对重叠子问题本质的理解，干扰项仍会集中在“栈开销”“空间复杂度”等概念混淆上。暂无足够依据预测具体题型变化，但核心考点不会变。