前言：为什么从一个数列开始

你大概见过这串数。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

第一项是 0，第二项是 1，之后每一项都等于前两项相加。0 加 1 是 1，1 加 1 是 2，1 加 2 是 3，2 加 3 是 5。一个会做加法的小孩能把它续写下去，写一整天都不需要乘除。

但是这串数不太安分。

你拿它写一段最直接的递归程序，它会反过来教你：看上去最像数学定义的程序，跑起来最不像样。

你拿它数一段走廊能用多少种方式铺砖，它会从你手里那一块块砖里长出来。

你把它装进一个 $2 \times 2$ 的小方块，它就变成"状态怎么从这一步变到下一步"。

你问它第 $n$ 项到底是多少，它会从一串整数里拿出一个 $\sqrt{5}$ 给你看。

你只盯着它的最后一位数字，它会像钟表一样循环，60 步回到原地。

你抛硬币，要求不出现连续两个正面，它又一次跑出来，当起了计数员。

这么多门，都被同一串数推开。

听起来像在讲不同的故事。一段慢程序、一条铺砖走廊、一个 $2 \times 2$ 矩阵、一个 $\sqrt{5}$、一个 60 步的循环、一个抛硬币的游戏。它们都从同一条小规则里长出来：每一项等于前两项之和。

这本书想讲的就是这件事。

黄金比例会出现，但不在这本书的中心

黄金比例 $\varphi=\frac{1+\sqrt5}{2}$ 这本书里会出现。它必须出现，因为它和斐波那契数列真正连在一起：相邻两项之比会越来越靠近 $\varphi$，闭式公式里也直接写着它。这部分很美，我们会慢慢看清楚它是怎么进来的。

$\varphi$ 之外，松果、向日葵、鹦鹉螺、希腊神庙、达·芬奇素描、各种宽长比的人脸，这些就不在这本书里了。它们都好看，也都真实存在，但停在这一步有点亏。

数学最好看的部分，常常在"它为什么会这样"。一个现象只被展示成奇迹，我们能欣赏一秒。一个现象被拆开看清楚机制，我们能带走它一辈子。

所以黄金比例会出现，作为整条故事线里的一个角色，在它该出现的位置出现。

这本书真正要看什么

同一个递推 $F_n=F_{n-1}+F_{n-2}$ 可以被写成定义、被执行成程序、被存成一张表、被加速成对数时间的算法、被压缩进一个 $2 \times 2$ 矩阵、被解成带有 $\sqrt{5}$ 的闭式公式、被一段一段铺成砖、被画成点和线、被追问整除性、被模掉一个数看余数、被嵌进一个概率分子里。

这些是同一种结构换了十一种说法。

每一种说法背后，是一种数学分支在问自己的问题。

程序会问：怎么算？算法会问：什么工作在重复，怎么省掉它？矩阵会问：状态怎么从这一步变到下一步？闭式公式会问：能不能直接跳到第 n 项？组合数学会问：这个数到底在数什么？图论会问：能不能把它画成点和线？数论会问：整数运算里留下了什么规律？模运算会问：只看余数会怎样？概率会问：所有可能里，有多少个是我们想要的？

斐波那契数列的好处是：换一个问题，不用换对象。

它够小，能放在脑子里。它够厚，能撑住一整本这种来回翻译的练习。

学完之后，你不会变成斐波那契专家。但你会比以前更习惯一件事：数学里那些被切成不同课程的内容，其实从来没有真正分开过。它们只是同一种结构被不同的人用不同的口音说出来。

一个小例子，先垫垫底

讲一个具体一点的，好让你知道这本书喜欢什么样的瞬间。

想象一条长度为 4 的窄走廊，你要用 1 格砖和 2 格砖把它铺满。问有多少种铺法。

我们干脆把所有铺法列出来：

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2

一共 5 种。

这个 5 是五种你能亲手摆出来的铺法。你能拿五张纸各画一种，铺在地上对比。

现在再看一条长度为 $n$ 的走廊。最后一块砖要么是 $1$ 格，要么是 $2$ 格。如果最后一块是 $1$ 格，前面剩下长度 $n-1$ 的走廊，铺法数就是长度 $n-1$ 的铺法数。如果最后一块是 $2$ 格，前面剩下长度 $n-2$ 的走廊，铺法数就是长度 $n-2$ 的铺法数。

所以总数满足 $A(n) = A(n-1) + A(n-2)$。它就是斐波那契递推。

这一次，斐波那契递推从"最后一块砖到底是 1 格还是 2 格"这个问题里长出来。

这本书喜欢的就是这种时刻：一个具体的小例子，一个简单的分情况，一个熟悉的结构突然冒出来。

比魔术更稳，也比魔术更耐看。

这本书的结构

全书分前言、二十一章正文、尾声。

第一部分"递推"是第 1 到 6 章。第 1 章从兔子、楼梯、铺砖三个场景长出递推。第 2 章把这段递推翻译成递归程序，跑几个例子，第一次感觉慢。第 3 章展开调用树，分析慢的原因。第 4 章给程序装上记忆，把指数级压成线性。第 5 章让程序跳步，用快速倍增做到对数时间。第 6 章再用矩阵快速幂，给出另一种对数时间算法。

第二部分"换语言"是第 7 到 15 章，九章六种语言。第 7 章用矩阵看（状态视角），第 8 章用闭式公式看（推导 Binet 公式），第 9 章追问 $\sqrt{5}$ 怎么消失，第 10 章用铺砖和楼梯的计数看，第 11 章把计数推广到子集和二进制串，第 12 章用图看，第 13 章用恒等式的代数证法看，第 14 章用恒等式的组合证法看，第 15 章用生成函数看。

第三部分"整数性质"是第 16 到 19 章。第 16 章看整除性，第 17 章看模周期（发现循环），第 18 章解释为什么是 60（素数情况与中国剩余定理），第 19 章看 Zeckendorf 表示，用斐波那契数反过来表示任意整数。

第四部分"推广"是第 20 和 21 章。第 20 章把斐波那契搬到抛硬币概率里，第 21 章问"等到首次出现连续两个正面平均要抛几次"，并推广到 k-bonacci。尾声把视角拉到一般线性递推，回到"换语言"这条主线。

每章大约三四千字。可以按顺序读，也可以跳着读。但建议前六章按顺序，因为后面反复用到第 2、3、4 章里建立的几个工具。

一句关于精度的说明

不同书对斐波那契数列的起点写得不一样。有的从 $F_1 = 1, F_2 = 1$ 开始，有的从 $F_0 = 0, F_1 = 1$ 开始。

本书统一用 $F_0 = 0, F_1 = 1$。这样写的好处是和矩阵、闭式公式、组合计数都对得整齐。代价是某些常见说法要平移一下：比如"爬 $n$ 阶楼梯的方法数等于 $F_{n+1}$"而不是 $F_n$。索引看起来差 $1$，但里面的逻辑是稳的。

这种细节在书里第一次出现时会说清楚。之后用到就不再重复。

小数字是护栏。每次写完一个公式，我会拿 $n = 1, 2, 3$ 代进去试一下。如果对不上，我们就回去修索引，而不是挥手遮过去。

这是数学的一部分。

最后说一下语气

我尽量不用"神奇""奥秘""宇宙密码"这一类词。它们把数学讲成巫术，听起来热闹，听完什么也带不走。

我尽量不用"本章我们将""由此可见""具有重要意义""我们可以得出三点启示"这种教材腔。它们把数学讲成文件，读起来像在签合同。

我想写的语气大概是这样：

"你看，这儿有个小机关。我们把它拆开看看。拆完你会发现，它还连着后面那一串东西。"

