CSP-S 2025 第一轮 第14题：斐波那契数列的定义为 F(0)=0, F(1)=1, F(n)=F(n-1)+F

题目

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

选项

• A. 递归函数调用栈开销过大
• B. 操作系统对递归深度有限制
• C. 朴素递归中存在大量的重叠子问题未被重复利用
• D. 动态规划使用了更少的数据存储空间

答案

C

题解

答案选 C：朴素递归中存在大量的重叠子问题未被重复利用。

例如计算 \(F(5)\) 时：

• 需要计算 \(F(4)\) 和 \(F(3)\)；
• 计算 \(F(4)\) 时，又要计算一遍 \(F(3)\)；
• 这些计算还会继续重复求解 \(F(2)\) 等更小的子问题。

朴素递归不保存已算出的结果，导致相同子问题被反复计算，总计算量呈指数级增长。动态规划保存并复用结果，每个 \(F(i)\) 只计算一次，因此时间复杂度为 \(O(n)\)。

A 的调用栈开销不是复杂度差异的根本原因；B 与重复计算无关；D 讨论的是空间，且动态规划不一定使用更少的空间。