波仔
🧠 第三章 编程语言
📄 一句话概括

第 24 项四种写法都给 46368，但耗时是 12.278 对 0.004 毫秒。 递归在 n=32 时要调用 7049155 次。第 90 项用浮点公式算，比精确值少 8584。

📝 本节和前面几节的关系

上一节排数字，这一节算数列。 斐波那契是「同一个答案、几百倍代价」最干净的例子，也是理解递归代价的入口。

一、四种写法，一个答案

Demo 写了四种：递归、迭代、记忆化、矩阵快速幂。n=24 时全部给出 46368。 耗时差得很远：递归 12.278 毫秒，迭代 0.004，记忆化 0.015，矩阵快速幂 0.013。 递归慢在哪？它把同一个子问题反复算。 算 F(24) 要算 F(23) 和 F(22)，而 F(23) 里面又要再算一遍 F(22)——重复 exponentially 增长。 记忆化就是把算过的存起来，下次直接取。 这一个改动，把 12.278 毫秒压到 0.015 毫秒，快了约八百倍——而且代码只多了两行。

二、递归到底调了多少次

Demo 直接算了调用次数：n=20 要 21891 次，n=24 要 150049 次，n=28 要 1028457 次， n=32 要 7049155 次。 规律是 2×F(n+1)-1。也就是说，调用次数本身就是一个斐波那契数——每加 1，工作量涨约 1.6 倍。 这就是为什么递归版本看起来优雅、实际不能用：n=40 就是三亿次调用，等半天。 能算出「调用多少次」比「感觉有点慢」有用得多。估算耗时、判断会不会超时，靠的都是这个数。

三、矩阵快速幂：把递推变成乘方

斐波那契可以写成矩阵形式：把向量 [F(n), F(n-1)] 乘一个固定矩阵，就得到 [F(n+1), F(n)]。 于是求第 n 项变成求那个矩阵的 n 次方。 而 n 次方可以用快速幂：每次把指数减半、底数自乘，复杂度从 O(n) 降到 O(log n)。 Demo 的实现里没有幂运算符，是手写的 2×2 矩阵乘法加二进制拆解。 n=24 时它跑 0.013 毫秒，跟迭代差不多——小 n 时优势看不出来，n 到百万级才显出来。 这套「矩阵表示 + 快速幂」不只用于斐波那契，线性递推都能这么加速。 它是「把递推问题变成矩阵乘法」这个套路的最小样例。

四、精度：第 90 项差了 8584

Demo 最后对比了精确值与浮点通项公式： - 整数迭代：F(90) = 2880067194370816120 - 浮点公式：2880067194370824704 - 差 8584 通项公式 F(n) = (φⁿ - ψⁿ) / √5 在数学上是精确的，但 φ 是无理数，用浮点存必然截断， n 一大误差就放大。 结论：算整数数列不要碰浮点。 真要算大数，用 Python 的 int（它没有上限），或者上 decimal 提高精度。

五、动手 Demo：四种算法与一次精度崩塌

打出前 20 项；对 n=24 用递归、迭代、记忆化、矩阵快速幂各算一次并计时； 再算 n=20／24／28／32 时递归的调用次数；最后对比 F(90) 的精确值与浮点通项公式的结果。

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def fib_memo(n):
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

def fib_mat(n):          # 矩阵快速幂
    r = [list((1, 0)), list((0, 1))]
    m = [list((1, 1)), list((1, 0))]
    e = n
    while e:
        if e & 1:
            r = mul(r, m)
        m = mul(m, m)
        e >>= 1
    return r[0][1]

实跑输出：

--------------------------------------------------------------------
实例 3：斐波那契数列，四种算法与一次精度崩塌
--------------------------------------------------------------------
  前 20 项                 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

  算法         F(24)   耗时(ms)
  ----------------------------
  递归         46368     10.410
  迭代         46368      0.003
  记忆化       46368      0.012
  矩阵快速幂   46368      0.011
  n=24 时递归还没慢到离谱；每加 1，它就要多算一倍。

   n   递归要调用的次数
  --------------------
  20              21891
  24             150049
  28            1028457
  32            7049155
  次数是 2*F(n+1)-1，随 n 指数长。n=32 已经七百万次了。

  F(50)                    12586269025
  F(90) 整数算             2880067194370816120
  F(90) 浮点公式           2880067194370824704
  整数减浮点               -8584
  n 越大，浮点通项公式的误差越大——第 90 项差了 8584。
  算整数数列就别碰浮点，除非你能接受「差不多」。

前 20 项是 0, 1, 1, 2, 3, 5, 8, …，到第 19 项是 4181。 注意第一项从 0 开始，不同教材从 1 开始，写法要跟题目对齐。 四种写法的耗时：12.278、0.004、0.015、0.013 毫秒。 递归比迭代慢三千倍，而结果完全一样。 调用次数那四行最能说明递归的代价：21891 → 150049 → 1028457 → 7049155。 n 从 20 涨到 32，工作量涨了 322 倍。 F(50) 是 12586269025，F(90) 是 2880067194370816120——Python 的整数没有上限， 这么长照样精确。 浮点公式给出 2880067194370824704，比真值大 8584。 小数点后十几位的精度，在这个量级上已经撑不住了。

30 秒实验

  1. 把递归版本加一行 print(n)，跑 n=6，数一数它到底打了几行。
  2. 用 memo 字典做缓存，把递归版改造成记忆化版，量一下提速倍数。
  3. 想一想：为什么矩阵快速幂在 n=24 时看不出优势，n 很大时才显出来？

常见误区

  1. 「递归写法优雅，就用递归」——n=40 要三亿次调用。
  2. 「记忆化是高级技巧」——加两行缓存，快八百倍。
  3. 「数学公式总是精确的」——浮点一存就截断，第 90 项差 8584。
自测三问（点开对答案） 1. 递归求斐波那契为什么慢？ —— 同一个子问题被反复计算，调用次数本身按斐波那契增长。 2. 记忆化只改了什么，就快了约八百倍？ —— 把算过的结果存进字典，下次直接取，不再重复递归。 3. 为什么 F(90) 的浮点公式会算错？ —— φ 是无理数，浮点存储必然截断，n 越大误差越大。

数列算完，下一个实例练排版——九九乘法表看着简单，四种版式差别不小。

相关笔记