仅此而已。

开始

我们从最普通的一个动作开始：问下一项从哪儿来。

一个当前的数，可能由前面几个更小的数决定。一个大问题，可能可以拆成两个更小的问题。最后一步，可能就解释了整个递推。

这是第一扇门。

推开门，后面那些门会一扇一扇亮起来。

第 1 章 一个递推是怎么长出来的

1202 年，比萨的莱昂纳多写了一本叫《计算之书》的著作。莱昂纳多有个外号叫 Fibonacci，意思是波那契的儿子。这本书把印度-阿拉伯数字和算法介绍到欧洲，影响很大。书里第 12 章有一个问题，大意是这样：

有人把一对刚出生的小兔子放进一个围起来的地方。小兔子要一个月长大，长大之后每个月生一对新的小兔子。假设兔子都不死，问一年后有多少对兔子。

我们一格一格地数。

第 0 个月：1 对小兔子。
第 1 个月：还是 1 对，但它们已经长大。
第 2 个月：这对大兔子生了 1 对小兔子，所以总共 2 对。
第 3 个月：原来的大兔子再生 1 对小兔子，上个月的小兔子刚长大还不生，所以总共 3 对。
第 4 个月：两对大兔子各生一对，上个月新生的还太小不生，所以总共 5 对。

继续下去：8 对、13 对、21 对、34 对。

这串数就是 1, 1, 2, 3, 5, 8, 13, 21, 34。

兔子故事本身不重要。重要的是它怎么算出来的。

把"本月怎么从上月变来"分成两种情况

每个月的兔子总数，可以分成两群：上个月就已经在的兔子，加上这个月新生的兔子。上个月就已经在的兔子，这个月都还活着（题目假设兔子不死），所以这一群就是上个月的总数。

新生兔子有多少对？等于上个月已经长大、可以生小兔子的兔子对数。哪些兔子在上个月已经长大？再上一个月就已经在的所有兔子。因为它们要么当时已经长大，要么上个月从小变大会在下个月开始生。所以"新生兔子对数"等于"再上一个月的兔子总数"。

把这个分情况用一句话写出来：

本月总数 = 上月总数 + 再上月总数。

如果记第 $n$ 个月的兔子对数为 $R_n$，那么 $R_n=R_{n-1}+R_{n-2}$。兔子数列从 $1,1$ 开始，整个故事就被一行式子压缩完了。

这是斐波那契递推的第一次出现。它从"今天和昨天有什么关系"分成两种情况，然后写下来。

把这个动作看清楚

刚才那段推导里藏着一个动作。这个动作后面会反复用到，所以这里值得把它讲清楚。

我们想要的是"第 n 个月有多少对兔子"。我们没有直接去算它。我们把它拆成了两种情况：上个月就已经有的兔子，加上这个月新生的兔子。这两种情况加起来就是全部兔子，而且不重不漏。

拆完之后，"上个月就已经有的兔子"等于"上月总数"，这没什么好说的。"这个月新生的兔子"看起来要再分析一遍，但好在它只依赖"再上一个月的兔子数"，比 n 小，所以可以把这个子问题的答案直接拿来用。

把一个大问题拆成几个小问题，每个小问题的规模都比原问题小，然后把它们的答案合起来。这是递推的核心动作。后面第 2、3、4 章会反复看到这个动作，只不过小问题不再是"上月和再上月"，而是更细致的拆法。

如果递推式是这种"分最后一步"的产物，那它就是一个对"系统的下一步怎么从这一步长出来"的描述。这一点在后面看动态规划、看矩阵、看组合计数的时候会越来越清楚。

一个更干净的例子：楼梯

兔子问题有人物、有时间、有月份，记起来稍微要绕一下。我们换一个更干净的版本。

你站在一段 $n$ 阶楼梯下面。每次你可以走 1 阶或者 2 阶。问走到顶有多少种走法。

我们让 $W_n$ 表示走 $n$ 阶楼梯的方法数。

$n = 1$：只能一步走完，方法数 1。
$n = 2$：可以一步一步走，也可以一步直接跨 2 阶，方法数 2。
$n = 3$：可以 1+1+1、1+2、2+1，方法数 3。
$n = 4$：1+1+1+1、1+1+2、1+2+1、2+1+1、2+2，方法数 5。

得到 1, 2, 3, 5。和兔子数列错位了一下，但形状一样。

为什么会这样？

站在 $n$ 阶楼梯下面，你的第一步要么走 1 阶，要么走 2 阶。

如果第一步走 1 阶，那你之后还剩 $n-1$ 阶要走，剩下的走法数等于 $W_{n-1}$。

如果第一步走 2 阶，那你之后还剩 $n-2$ 阶要走，剩下的走法数等于 $W_{n-2}$。

所以 $W_n=W_{n-1}+W_{n-2}$。这就是斐波那契递推。和兔子问题一模一样。

楼梯的好处是没有兔子，没有月份，没有"上个月再生一对"这种需要画图的事。整个递推就在"第一步走几阶"这一刀里完成。

到这里，斐波那契递推已经在两个看起来不相干的故事里出现了。这件事本身是个暗示：它要说的不是兔子，也不是楼梯，而是"系统的下一步由前两步决定"这种结构本身。

把索引说清楚

斐波那契数列在不同书里的写法不一样。有的从 $F_1=1,F_2=1$ 开始，第 0 项不存在。有的从 $F_0=0,F_1=1$ 开始，把第 0 项写出来。

这本书统一用后者：$F_{0} = 0, F_{1} = 1$。也就是说，完整地写出来是 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …。

这样写的好处，到第 7 章矩阵和第 8 章闭式公式那里就会看出来，所有的公式都对得整整齐齐。代价是要记一下：兔子问题和楼梯问题给出的数列，刚好错位一格。

具体来说：

• 兔子问题里的"第 n 个月兔子对数"对应 $F_{n+1}$。第 $0$ 个月是 $1$ 对，等于 $F_1=1$；第 $1$ 个月是 $1$ 对，等于 $F_2=1$；第 $2$ 个月是 $2$ 对，等于 $F_3=2$，以此类推。
• 走 $n$ 阶楼梯的方法数 $W_n$ 对应 $F_{n+1}$。$W_1=1=F_2$，$W_2=2=F_3$，$W_3=3=F_4$，……

为什么这种错位一直出现？因为"事件从 1 开始数"和"数列从 0 开始数"在描述同一件事时，自然差一格。我们要做的把它说清楚，让小数字充当护栏。

后面所有的组合计数问题，铺砖、不连续子集、图上匹配，我们都会按同样的方式做：先把小数字列出来，再问"对应到 F 的哪一项"。错了就修，不挥手。

再换一个外壳：铺砖

离开兔子，离开楼梯，再看一个完全不同场景里同一个递推。

考虑一条长度为 $n$ 的 1 维走廊。你手上有 1 格砖和 2 格砖。问把走廊铺满有多少种铺法。记这个数为 $T_n$。

$n = 1$：只能用 1 块 1 格砖。$T_1=1$。
$n = 2$：可以两块 1 格砖，也可以一块 2 格砖。$T_2=2$。
$n = 3$：1+1+1、1+2、2+1。$T_3=3$。
$n = 4$：1+1+1+1、1+1+2、1+2+1、2+1+1、2+2。$T_4=5$。

1, 2, 3, 5。又是它。

最后一块砖要么是 1 格，要么是 2 格。如果最后一块是 1 格，前面剩下长度 $n-1$ 的走廊，铺法数等于 $T_{n-1}$。如果最后一块是 2 格，前面剩下长度 $n-2$ 的走廊，铺法数等于 $T_{n-2}$。所以 $T_n=T_{n-1}+T_{n-2}$。

