面试题10：斐波那契数列

从重复子问题出发，比较递归、滚动迭代与矩阵快速幂，并把同一递推迁移到青蛙跳台阶。

学习目标

  • 能解释朴素递归为何调用数指数增长（重复子问题）
  • 能用滚动迭代只保留前两项，O(n) 时间 O(1) 空间计算斐波那契
  • 能把同一递推迁移到青蛙跳台阶问题

从定义直译为何会变慢开始

先预测：计算F(6)时，递归函数会求几次F(4)和F(2)？如果把n增加到40，返回值只有102334155，为什么作者把朴素递归列为“不实用”的第一种解法？

在本题中的从0开始：

F(n)={0,n=0,1,n=1,F(n−1)+F(n−2),n≥2.F(n)= \begin{cases} 0, & n=0,\\ 1, & n=1,\\ F(n-1)+F(n-2), & n\ge 2. \end{cases}

把数学定义直接翻译成函数十分简洁，但F(n-1)和F(n-2)的递归树大量重叠。计算F(6)的左分支会计算F(4)，右分支本身又是F(4)；更小的F(3)、F(2)会在更多路径中反复出现。这些被不同分支请求、输入完全相同的计算叫。也就是说，递归会重复计算相同输入，而函数没有保存任何结果。

递归树增长来自同一子问题被反复展开F(6)F(5)F(4)F(4)F(3)F(3)F(2)F(3)F(2)F(2)F(1)记忆化让每个n只求一次；自底向上连递归栈也省掉。
高亮节点在不同分支重复出现，n增大后调用数按指数级增长。

递归版正确，但调用数指数增长

作者的Fibonacci_Solution1对n=0返回0，对n=1返回1，其余情况递归相加。它在结构上与定义完全一致，因此容易证明：假设更小下标都返回正确值，则两个递归结果相加就是F(n)。

long long fibonacciRecursive(unsigned int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacciRecursive(n - 1)
         + fibonacciRecursive(n - 2);
}

正确不等于高效。若C(n)表示调用次数，它也满足近似斐波那契递推：

C(n)=C(n−1)+C(n−2)+1=Θ(φn),φ=1+52.C(n)=C(n-1)+C(n-2)+1=\Theta(\varphi^n), \qquad \varphi=\frac{1+\sqrt{5}}{2}.

时间按指数增长，递归路径最大深度为n，所以调用栈空间是O(n)。作者测试还调用递归版F(40)，这恰好能直观看出它与循环、矩阵方案的巨大耗时差距，但生产测试不应反复执行更大的朴素递归输入。

加入哈希表或数组记忆化后，每个下标只求一次，时间降为O(n)，但仍需O(n)缓存和O(n)递归栈。既然每个状态只依赖前两项，更直接的做法是改变计算方向。

只保留前两项

作者的Fibonacci_Solution2先处理n小于2的情况，然后从i=2循环到n。每轮开始时，fibNMinusTwo保存F(i-2)，fibNMinusOne保存F(i-1)；两者相加得到F(i)，再把窗口向前滚动一格。

这就是从下往上计算：先得到已知小问题，再按依赖顺序构造大问题。只保存下一状态依赖的有限个历史值称为。每个下标只访问一次，时间O(n)；只保存两个历史值和当前值，额外空间O(1)。

轮次前两项前一项当前项循环不变量
初始01尚未计算对应F(0)、F(1)
i=2011滚动后保存F(1)、F(2)
i=3112滚动后保存F(2)、F(3)
i=4123滚动后保存F(3)、F(4)
i=5235返回F(5)=5
每轮计算前两个变量恰好保存下一项所需的两个历史状态。

更新顺序不能随意交换。若先把previousOne覆盖成current，再用它更新previousTwo，就会丢失旧的F(i-1)。使用独立next临时变量能让右侧都读取旧状态，再一次性滚动：

#include <limits>
#include <stdexcept>
 
unsigned long long fibonacci(unsigned int n) {
    if (n < 2) return n;
 
    unsigned long long previousTwo = 0;
    unsigned long long previousOne = 1;
    for (unsigned int i = 2; i <= n; ++i) {
        if (previousOne >
            std::numeric_limits<unsigned long long>::max() - previousTwo) {
            throw std::overflow_error("Fibonacci overflow");
        }
        const auto next = previousOne + previousTwo;
        previousTwo = previousOne;
        previousOne = next;
    }
    return previousOne;
}

作者返回long long。在有符号64位整数中，F(92)=7540113804746346429仍可表示，F(93)=12200160415121876738已经超过最大值；无符号64位能再容纳F(93)，但F(94)仍溢出。接口应根据需求选择检查溢出、大整数或模运算，不能让有符号溢出默默发生。

把线性递推变成快速幂

斐波那契的相邻两项可以写成固定线性变换。令Q为二阶矩阵：

Q=[1110],Qn=[F(n+1)F(n)F(n)F(n−1)](n≥1).Q= \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}, \qquad Q^n= \begin{bmatrix} F(n+1)&F(n)\\ F(n)&F(n-1) \end{bmatrix} \quad(n\ge1).