铺砖、楼梯、兔子，三个完全不同的故事，推出来的递推式完全一样。它们都是"系统的下一步由前两步决定"这个结构的不同外衣。

你换衣服，结构不变。

第 10 章会把铺砖问题正式当成组合计数的入口，到时候我们还会再回来仔细数一数，看这个 5 是怎么从五块真实的砖头里数出来的。这里只是先让你看一眼：斐波那契数能被一块一块摆出来。

把它写成一个定义

现在我们有了递推 $F_n=F_{n-1}+F_{n-2}$ 和初值 $F_0=0,F_1=1$。这就构成了一个完整的定义。给定任意一个非负整数 n，按这个定义都能算出一个唯一的 $F_n$。

定义只说了"$F_n$ 等于前两项之和"。它没说"怎么算 $F_n$"。

这两件事看起来一样，其实差很远。定义是数学的事，它告诉你 $F_n$ 是什么。算法是计算的事，它告诉你怎么把这个值拿出来。

把定义直接翻译成算法，最朴素的版本就是：

function F(n):
    if n == 0: return 0
    if n == 1: return 1
    return F(n-1) + F(n-2)

这段程序读起来和数学定义几乎一模一样。它会正确给出 $F_n$。但下一章我们会看到，它也是你写过最慢的程序之一。

斐波那契给我们的第一课来自这里：数学定义和高效算法之间有一道沟。优雅的定义不保证优雅的计算。

这个教训听起来好像只关于斐波那契。其实它出现在很多地方。一个图的最短路可以用递归定义写得很短，但直接跑会爆炸。一个组合数 $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ 看上去人畜无害，直接展开会算到天荒地老。一个概率分布的边缘分布可以用全概率公式写一行，真去算要遍历整个样本空间。

这些场景看起来各不相同，背后都是同一件事：定义回答"是什么"，算法回答"怎么算"，二者之间常常差一个聪明的中间步骤。

斐波那契的好处是它小到可以看清这个差距是怎么出现的，又大到可以让我们看清楚怎么把差距填上。

这章我们看到了什么

兔子问题、楼梯问题、铺砖问题，三个看起来毫无关系的故事，最后都给了我们同一个递推 $F_n=F_{n-1}+F_{n-2}$。这件事本身就在告诉我们：递推从"把系统的下一步分成几种情况"这一动作里自然长出来。

我们把索引说清楚了：本书统一用 $F_0=0,F_1=1$，组合计数问题对应的下标会差一格，错位时用小数字修。

最后我们把递推直接翻译成了一段最朴素的递归程序，并且发现：定义看起来够清楚了，可是它并没有告诉我们"怎么算才不慢"。

第一扇门开了。后面那扇门后面是一段慢得离谱的程序，慢到你会怀疑电脑是不是坏了。

我们去把它拆开看看。

第 2 章 把它翻译成程序：朴素递归

上一章末尾那段递归程序，我们这一章真的拿去跑一下。

function F(n):
    if n == 0: return 0
    if n == 1: return 1
    return F(n-1) + F(n-2)

读起来和数学定义 $F_n=F_{n-1}+F_{n-2}$ 几乎一一对应。你看不出它有什么问题。它也没有 bug。它给出的答案永远是对的。

但是你跑 $F_{10}$，瞬间。$F_{20}$，瞬间。$F_{30}$，等 0.1 秒。$F_{40}$，等几秒。$F_{45}$，等一分钟。$F_{50}$，你可以去泡杯茶。$F_{100}$，你这台机器大概这辈子算不完。

明明每一步都只是加法，慢在哪里。

先跑几个小例子

跑 $F_5$ 看看。表面上是 5 次递归调用。结果是 5。一次加法出来。看上去没什么。

跑 $F_{10}=55$。从 10 个递归调用一直到几十次调用，结果是 55，瞬间给出。

跑 $F_{20}=6765$。还是瞬间，但仔细看，调用次数已经不是 20 次了，是 21891 次。

跑 $F_{30}=832040$。0.1 秒左右。调用次数约 270 万。

跑 $F_{40} = 102334155$。几秒。总调用数 $T_{40}=2F_{41}-1=331160281$，约 3.3 亿次。

跑 $F_{50} = 12586269025$。几分钟到十几分钟。总调用数 $T_{50}=2F_{51}-1=40730022147$，约 407 亿次。

数字看上去已经不对劲了。$F_{40}$ 这台机器几秒就给出 1 亿这个量级的数，但调用次数居然达到 3 亿。也就是说，每次调用平均只产生不到一位数的有效计算。这种"调用次数远超结果位数"的现象，是出问题的征兆。

我们这一章不展开分析。先记下这个现象：朴素递归的调用次数随 n 增长极快，比 $F_n$ 本身增长还快一档。

下一章我们把调用过程画出来，看清楚这些多出来的调用在做什么。

看一眼小例子的展开

虽然这一章不展开调用树，但跑 $F_5$ 还是要看一眼的，否则现象就太抽象了。

$F_5$ 要算 $F_4$ + $F_3$。
$F_4$ 要算 $F_3$ + $F_2$。
$F_3$ 要算 $F_2$ + $F_1$。
$F_2$ 要算 $F_1$ + $F_0$。

最底层 $F_0$ 和 $F_1$ 直接返回 0 和 1，递归开始往回走。但是注意上面那一行：$F_3$ 在 $F_5$ 的展开里出现了两次，一次是 $F_4$ 的右边，一次是 $F_5$ 自己的右边。$F_2$ 出现了三次。

跑 $F_5$ 总共产生 15 次调用。但是真正"新"的计算只有 $F_0$, $F_1$, $F_2$, $F_3$, $F_4$, $F_5$ 这 6 项。剩下 9 次调用，都是把已经算过的东西再算一遍。

这才 n = 5。换成 n = 10，整个调用过程里 $F_2$ 被调用 34 次，$F_1$ 被调用 55 次，$F_0$ 被调用 34 次。每一项都被反复重算。

到 n = 30，$F_2$ 被算了大约 832040 次。一项被算 80 多万次，这就是为什么 0.1 秒才出结果。

到 n = 50，$F_2$ 被调用 $F_{49} = 7778742049$ 次，约 78 亿次。

到这一步可以下一个粗略判断：朴素递归慢，是因为它在反复算同一件事。

慢的根源是结构性的

慢的根源不在加法本身。加法在所有现代 CPU 上都是纳秒级的。即使 $F_{50}$ 真的要做 407 亿次加法，按每秒 10 亿次算，也就 40 秒。可朴素递归跑 $F_{50}$ 要十几分钟，差了一个数量级。所以慢的根源不只是"加法次数多"。

慢的真正根源是：朴素递归算了就忘。每次遇到 $F_{k}$，它都从头开始把 $F_{k}$ 重新算一遍，完全不管刚才是不是已经算过。

这种"算了就忘"是结构性的，不是某个具体实现的偶然缺陷。递归程序按定义展开，定义本身没说"已经算过的就别再算"，所以程序也不会这么干。这是数学定义和高效算法之间那道沟的具体形状：定义回答"是什么"，算法听成"每次需要就从头算一遍"。

斐波那契给我们的第二课来自这里：优雅的定义翻译成朴素递归，会变成计算灾难。

这不是递归的错。递归只是一种写法，本身不慢。慢的是这种特定递归，它不保存子问题答案。换成另一种递归（带记忆的递归），同一道题可以快几个数量级。

"翻译"这件事

我们再多想一步。把数学定义翻译成程序，听起来像是一个机械的过程：定义里有什么，程序就写什么。递推式 $F_n=F_{n-1}+F_{n-2}$ 被直接翻译成 fib(n)=fib(n-1)+fib(n-2)，看起来一一对应。