因此计算F(n)可以转化为求Q的幂。作者使用：Fibonacci_Solution3求MatrixPower(n-1)并返回左上角；当n为偶数时先求半次幂再平方，为奇数时平方后再乘一次Q。指数每层减半，矩阵大小固定，所以时间O(log n)，递归栈O(log n)。

矩阵快速幂降低的是加法和乘法次数，不会自动解决数值增长。固定宽度整数仍会在同一下标附近溢出，而且矩阵乘法的中间乘积可能先越界。若题目要求对某个模数取余，应在每次乘加后取模并使用足够宽的中间类型；若要求精确大整数，复杂度还要计入大数乘法成本。

迭代二进制快速幂可以把递归栈降为O(1)：维护结果矩阵为单位矩阵，指数当前位为1时乘入底数，每轮底数平方、指数右移。面试中若n规模普通，滚动迭代通常更清晰；矩阵法展示的是如何把固定维线性递推加速到对数轮次。

三种方案如何按约束选择

三种方案不是按“越高级越好”排序。朴素递归最接近定义，适合解释递推和展示重复子问题，但不适合中大输入；记忆化适合状态依赖复杂、无法只保留固定窗口的问题；滚动迭代代码最短、常数小，是本题普通整数范围的首选；矩阵快速幂只有在下标巨大、按模计算或需要推广固定维线性递推时才显出对数轮次优势。

选择前先问输出类型。若要求精确F(100000)，即使循环轮数或矩阵乘法轮数很少，结果本身也有数万位，固定64位接口无法交付；需要大整数，并把复杂度写成随数字位数增长。若只要求F(n) mod M，矩阵乘加可逐步取模，时间优势才更容易保留。

还要问调用模式。连续查询F(0)到F(N)时，一次线性预计算并缓存整个表比对每个下标重复做快速幂更合适；只查询一个极大下标时，快速幂更合适；输入上限只有92时，滚动循环最多92轮，微小且易审计。复杂度结论必须放在真实约束中解释。

青蛙跳台阶先找最后一步

相关题“青蛙跳台阶”规定一次可以跳1级或2级，求到达n级的跳法数。不要因为题目提到斐波那契就直接套式子；先按最后一步分类。由较小状态计算当前状态的规则称为：最后跳1级的方案，在此之前必须到达n-1级；最后跳2级的方案，在此之前必须到达n-2级。两类互斥且覆盖所有方案，所以：

J(n)=J(n−1)+J(n−2),J(1)=1,quadJ(2)=2,J(n)=F(n+1).J(n)=J(n-1)+J(n-2), \qquad J(1)=1,quad J(2)=2, \qquad J(n)=F(n+1).
按最后一步分类：两类方案互斥且穷尽第1级第2级第3级第4级第5级从n-1跳1级从n-2跳2级J(n)=J(n-1)+J(n-2)，初值J(1)=1、J(2)=2。
递推式来自最后一步的完备分类，不是看到数列后机械套公式。