但是这种"一一对应"忽略了几个东西。

第一，定义没说"什么时候算"。数学里 $F_n$ 是一个抽象的值，它"就是"那个数。程序里 $F_n$ 是一个动作，它在某个时刻被执行，产生一个结果。这两个 $F_n$ 看起来一样，性质完全不同。

第二，定义没说"算过的要不要记"。数学里 $F_3$ 永远等于 2，无论你查多少次。程序里 $F_3$ 是一个调用，每次调用都重新算，结果当然是 2，但算的过程花时间。

第三，定义没说"按什么顺序算"。数学里 $F_5$ = $F_4$ + $F_3$ 是一个等式，左右两边同时成立。程序里要先算 $F_4$ 再算 $F_3$，或者反过来，顺序由实现决定。不同的顺序可能影响效率。

这三个"没说"加起来，意味着从定义到程序之间有相当大的自由度。朴素递归只是其中一种翻译方式，它选择了"按定义顺序算、算完就丢、不记忆"。这种选择看起来最自然，恰恰因为它最自然，所以也最容易踩坑。

其他翻译方式包括：自顶向下带记忆的递归（先按定义展开，但算过的存下来），自底向上迭代（从 $F_0$、$F_1$ 开始往大算，不用递归），分治加速（发现递推里藏着跳步结构，对数时间搞定）。这些方式都对应同一个数学定义，但性能差好几个数量级。

第 3 章我们会展开调用树，把"算了就忘"这件事画清楚。第 4 章给程序装上记忆。第 5、6 章让程序跳步。每一步都是在重新填"定义"和"算法"之间的那道沟。

一个直觉：朴素递归比 $F_n$ 本身慢一档

虽然这一章不展开复杂度推导，但有一个直觉值得现在就建立。

朴素递归的调用次数 $T_n$ 满足 $T_n\approx2F_{n+1}$。也就是说，调用次数和斐波那契数本身同阶，但稍微大一点，差一个 2 倍和一个位移。

这个事实有几个直接的后果：

• $F_n$ 增长得很快（指数级，约 $\varphi^n/\sqrt5$）。
• $T_n$ 也增长得很快（也是指数级，约 $2\varphi^{n+1}/\sqrt5$）。
• $n$ 增加 1，调用次数大约乘以 1.618（黄金比例）。
• $n$ 增加 10，调用次数大约乘以 122 倍。
• $n$ 增加 50，调用次数大约乘以 $10^{10}$ 倍。

这就解释了为什么 $F_{40}$ 几秒，$F_{50}$ 几分钟，$F_{60}$ 大概要好几小时。每多 10 项，时间乘以 122。

下一章我们会把这个直觉推导清楚：为什么 $T_n\approx2F_{n+1}$？为什么朴素递归的复杂度恰好是斐波那契数本身？这个"递归算斐波那契的代价是另一个斐波那契数"的事实，是这本书最讽刺的瞬间之一。

这章我们看到了什么

朴素递归跑小例子没事，跑大例子就慢得离谱。慢的根源不在加法本身，而在"算了就忘"：每次遇到 $F_{k}$ 都从头算，不管之前算没算过。

我们把"翻译"这件事看了一眼：从数学定义到程序之间有好几个"没说"，朴素递归只是其中一种最自然的翻译，恰恰因为它最自然，所以最容易踩坑。

最后留下一个直觉：朴素递归的调用次数和斐波那契数本身同阶，$T_n\approx2F_{n+1}$。这意味着 $n$ 每增加 1，时间乘以 1.618。下一章我们会把这个直觉推导清楚，看清楚那棵调用树到底长什么样。

第 3 章 调用树与"为什么这么慢"

第 2 章那段程序，我们说要回过头看它怎么慢的。这一章把它的调用过程画出来，让慢这件事有具体的形状。

把 $F_5$ 的调用展开

跑 $F_5$ 的时候，调用过程是这样的：

$F_5$ 要 $F_4$ + $F_3$。
$F_4$ 要 $F_3$ + $F_2$。
$F_3$ 要 $F_2$ + $F_1$。
$F_2$ 要 $F_1$ + $F_0$。
$F_1$ 和 $F_0$ 直接返回。

把它画成一棵树：

                       F(5)
                     /      \
                  F(4)        F(3)
                 /    \      /    \
              F(3)   F(2)  F(2)  F(1)
             /    \   / \   / \
          F(2) F(1) F(1)F(0)F(1)F(0)
          /  \
       F(1) F(0)

数一下每个节点被算了多少次。

$F_1$ 出现 5 次。
$F_0$ 出现 3 次。
$F_2$ 出现 3 次。
$F_3$ 出现 2 次。

整个树总共 15 个节点。但是真正"新"的计算只有 $F_0$, $F_1$, $F_2$, $F_3$, $F_4$, $F_5$ 这 6 项。剩下 9 次调用，都是把已经算过的东西再算一遍。

这才 n = 5。换成 n = 10 试试。$F_9$ 是一棵独立的斐波那契调用树，$F_8$ 也是一棵独立的斐波那契调用树。它们之间共享的部分，$F_8$, $F_7$, $F_6$, …，全部被算了两次。

到 n = 30，整棵树大概有 270 万个节点。到 n = 40，约 3.3 亿个。到 n = 50，约 407 亿个。这就是为什么 $F_{50}$ 跑不动。要做的加法次数太多。

把"太多"算出来

设 $T_n$ 是计算 $F_n$ 所需的递归调用次数。从程序结构看：

这里的 $+1$ 是因为 $F_n$ 自己也算一次调用。

把 $T_n+1$ 记作 $U_n$，那么

又有 $U_0=2,U_1=2$。所以 $U_n$ 满足的就是斐波那契递推，只是初值是 $2,2$ 而不是 $0,1$。这意味着

也就是说

朴素递归计算 $F_n$ 的调用次数，差不多是 2 $F_{n+1}$。

这是一个很讽刺的结果。你写程序去算 $F_n$，结果程序做的工作量正比于 $F_{n+1}$。你想算的数，恰好就是你要付出的代价。斐波那契数列增长得很快，所以你的程序也慢得很快。

具体一点：

• $F_{10} = 55$，$T_{10}=2F_{11}-1=2\cdot89-1=177$ 次调用。瞬间。
• $F_{20} = 6765$，$T_{20}=2F_{21}-1=2\cdot10946-1=21891$ 次调用。瞬间。
• $F_{30} = 832040$，$T_{30}=2F_{31}-1=2\cdot1346269-1=2692537$，约 270 万次。0.1 秒左右。
• $F_{40} = 102334155$，$T_{40}=2F_{41}-1=331160281$，约 3.3 亿次。几秒。
• $F_{50} = 12586269025$，$T_{50}=2F_{51}-1=40730022147$，约 407 亿次。一个半小时起步。
• $F_{100} \approx 3.5 \times 10^{20}$，$T_{100}\approx10^{21}$ 次调用。即使每次调用 1 纳秒，也要 3 万年。

同一个子问题被算了无数次。$F_2$ 在算 $F_{50}$ 时被算了大约 $F_{49}$ ≈ 78 亿次。$F_3$ 被算了大约 $F_{48}$ ≈ 48 亿次。一棵看似简单的二叉树，因为子问题之间完全重叠，节点数指数级膨胀。

调用树的两条对角线

如果你想再看得精确一点，调用树上有两条线特别有讲究。

第一条线：最左路径。从根 $F_n$ 一路向左走 $F_{n-1}$, $F_{n-2}$, …, $F_1$, $F_0$。这条线有 n + 1 个节点，对应"从顶向下递归到最底层"的过程。任何递归实现都必须走完这条线，因为你至少要碰到 $F_0$ 和 $F_1$ 才能开始返回。

第二条线：最右路径。从根 $F_n$ 一路向右走 $F_{n-2}$, $F_{n-4}$, $F_{n-6}$, …。这条线长度大约 n/2，也是任何递归实现都要走的。

整个调用树的节点数，主要由"在最左路径基础上往右伸展出去的子树"决定。根的右子树是 $F_{n-2}$，它本身又是一棵完整的斐波那契调用树。这棵子树的根的右子树是 $F_{n-4}$，又是一棵完整的斐波那契调用树。以此类推。

把这些右子树加起来，你会发现总节点数恰好满足斐波那契递推。所以 $T_n$ ≈ 2 $F_{n+1}$ 这件事，从结构上看就是：调用树是一棵"每一层都长出和上一层差不多大子树"的二叉树，子树之间的内容大量重叠，但程序并不识别这种重叠。

调用树的形状本身就是斐波那契

到这里可以下一个稍微深一点的判断。

朴素递归的调用树，结构上和斐波那契数列同构。每个节点 $F_{k}$ 的子树大小，等于 $T_k\approx2F_{k+1}$。每个节点的左子树大小约等于 2 $F_{k}$，右子树大小约等于 2 $F_{k-1}$。两棵子树加起来差不多等于父节点的子树大小。

这件事的几何效果是：朴素递归的调用树长得像一棵"斐波那契分形"。每个子树都是父树的缩小版，缩小比例大约是 1/$\varphi$ 和 1/$\varphi^{2}$。整棵树的节点数指数级膨胀，膨胀速度就是斐波那契数列本身的增长速度。

这是这本书里最讽刺的一个瞬间。你写程序去算斐波那契数，结果程序构造的调用树本身就是斐波那契形状的。你想算的那个数，恰恰就是你程序的代价。

问题不在递归，问题在没记性

到这里你可能会想：递归是不是不能用？

递归只是一种写法，本身不慢。慢的是这段程序"算了就忘"。

你看，$F_5$ 在算 $F_4$ 的时候已经把 $F_3$ 算了一遍。等它回到顶层去算 $F_3$ 的时候，它根本不知道自己刚才算过这玩意儿，从头再来一次。

把同一份工作做了两遍，又两遍，又两遍。整个调用树的膨胀不因为这个程序写得多复杂，而是因为最简单的子问题，$F_2$, $F_3$, $F_4$，被反复重算。

打个比方。你去超市买东西，列了一张单子：牛奶、面包、鸡蛋、苹果、香蕉。买完回家发现忘了牛奶。再去一次。又买完回家发现还忘了面包。再去一次。如果每次只解决一个遗忘项，你跑超市的次数等于商品数。

朴素递归就是这样。它每遇到一次 $F_2$ 就重新算一遍，每次都从最底下 $F_0$ 和 $F_1$ 一路加起来。它没有一张"已经算过"的备忘录，所以每次都从头来。

让程序长出一张备忘录，是下一章要做的事。这一章我们先把"为什么这么慢"这件事彻底看清楚。

一个更直观的失败

把斐波那契递归展开成调用树，能看出它哪里慢。但这件事其实可以用一个更直观的方式感受。

你跑 $F_{50}$ 在你的笔记本上要等几分钟。你的笔记本每秒能做几十亿次基本运算。也就是说，在这几分钟里，你的电脑做了 $10^{11}$ 次以上的加法。而 $F_{50}$ 这个数本身，按定义只需要 50 次加法就能算出来。

50 步加法，几纳秒就完事。可是朴素递归花了几分钟，做了 $10^{11}$ 次运算。中间差的 $10^{10}$ 倍，全是浪费。

这就是定义和算法之间那道沟的具体形状。定义说"$F_n$ 等于 $F_{n-1}$ + $F_{n-2}$"，算法听成"每次需要 $F_n$，就把 $F_{n-1}$ 和 $F_{n-2}$ 都从头算一遍"。这中间没有任何"已经算过就别再算"的意识。

朴素递归把数学定义的优雅翻译成了计算灾难。这是递归的特定写法的错，不是递归本身的错。

这本书第一次出现的反常识

到这里我们可以把这一章的核心说出来。

我们通常觉得，一段程序越简洁、越接近数学定义，它就越优雅，越值得写。这一章里，斐波那契递归就是这种优雅的化身：6 行代码，结构清楚，读起来像诗。

但是优雅的定义不保证优雅的计算。这段最像数学定义的程序，跑起来却极慢。

这件事在算法课里被叫做"定义 $\neq$ 算法"。听起来朴素，但是真碰到的时候很容易栽。斐波那契递归是栽这个跟头最好的地方，因为它小到能让你看清跟头是怎么栽的，又大到能让你感觉到疼。

后面第 4 章会讲怎么修，给程序加上一张备忘录，让它从指数级变线性。第 5 章会讲怎么修得更狠，把步子折半，做到对数级。第 6 章会把整个递推改写成矩阵快速幂。每一步都是在重新填"定义"和"算法"之间的那道沟。

但是这一章我们停下来看一下：原来这道沟，是真的存在的。即使是这么简单的一段递归，也会有。

一个值得记住的画面

最后留一个画面。

那棵调用树。每个节点上写着一个 $F_{k}$。整棵树有 2 $F_{n+1}$ − 1 个节点，但你真正需要的"新计算"只有 n + 1 个：$F_0$, $F_1$, $F_2$, …, $F_n$。

剩下所有的节点，都是把已经算过的东西重算一遍。

那些重算的节点，是浪费。它们也是机会。只要把每个 $F_{k}$ 算过一次之后存下来，下次再遇到就直接查表，所有的重算节点会瞬间消失。一棵 2 $F_{n+1}$ 节点的树，会塌缩成 n + 1 个节点的链。

下一章我们就让这棵树塌缩。

第 4 章 给程序装上记忆：动态规划的内核

第 3 章那棵膨胀的调用树，我们说它"算了就忘"。这一章给程序装上一张备忘录，让算过的东西别再算第二遍。整个改动很小，但效果是数量级的。

第一步：把算过的存下来

最直接的修改，是给 $F_{k}$ 配一张表。每次算 $F_{k}$ 之前先查表，如果表里已经有，直接拿来用。如果还没有，算一遍，把结果写进表里，再返回。

代码大概长这样：

memo = {0: 0, 1: 1}

function F(n):
    if n in memo:
        return memo[n]
    result = F(n-1) + F(n-2)
    memo[n] = result
    return result

加了两行代码，效果完全不一样。

跑 $F_{50}$：原来要算约 407 亿次，现在算 51 次（$F_0$ 到 $F_{50}$ 各一次）。跑 $F_{100}$：原来要算 $10^{21}$ 次，现在 101 次。

为什么差距这么大？因为每个 $F_{k}$ 在整张调用树里只第一次被算。之后所有遇到 $F_{k}$ 的地方，都查表返回，不再往下展开。

回到第 3 章那棵 $F_5$ 的调用树：

                       F(5)
                     /      \
                  F(4)        F(3)
                 /    \      /    \
              F(3)   F(2)  F(2)  F(1)
             /    \   / \   / \
          F(2) F(1) F(1)F(0)F(1)F(0)
          /  \
       F(1) F(0)

加了备忘录之后，调用过程变成：