若把“0级台阶”视为已经到达，有一种空方案，可定义J(0)=1，递推从n=2开始保持一致。若业务把n=0定义为0种，入口可以单独处理，但必须明确契约；不同初值会让相同递推产生不同数列。

原书还可把同一思路迁移到2×n矩形用2×1小矩形覆盖：最左侧竖放后剩2×(n-1)，横放时必须上下两块成对，剩2×(n-2)，因此仍是两类完备分解。真正可迁移的能力是“状态加最后选择”，不是记住某个答案长得像斐波那契。

测试要分算法正确性与数值边界

作者对三种方案都检查n=0到10，预期依次为0,1,1,2,3,5,8,13,21,34,55，并检查F(40)=102334155。这覆盖两个初值、第一次递推、多个普通项和能拉开性能差距的较大输入。

测试优化方案时，可以让滚动版和矩阵版在0到安全上限范围内逐项互相校验；递归版只对小n参与，避免测试本身指数爆炸。溢出检查要覆盖“最后一个可表示值”和“第一个不可表示值”，并确认错误不会返回伪造结果。

#include <array>
#include <cassert>
 
void testSmallFibonacci() {
    constexpr std::array<unsigned long long, 11> expected{
        0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
    };
    for (unsigned int n = 0; n < expected.size(); ++n) {
        assert(fibonacci(n) == expected[n]);
        if (n <= 10) {
            assert(fibonacciRecursive(n) == expected[n]);
        }
    }
    assert(fibonacci(40) == 102334155ULL);
}
 
void testFrogSteps() {
    assert(frogWays(1) == 1);
    assert(frogWays(2) == 2);
    assert(frogWays(5) == 8);
}

跳台阶还应枚举小规模方案验证计数，例如n=3恰有1+1+1、1+2、2+1三种；只检查大数无法发现初值偏移。若允许的步长集合改变为1,3,5，状态转移也必须相应改写，不能继续沿用两项递推。

负数输入也要在接口层说清楚。作者参数是unsigned int，调用者若把-1隐式转换进去，会得到一个巨大的无符号数，而不是自然的错误。因此外部输入应先以有符号或字符串形式解析、验证非负和上限，再转换到核心函数类型。测试只覆盖无符号函数内部的0并不能证明调用边界安全。

性能基准应把编译优化、输入和算法分开记录。若直接让朴素递归跑F(40)、循环只跑一次，测得的巨大差距能说明数量级，却不能精确比较常数；更规范的基准会让快速方案重复足够次数、消费返回值防止优化删除，并把溢出检查开销纳入同一配置。

本章练习

练习

问题 1： 朴素递归计算 F(6) 时为什么慢？

问题 2： 滚动迭代如何用 O(1) 空间计算？

问题 3： 青蛙跳台阶与斐波那契如何对应？

概念说明

本章核心概念包括：斐波那契数列。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. 斐波那契数列由F(0)=0、F(1)=1和前两项求和定义。
  2. 朴素递归会重复计算相同下标，时间为指数级、调用栈为O(n)。
  3. 从下往上计算每个状态一次，滚动变量方案时间O(n)、空间O(1)。
  4. 矩阵快速幂把固定二阶递推压缩为O(log n)轮矩阵运算。
  5. 快速算法不消除整数溢出，有符号64位只能精确容纳到F(92)。
  6. 青蛙跳台阶通过最后一步分类得到同一递推，但初值使它等于F(n+1)。
  7. 递推建模必须同时写状态语义、转移、初值、计算顺序和数值范围。
  8. 测试应覆盖小值表、作者的F(40)、算法交叉校验和溢出边界。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

下标
数列项的位置编号，本题 F(0)=0、F(1)=1。
滚动迭代
只保留前两项的迭代计算，O(1) 空间。
矩阵快速幂
把线性递推写成矩阵乘法，用快速幂 O(log n) 求 F(n)。

讨论

评论区加载中…