1. $F_5$ 没在表里，要算 $F_4$ + $F_3$。
2. $F_4$ 没在表里，要算 $F_3$ + $F_2$。
3. $F_3$ 没在表里，要算 $F_2$ + $F_1$。
4. $F_2$ 没在表里，要算 $F_1$ + $F_0$。两个都在表里，返回 1 + 0 = 1。写入 memo[2] = 1。
5. $F_1$ 在表里，返回 1。
6. $F_3$ 算完：$1 + 1 = 2$。写入 memo[3] = 2。
7. $F_2$ 在表里，返回 1。
8. $F_4$ 算完：$2 + 1 = 3$。写入 memo[4] = 3。
9. $F_3$ 在表里，返回 2。
10. $F_5$ 算完：$3 + 2 = 5$。写入 memo[5] = 5。

10 步。原来 15 步。看上去差距不大。但放大到 n = 50，原来是 407 亿步，现在是 51 步。

那棵原来指数膨胀的树，被一张备忘录压扁成一条链。

这种写法有个名字：记忆化

把"算过的就存下来"这个动作加到递归上，叫做记忆化（memoization）。这个英文字生造于 1968 年，是 Donald Michie 提出来的，意思是"把函数已经算过的结果记下来，下次再问就直接给答案"。

记忆化是一个很通用的技巧，不限于斐波那契。任何递归函数，只要满足两条性质，都可以记忆化加速：

函数对同一个输入永远给出同一个输出（没有副作用、没有外部状态）。
在递归展开的过程中，同一个输入会被反复问到。

斐波那契递归满足这两条。所以记忆化一上去，2 $F_{n+1}$ 次调用塌缩成 n + 1 次。

记忆化的好处是改动小。原本那段优雅的递归代码不动，只在外面包一层"先查表"的逻辑，整体结构没变。

代价是要花内存。memo 表里要存 n + 1 个数。对斐波那契来说，n 通常不会太大，几十兆就够算到 $F_{10^6}$，所以这点内存完全可以接受。

第二步：换个方向，自底向上

记忆化是"自顶向下"的：从 $F_n$ 出发，递归到 $F_0$ 和 $F_1$，然后一层层算回来。

可以反过来，"自底向上"：从 $F_0$ 和 $F_1$ 出发，一步步往上算到 $F_n$。

function F(n):
    if n == 0: return 0
    if n == 1: return 1
    a, b = 0, 1
    for i = 2 to n:
        a, b = b, a + b
    return b

跑一下 n = 5 看看。

初始：$a = 0, b = 1$（这就是 $F_0$ 和 $F_1$）。
$i = 2$：$a, b = 1, 0+1 = 1$（这就是 $F_1$, $F_2$）。
$i = 3$：$a, b = 1, 1+1 = 2$（这就是 $F_2$, $F_3$）。
$i = 4$：$a, b = 2, 1+2 = 3$（这就是 $F_3$, $F_4$）。
$i = 5$：$a, b = 3, 2+3 = 5$（这就是 $F_4$, $F_5$）。
返回 b = 5。

5 次循环，5 次加法，得到 $F_5$。换成 n = 50，50 次循环。换成 n = 1000，1000 次循环。

时间和记忆化一样是 $O(n)$，但是空间省了：自底向上版本只用两个变量 a 和 b，$O(1)$ 空间。记忆化要用 $O(n)$ 空间存整张表。

为什么自底向上能省空间？因为它不需要"回头"。$F_{k}$ 一旦用来算 $F_{k+1}$ 之后就再也不需要了。除了 $F_{k+1}$ 计算时用到的两个值 $F_{k}$ 和 $F_{k-1}$，其他都不用记。所以只需要两个变量来回倒腾就行。

自顶向下的记忆化不一样，它要把整张表留在那里，因为递归回去的时候可能还要查。其实严格来说，记忆化版本如果改成"只保留最近两项"也是可以的，但写起来没有自底向上那么自然。

这两个写法，本质上做的是同一件事

记忆化和自底向上迭代，从代码看是完全不同的两套写法。一个递归，一个循环。一个用字典，一个用两个变量。

但是从"算了几次加法"这个角度看，它们完全一样：都是 n − 1 次加法，每个 $F_{k}$ 算一次，从 k = 2 算到 k = n。

它们都在做同一件事：让每个子问题只被解决一次，然后被复用。

这件事有一个统一的名字：动态规划。

动态规划到底是什么

动态规划这个名字，是 1950 年代 Richard Bellman 起的。这个名字起得不太好，"dynamic" 和 "programming" 都和它实际做的事没什么直接关系。Bellman 自己在回忆录里说，起这个名字主要是为了让资助方听上去觉得时髦，本质上是公关考虑。

抛开名字不谈，动态规划的核心其实就一句话：

如果一个问题可以拆成若干个重叠的子问题，那么把每个子问题的答案记下来，下次再用就直接拿，别再算第二遍。

就这么一句。

这句话里有两个关键词。"重叠"和"记下来"。

"重叠"指的是不同子问题之间会有公共部分。斐波那契递归里 $F_{50}$ 需要 $F_{49}$ 和 $F_{48}$，$F_{49}$ 又需要 $F_{48}$ 和 $F_{47}$，$F_{48}$ 是两个父问题的公共子问题。重叠是动态规划起作用的前提。如果子问题完全不重叠（比如归并排序里的两个一半），那每个子问题只被解决一次，根本不需要记忆化，分治就够了。

"记下来"指的是用一张表（或者两个变量、一个数组、一个字典）保存子问题的答案。这是动态规划和朴素递归的区别。朴素递归也算子问题，但算完就丢，所以同一个子问题被反复解决。动态规划算完不丢，所以每个子问题只算一次。

斐波那契是动态规划最简单的样本。它只有一个一维的状态（k 从 0 到 n），状态转移也很简单（$F_{k} = F_{k-1} + F_{k-2}$）。但它已经把动态规划的两条核心都展示出来了：有重叠子问题，且通过记忆化或自底向上迭代把每个子问题算一次。

动态规划不是背模板

很多人学动态规划的方式，是背一堆模板：背包问题、最长公共子序列、最长上升子序列、编辑距离、矩阵链乘法。每个模板一个转移方程、一组边界条件，套上去就能做。

这种学法的问题在于：它把动态规划当成一堆孤立的技巧，掩盖了它真正的内核。

动态规划的内核其实很简单：识别子问题，发现它们重叠，决定先算哪个，然后算一次就够了。

模板只是这个内核在不同问题上的具体应用。背模板而不懂内核，会做的是模板题。懂了内核，模板只是顺手的事。

我们用斐波那契把内核拆开来看：

1. 识别子问题。原问题是"算 $F_n$"。子问题是"算 $F_{k}$，其中 0 $\leq$ k $\leq$ n"。
2. 发现重叠。$F_n$ 依赖 $F_{n-1}$ 和 $F_{n-2}$，$F_{n-1}$ 又依赖 $F_{n-2}$ 和 $F_{n-3}$，所以 $F_{n-2}$ 被两个父问题需要。重叠出现了。
3. 决定顺序。从 k = 0 开始往大算，到 k = n 结束。每个 $F_{k}$ 只在 $F_{k-1}$ 和 $F_{k-2}$ 都已知时才被算。
4. 算一次。每个 $F_{k}$ 在被算出来之后存起来（或丢弃，如果不再需要），下次再用就直接拿。

这四步就是动态规划的全部。模板题里那些复杂的状态定义、奇怪的转移方程，都是这四步在具体问题上的细化。

把动态规划的第一层意思说清楚

到这里可以做一个清楚的判断：

动态规划的核心是一种关于"计算有记忆"的意识。

朴素递归的意识是：每次需要什么就算什么，算完丢掉。
动态规划的意识是：已经算过的东西，不该再付一次代价。

这两种意识之间，差的不只是一张表。差的是对"什么是计算"的根本理解。

朴素递归把计算理解成"按定义展开"。这种理解在数学上是对的，但在工程上不对。展开会出现大量重复，重复会爆炸。

动态规划把计算理解成"按依赖图遍历"。每个子问题是一个节点，依赖关系是边，按拓扑序遍历这张图，每个节点只访问一次。

这两种理解给出的算法，时间复杂度可以差指数级。斐波那契是最干净的例子：朴素递归 $\Theta(\varphi^n)$，动态规划 $\Theta(n)$。

动态规划的代价

动态规划不是免费的。它用时间换时间，用空间换时间。

空间上，自顶向下要 $O(n)$ 的备忘录，自底向上虽然能压到 $O(1)$，但本质上还是"在某个时刻需要保存某些状态"。在更复杂的问题里，状态空间可能很大。背包问题 $O(nW)$，矩阵链乘法 $O(n^2)$，编辑距离 $O(mn)$。空间常常成为瓶颈。

时间上，虽然每个子问题只算一次，但是子问题的总数本身可能很多。某些问题（比如旅行商）子问题数是指数级的，动态规划只能把"指数的指数"降到"指数"，依然不可解。

所以动态规划只在子问题数量可控、且子问题之间确实重叠的时候有用。

对斐波那契来说，子问题数量是 $O(n)$，重叠是显然的，所以动态规划是最合适的工具。从 $\Theta(\varphi^n)$ 降到 $\Theta(n)$，这一步已经把朴素递归慢成灾难的问题解决了。

还能更快吗

$O(n)$ 听起来已经很快了。$F_{10^6}$ 用自底向上迭代跑，几毫秒就完事。$F_{10^9}$ 跑不动了。这不能怪算法，是数本身太大，存不下来。

但是从算法角度，$O(n)$ 还能更快。下一章会讲怎么把步子折半，做到 $O(\log n)$。

那里的关键，是发现斐波那契递推里藏着一种"翻倍"的结构。$F_{n+m}$ 可以从 $F_n$, $F_{m}$ 和它们附近的几个值直接算出来，不需要从 $F_0$ 一路加到 $F_{n+m}$。这等于说，从 $F_{k}$ 跳到 $F_{2k}$ 不需要 k 步加法，只需要常数次乘法和加法。

但是先停下来想一想：从 $O(\varphi^n)$ 到 $O(n)$ 这一步，已经够我们记一辈子了。它告诉我们一件事：

优雅的定义不保证优雅的计算。给计算加上一张备忘录，常常就能把优雅找回来。

斐波那契数列给我们的第三课就是这个：计算是有记忆的，算过的东西不该再付一次代价。

这件事听起来朴素，但它就是动态规划的全部。

下一章我们问：除了"算过的就别再算"，还能不能再省一些？答案藏在递推自身的结构里。

第 5 章 快速倍增：从加法到乘法

到上一章为止，我们最好的算法是 $O(n)$。要算 $F_n$，从 $F_0$ 走到 $F_n$，每一步一次加法，n 步搞定。

这一章问的是：能不能不一步一步走？能不能跳？

答案是可以。斐波那契递推里藏着一种"翻倍"的结构。从 $F_{k}$ 跳到 $F_{2k}$，不需要 k 步加法，只需要常数次乘法和加法。这一步把 $O(n)$ 砍成 $O(\log n)$。

先想清楚"翻倍"是什么意思

假设我们已经知道 $F_{k}$ 和 $F_{k+1}$。能不能从这两个数直接算出 $F_{2k}$ 和 $F_{2k+1}$，而不需要从 $F_{k+2}$ 一路加到 $F_{2k}$？

如果能，那从 $F_0$, $F_1$ 出发，反复翻倍，就能跳着算到任意 $F_n$。

知道 $F_0$, $F_1$，翻一次倍，得到 $F_0$, $F_1$, $F_2$, $F_3$ 里的 $F_2$ 和 $F_3$。
再翻一次倍，从 $F_2$, $F_3$ 得到 $F_4$, $F_5$。
再翻一次倍，从 $F_4$, $F_5$ 得到 $F_8$, $F_9$。
再翻一次倍，从 $F_8$, $F_9$ 得到 $F_{16}$, $F_{17}$。

每一次翻倍，下标翻一倍。所以从 $F_0$, $F_1$ 走到 $F_n$，只需要 $\log_2 n$ 次翻倍。

这个思路要工作，关键是有一个公式把 $F_{2k}$ 和 $F_{2k+1}$ 用 $F_{k}$ 和 $F_{k+1}$ 直接写出来。我们下面就把它推出来。

推加法公式

要推翻倍公式，先要推一个更基础的公式：加法公式。它说 $F_{n+m}$ 可以用 $F_n$ 和 $F_{m}$ 附近的几个值表示出来。

我们先猜 $F_{n+m}$ 是 $F_n$ 和 $F_{m}$ 的某种线性组合。也就是说，$F_{n+m} = a F_{n+1} + b F_{n} + c F_{m+1} + d F_{m}$ 这种形式，其中 $a,b,c,d$ 是常数。

但是这种猜法太宽。我们直接做。

考虑 $F_{n+m}$。固定 $m$，把 $n$ 从 $0$ 开始一个个推：

$F_{m} = F_{m}$。这是 $n=0$。
$F_{m+1} = F_{m+1}$。这是 $n=1$。
$F_{m+2} = F_{m+1} + F_{m}$。这是 $n=2$。
$F_{m+3} = F_{m+2} + F_{m+1} = 2 F_{m+1} + F_{m}$。
$F_{m+4} = F_{m+3} + F_{m+2} = 3 F_{m+1} + 2 F_{m}$。
$F_{m+5} = F_{m+4} + F_{m+3} = 5 F_{m+1} + 3 F_{m}$。

看出来了吗？当 $n\ge1$ 时，

这里先把边界说清楚：这个写法默认 $n\ge1$，避免引入 $F_{-1}$。如果 $n=0$，公式左边就是 $F_m$，直接单独验证即可。

验证一下。$n = 5, m = 2$：$F_{7} = F_{5} F_{3} + F_{4} F_{2} = 5 \cdot 2 + 3 \cdot 1 = 13$。对，$F_{7} = 13$。
$n = 4, m = 3$：$F_{7} = F_{4} F_{4} + F_{3} F_{3} = 3 \cdot 3 + 2 \cdot 2 = 13$。也对。

把下标对称地换一种写法，常用的加法公式是：

这一式默认 $n\ge0,m\ge1$。如果想让 $m=0$ 也包括进来，就需要额外约定负指标，或者把 $m=0$ 作为边界情形单独验证。这个公式可以数学归纳法证明（对 $n$ 归纳）。第 14 章会给出它的组合证明。重要的是它给了我们一个工具：$F_{n+m}$ 可以从 $F_n$, $F_{n+1}$, $F_{m}$, $F_{m-1}$ 这四个值直接算出来，不需要从 $F_0$ 一路加到 $F_{n+m}$。

推翻倍公式

现在令 $n=m=k$，加法公式给出：

$F_{2k} = F_{k+1} F_{k} + F_{k} F_{k-1} = F_{k} [F_{k+1} + F_{k-1}]$

但是

最后一个等号用了

它可以从 $F_{k+1}=F_k+F_{k-1}$ 推出。

所以：

$F_{2k}=F_k\cdot(2F_{k+1}-F_k)$

这就是 $F_{2k}$ 的翻倍公式。

类似地，令 $n=k+1,m=k$：

用

得到

所以：

把两个公式写在一起：

$$F_{2k+1}=F_k^2+F_{k+1}^2.$$

这两个公式合起来叫"快速倍增公式"。

验证一下

拿 $k=3$ 试一下。$F_3=2,F_4=3$。

按公式：

$F_6=F_3\cdot(2F_4-F_3)=2\cdot(6-2)=8$
$F_7=F_3^2+F_4^2=4+9=13$

实际值：$F_{6} = 8, F_{7} = 13$。对。

再拿 $k=5$ 试一下。$F_5=5,F_6=8$。

$F_{10}=F_5\cdot(2F_6-F_5)=5\cdot(16-5)=55$
$F_{11}=F_5^2+F_6^2=25+64=89$

实际值：$F_{10} = 55, F_{11} = 89$。对。

公式稳。

把它写成算法

用这两个公式，可以从 $(F_0,F_1)=(0,1)$ 出发，按 $n$ 的二进制位一步步跳到 $(F_n,F_{n+1})$。

具体怎么跳？我们让「当前知道的」始终是一对 $(F_k,F_{k+1})$。从 $(F_0,F_1)$ 开始，每一步可以选择：

1. 翻倍：把 $(F_k,F_{k+1})$ 变成 $(F_{2k},F_{2k+1})$。用上面两个公式。
2. 加一：把 $(F_k,F_{k+1})$ 变成 $(F_{k+1},F_{k+2})$。其中 $F_{k+2}=F_k+F_{k+1}$。

要从 $k=0$ 跳到任意 $n$，按 $n$ 的二进制位从高到低走：每一步先翻倍，如果当前二进制位是 1 就再翻加一。这和快速幂的思路完全一样。

举个例子，$n=13=1101_2$。从 $(F_0,F_1)=(0,1)$ 出发：

最高位 $1$：先翻倍（到 $k=0\times 2=0$），再加一（到 $k=1$）。得到 $(F_1,F_2)=(1,1)$。
下一位 $1$：先翻倍（到 $k=2$），再加一（到 $k=3$）。得到 $(F_3,F_4)=(2,3)$。
下一位 $0$：先翻倍（到 $k=6$），不加一。得到 $(F_6,F_7)=(8,13)$。
下一位 $1$：先翻倍（到 $k=12$），再加一（到 $k=13$）。得到 $(F_{13},F_{14})=(233,377)$。

四步，从 ($F_0$, $F_1$) 跳到 ($F_{13}$, $F_{14}$)。每步常数次乘法和加法。如果用朴素自底向上，要 13 步。

对一般的 $n$，二进制位数是 $\log_2 n$，所以总共 $O(\log n)$ 步。每步常数次大数运算，每次大数运算的时间取决于数的大小，但总时间仍然是 $O(\log n)$ 次乘法的代价。

这就是快速倍增

这个算法叫"快速倍增"（fast doubling）。它的核心是：

一对相邻斐波那契数 ($F_{k}$, $F_{k+1}$) 可以被翻倍成 ($F_{2k}$, $F_{2k+1}$)。
用 $n$ 的二进制表示控制翻倍和加一，跳着到 ($F_n$, $F_{n+1}$)。

时间 $O(\log n)$，空间 $O(1)$（不算大数存储）。

跑 $F_{10^{18}}$，自底向上要 $10^{18}$ 步，几亿年。快速倍增在下标层面的递归深度约为 $\log_2(10^{18}) \approx 60$ 步。

但要小心一个细节。如果只算 $F_{10^{18}} \bmod m$ 这种余数，60 步确实足够，因为中间结果不超过 $m^2$。如果要输出精确整数，结果本身约有 $2.09 \times 10^{17}$ 位十进制数字（因为 $\log_{10} \varphi \approx 0.209$，所以 $\log_{10} F_n \approx 0.209 n$），不可能瞬间输出。本章后面提到"快速倍增 $O(\log n)$"都是指下标层面的步数，不是指实际输出大整数的时间。

为什么"翻倍"能成立

这件事值得多想一下。

朴素自底向上加法，是从 $F_{k}$ 加到 $F_{k+1}$ 一步一步走。每一步只看相邻两项，所以每次只能前进 1。

快速倍增能跳，是因为它用了一种"远距离"的依赖关系。具体来说，加法公式 $F_{n+m}$ = $F_{n+1}$ $F_{m}$ + $F_n$ $F_{m-1}$ 告诉我们：$F_{n+m}$ 不只是 $F_{n+m-1}$ 和 $F_{n+m-2}$ 的和，它还可以用 $F_n$ 和 $F_{m}$ 的乘积表示。

这意味着斐波那契数之间有一种"全局"的乘积关系。这种乘积关系允许我们把 k 步加法压缩成 1 次乘法。

为什么会有这种乘积关系？因为斐波那契递推是线性的。线性递推的解可以写成若干个 $r^{n}$ 的线性组合，其中 r 是特征方程的根。这意味着 $F_{n+m}$ 中的 (n+m) 可以拆成 n 和 m，分别用 $r^{n}$ 和 $r^{m}$ 表示。所以乘积形式是自然的。

这个观察在第 8 章（闭式公式）和尾声（一般线性递推）里会再次出现。这里只是先让你看到："线性"这个性质不只是说递推式里没有 $F_n^2$ 之类的项，它还隐含着一系列乘积恒等式，而这些恒等式让我们可以跳步。

加法变乘法，是结构允许跳步

到这里可以总结一下快速倍增的精髓。

朴素自底向上已经很聪明了。它发现子问题重叠，所以每个子问题只算一次。但是它只用了"局部"的递推关系：$F_{k}$ 依赖 $F_{k-1}$ 和 $F_{k-2}$。

快速倍增更进一步。它发现了"全局"的乘积关系：$F_{n+m}$ 可以用 $F_n$ 和 $F_{m}$ 表示。所以 $F_{2k}$ 不需要 k 步加法，只需要 1 次乘法。

把加法变成乘法，本质上是利用了递推的线性结构。线性带来可分性，可分性带来跳步。

这是斐波那契给我们的第四个教训。它告诉我们：算法的快慢，不只取决于代码写得多精巧，还取决于我们对底层结构的利用有多深。

一个小尾巴：再加一道恒等式

最后再补一个快速倍增会用到的小技巧。翻倍之后要做"加一"，从 ($F_{k}$, $F_{k+1}$) 变到 ($F_{k+1}$, $F_{k+2}$)。$F_{k+2} = F_{k+1} + F_{k}$是显然的。

但是有时候我们也想从 ($F_{k}$, $F_{k+1}$) 直接跳到 ($F_{2k+1}$, $F_{2k+2}$)，跳两格而不是一格。这种情况怎么算？

$F_{2k+2} = F_{2k+1} + F_{2k}$，两个值都已经在翻倍公式里算出来了，加一下就行。

更一般地，所有 $F_n$ 都可以通过"翻倍 + 一步前进"组合出来。具体的实现细节这里不展开，留到下一章讲完矩阵快速幂之后会看得更清楚。矩阵的乘法天然地把"翻倍"和"前进"统一成同一种操作。

下一章我们换一种工具看同一个跳步结构。不再用代数恒等式，改用矩阵幂。结果会发现，快速倍增公式其实是矩阵平方的展开版。

第 6 章 矩阵快速幂

上一章我们用快速倍增把斐波那契做到了 $O(\log n)$。这一章换一种工具看同一个跳步结构：矩阵快速幂。

矩阵在斐波那契里的位置很有意思。第一次见它的人会觉得"为什么要扯上矩阵"，但是看清楚之后会发现，矩阵只是把快速倍增的代数恒等式换了一种紧凑的写法。

把递推写成矩阵

回忆斐波那契递推：$F_{n+1} = F_n + F_{n-1}$。

把它和恒等式 $F_n = F_n$ 凑在一起，可以写成：