企业官网建设流程全解析

第四夜 · 影分身与记事本

灯又亮了。第四夜。

上一夜，神庙的僧侣还在慢慢搬。收工之后，我把那座庙写成了三段能跑的程序。写完第三段，雪花分形的那一段，我盯着屏幕发了很久的呆。程序里每一条边都把自己交给四条更短的边，函数在它自己的函数体里调用它自己，一层，又一层。我调用了它，它又调用它自己，每一次调用都裂出一个新的自己，在原地做事，做完就散。那一刻，我想起恰好摊在案头的《三国演义》。

第六十八回。宴席上，左慈掷出酒杯，杯子悬在半空，化作一只白鸠，绕殿而飞。满座的人抬头去找那只鸟，席位上的左慈已经不见了。曹操下令捉拿。第二天，满城都是左慈。一模一样的黄发，一模一样的羊裘，捉来一个，斩一个，街市上断头倒卧的，三百余人，头颅升空，都化作白鸠飞了。真正的那个，谁也没有捉到。

我合上书，忽然觉得递归这回事，整个就是一场无尽的分身术。每一次调用，本体裂出一只分身，把一半家事交给它；分身再裂，一直裂，直到裂到那个不必再裂的终点，然后一个接一个地散场，把答案一层一层传回本体。机器替这一切记着名册，每一次调用，名册上添一个名字。这本名册有个学名，叫调用栈。只是它摊在机器的暗处，你看不见它。

看不见，不等于不能讲。这一夜，就讲这本名册怎样被撑爆，又怎样被一页小小的记事本救回来。

1202 年，比萨的莱昂纳多写了一本书，叫《计算之书》。书里第十二章收着一道题。

有一个人把一对小兔子放进四面围墙的围栏里。兔子出生满一个月就成年，从第二个月末起，每一对成年兔每个月生一对新的小兔，兔子永不死。问一年之后，围栏里有多少对兔子？

一月，一对。二月，还是一对。三月，那对兔生下一对，两对。四月，再添一对，三对。五月，五对。六月，八对。七月，十三对。

把每个月的对数排成一列。1，1，2，3，5，8，13，21，34，55……从第三个月起，每一个数都是前两个数的和。这不是巧合，这是兔子的日子本身。上个月在围栏里的兔子，这个月一只不少；其中满一个月的，各生一对新的。本月总数，等于上月总数加本月新生，而本月新生的对数，恰好是上上个月的总数。

这个数列后来跟着莱昂纳多的绰号走，叫斐波那契数列。斐波那契，意思是波那契之子。这列数其实比他早了好几个世纪，出现在印度的韵律学里，用来数诗行中长音与短音的排法。把数列装进兔子问题、写进书里的，是他。中文世界里，这道题另有个更狠的别名，叫不死神兔。不死永生，听着就让人后背发凉。

用 f(n) 记第 n 个月的兔子对数，规则只有两句。头两个月，各是一对；从第三个月起，f(n) 等于 f(n-1) 加 f(n-2)。写出来只消三行。一行本体，头两个月，直接报一对；一行分身，把这个月的问题拆成上两个月的问题，各交给一个新的自己；一行合拢，把两份答案相加，报给叫它的人。这不是什么巧妙的技巧，这是兔子繁殖规则的直译。规则怎么说，代码就怎么写。

fib(10)，五十五对，眨眼就回。fib(20)，六千七百六十五对，还是眨眼。fib(45)。

我等着。

等了两秒多，答案出来了，1134903170，十一亿三千多万对。这个数不大，long 装得下，离它的天花板还远得很。可是两秒多里，机器在名册上添了 2269806339 个名字。二十二亿多次调用。

因为分身分裂的速度在失控。

fib(45) 要问 fib(44) 和 fib(43)。fib(44) 要问 fib(43) 和 fib(42)。你注意到了吗，fib(43) 被问了两次。fib(42) 被问了三次。再往深处走，同一个问题被问的次数疯长。实跑数出来，fib(30) 在这一问里被从头算了九百八十七次，fib(10) 被算了一千四百九十三万次。每一个分身都干得勤勤恳恳，没有谁偷懒；挤死这条路的，恰恰是勤快本身。

把 fib(5) 这棵最小的爆炸现场解剖给你看。九次提问，画在下面。

图 4-1 fib(5) 的调用树。第五个月的每一次提问都裂成两问，直到撞上头两个月的那对兔子才停。虚线框里是两棵一模一样的子树，fib(3) 被问了两次，fib(2) 三次，fib(1) 两次，右边那棵从头到尾，都是左边已经做过的事。这还只是第五个月。到第四十五个月，同一页名册要写下 2269806339 个名字。

第二夜那口井，塌在第 22835 层，那是永远回不来。这里的死法是另一副面孔。回得来，可是回来的人太多，多得把路挤死了。朴素递归不是算不出，是算不完。

我把 45 改成 50，起身倒了一杯水。回来的时候，它还在数。fib(50) 等于 12586269025，一百二十六亿对，本机实测三十七秒。在指数面前，机器和人一样，只有干看着的份。

满城的左慈。抓不完，也斩不尽。可是你想过没有，那些分身干的真是新事吗？fib(30) 被九百八十七个分身各算各的，fib(10) 被一千四百九十三万个分身各算各的，每一个都以为自己是头一个想到的。爆炸的秘密不在问题多，在同一个问题被反复地问。围栏里的月份只有四十五种，名册上的提问却有二十二亿次，平均每一种问题，被问了五千万遍。

假如每个分身手里有一页本子。算过的数记在上面，再有分身来问同一个数，翻开本子直接报，不必重算。你说会怎么样？

一行改动。

递归的骨架一个字没动，本体还是本体，分身的还是分身。只是多了一页本子，多了一个先翻本子的动作，多了一个算完记下的动作。本子上记过的直接报，没记过的才裂分身，算完顺手记下。就这一行，fib(45) 从两千两百九十四毫秒，掉到不足十微秒；名册上的二十二亿次提问，缩成八十七次。fib(50)，fib(92)，一样眨眼就回。指数膨胀坍缩成一条直线，一只分身只算一次，算完写下来，后来的分身只管抄。

这一招有名字，叫记忆化。1968 年，英国人唐纳德·米契在《自然》杂志上发了一篇短文，给这种翻本子的函数起了名字，memo function，memo 取自 memorandum，备忘录。他想让程序跟人一样，学过的不再重学。五十多年过去，这个词住进了每一种语言的口袋。

本子救了问的次数，救不了问的方式。递归还是那个问法，从终点一路往下问，每一问都在名册上压一层。名册有尽头。机器为每一次调用预备一小块地皮，装着参数、局部变量和回来的路。问得浅，地皮用不完；问得深，一层地皮叠一层，总有叠穿的一天。叠穿的那一下，Java 抛出的错叫 StackOverflowError。顺带说一句它的户口，它不是异常，Java 把它归在 Error 名下，意思是这等错处，别指望程序自己收拾。第二夜那口井，就是塌在这里。

fib 走不深，四十五层，离塌还远。可是那个问法还立在原地。每一个答案都踩着前两个，可每一个都要从终点往下问一遍。看清这个问法，你就看清了一件事。fib(3) 只认 fib(2) 和 fib(1)，fib(4) 只认 fib(3) 和 fib(2)，依赖的方向是单向的，一层只踩一层。那么，何必从终点往下问。从 fib(1) 和 fib(2) 动身，按月份的顺序往上走，每一步都踩在已经算好的答案上，名册就用不着了。

不请分身了。自己拿两个名额，上个月的对数和这个月的对数，从一月走到要问的那一月。每往前走一个月，两个名额往前滚一格。一个循环，两个变量，零次调用。fib(92)，7540113804746346429，long 装得下的最后一个，微秒级就回。

递归从终点往下问，递推从起点往上走，做的是同一件事，走的不是同一条路。一条叫自顶向下，一条叫自底向上。条条大路通罗马，有的路坐着马车，有的路走着过去，风景不同，到的都是同一座城。

分身会散场，本子留得下来。这一夜说的是兔子，说的是分身，其实说的是省下的那二十多亿次。能看见自己正在重复的人，才有资格停止重复。

这一夜的三版围栏，我都留了下来。第一版是满城的分身，第二版是发了本子的分身，第三版连分身也不请。你要是不信指数会爆炸、记忆化救得了场，自己跑一跑，数一数。

第一版 · 满城的分身

import java.io.PrintStream; /** * 《算法一千零一夜》第四夜 · 满城的分身（朴素递归） * 每一次提问都裂成两问，每个分身再裂出两个新的分身， * 直到撞上头两个月的那对兔子，才有一个分身停下来。 * 这一版不加任何记性，让指数爆炸当着你的面演一遍。 * 运行提示：最后一个月要等上几十秒；若把 50 改成 60，够读完一章书。 */ public class FibClones { static long asks = 0; // 名册。每叫一次分身，记一个名字。 static long fib(int n) { asks++; // 提问一次，名册添一笔。 if (n <= 2) { return 1; // 头两个月，围栏里只有一对，不必再问。 } return fib(n - 1) + fib(n - 2); // 裂成两问交给下一辈，两份答案合龙，报给叫它的人。 } static void month(int n) { asks = 0; long t0 = System.nanoTime(); long answer = fib(n); long t1 = System.nanoTime(); System.out.println("第 " + n + " 个月，围栏里 " + answer + " 对，名册记了 " + asks + " 次提问，耗时 " + (t1 - t0) / 1000000 + " 毫秒。"); } public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, "UTF-8")); month(10); month(20); month(45); month(50); } }

第二版 · 发下去的本子

import java.io.PrintStream; /** * 《算法一千零一夜》第四夜 · 发下去的本子（记忆化） * 分身还是那些分身，递归的结构一个字没有改， * 只是每人发了一页本子。算过的数记在上面， * 再有分身来问同一个数，翻开本子直接报，不再重算。 * 米契 1968 年在《自然》上给这一招起名 memo，取自 memorandum，备忘录。 */ public class FibNotebook { static long[] memo = new long[93]; // 本子只发到第九十二个月，long 装得下的最后一页。 static long fib(int n) { if (n <= 2) { return 1; // 头两个月，照旧守门。 } if (memo[n] != 0) { return memo[n]; // 本子上记过，直接报数，不裂分身。 } memo[n] = fib(n - 1) + fib(n - 2); // 没记过的才裂分身去算，算完记在本子上。 return memo[n]; } static void month(int n) { long t0 = System.nanoTime(); long answer = fib(n); long t1 = System.nanoTime(); System.out.println("第 " + n + " 个月，围栏里 " + answer + " 对，耗时 " + (t1 - t0) / 1000000.0 + " 毫秒。"); } public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, "UTF-8")); month(45); month(50); month(92); } }

第三版 · 一个人的散步

import java.io.PrintStream; /** * 《算法一千零一夜》第四夜 · 一个人的散步（迭代递推） * 这一次不请分身。答案只依赖前两个月，那就自己拿着两个名额， * 从第一个月走到要问的那一个月，每一步都踩在已经算好的答案上。 * 递归从终点往下问，递推从起点往上走，到的是同一座城。 */ public class FibWalk { static long fib(int n) { long prev = 1; // 上个月的兔子对数，先按第二个月算。 long curr = 1; // 这个月的兔子对数。 for (int i = 3; i <= n; i++) { long next = prev + curr; // 下一个月，等于前两个月相加。 prev = curr; // 两个名额往前滚一格。 curr = next; } return curr; } public static void main(String[] args) throws Exception { System.setOut(new PrintStream(System.out, true, "UTF-8")); StringBuilder head = new StringBuilder("头十三个月： "); for (int i = 1; i <= 13; i++) { head.append(fib(i)); if (i < 13) { head.append("、"); } } System.out.println(head); long t0 = System.nanoTime(); long answer = fib(92); long t1 = System.nanoTime(); System.out.println("第九十二个月，围栏里 " + answer + " 对，耗时 " + (t1 - t0) / 1000000.0 + " 毫秒。"); } }

---

① 真伪核对逐条照实登记。

Ⅰ 兔子问题 1202 年，比萨的莱昂纳多在《计算之书》（Liber Abaci）第十二章写下这道兔子题；英译见 L. E. Sigler，Fibonacci's Liber Abaci（Springer，2002），兔子问题在第十二章。这列数比莱昂纳多早了几个世纪，见于印度韵律学，平伽拉（Pingala）的著述里已有长音组合的计数，维拉汉卡（Virahanka）明确给出前两数相加的规则，戈帕拉（Gopala，1135 年）与赫马钱德拉（Hemachandra，1150 年）先于 1202 年记载了这一数列，考据见 P. Singh 论文，载 Historia Mathematica 第 12 卷第 3 期，1985 年，229 至 244 页。斐波那契，意为波那契之子（filius Bonacci），是后世给莱昂纳多起的绰号，用这个名字称呼这个数列，是他身后几百年的事。

Ⅱ 记忆化 记忆化（memoization）一词出自唐纳德·米契（Donald Michie）1968 年 4 月 20 日刊于《自然》的短文 “Memo” Functions and Machine Learning，第 218 卷第 5136 期，19 至 22 页；memo 取自 memorandum（备忘录）。米契是英国人，战时在布莱奇利园做过密码分析。

Ⅲ 数字与实跑 fib(45) 等于 1134903170，fib(50) 等于 12586269025，fib(92) 等于 7540113804746346429，均未超出 long 的容量；long 的第一次回绕发生在第九十三个月，fib(93) 本值 12200160415121876738，按 64 位补码回绕成 -6246583658587674878，Java 对整数溢出不做任何提醒，规则见《Java 语言规范》15.18.2 节。朴素递归答 fib(45) 共 2269806339 次调用，本机实测两千二百九十四毫秒；答 fib(50) 共 25172538049 次调用，实测约三十七秒；树中 fib(43) 被问 2 次，fib(42) 3 次，fib(30) 987 次，fib(10) 14930352 次；图 4-1 的九次提问与 fib(3) 两次、fib(2) 三次、fib(1) 两次，均为程序实跑所数。三版程序均在本机 JDK 21 下编译运行，逐月互查，第一到第四十个月全部一致；本子版答 fib(45) 不足十微秒，提问恰好 87 次；散步版答 fib(92) 微秒级。秒数以你的机器为准。

Ⅳ 左慈与第六十八回 满城分身一段，本事出自《三国演义》第六十八回，甘宁百骑劫魏营，左慈掷杯戏曹操。掷杯化白鸠、满城捉出黄发羊裘的同貌人、街市断头三百余人、头颅升空化鸠，皆系小说家言；正史里的左慈见《后汉书·方术列传》，无分身被斩之事。

Ⅴ 术语三笔 调用栈（call stack），机器为每次调用预留的一块记录，装着参数、局部变量与返回地址。StackOverflowError 在 Java 里归在 Error 一族，不在 Exception 之下，抛出即程序终止。Java 虚拟机至今不做尾调用优化，递归改写成递推的替换，机器不会替你做，Scala 与 Kotlin 的尾递归优化发生在编译器一层。自顶向下（top-down），自底向上（bottom-up）。

② 今夜习题两道，评论区见。

Ⅰ 把 fib(5) 的名册画在纸上，图 4-1 借你抄。数一数，fib(3) 被问了几次，fib(2) 被问了几次。再画 fib(6)，再数一遍。然后不必画了，推一推，fib(10) 的名册里，fib(2) 要被问多少次？

Ⅱ 围栏交给程序看守。用第三版的程序往第九十三个月走，报数第一次变成了负数。这一页写的是哪个数？它是怎么来的？

你算出来了吗？评论区见。（答案与参考程序，收在书后《参考解答》。）

本书目录导航上一篇：第三夜 神庙之夜的汉诺塔 下一篇：第五夜 春节晚会魔术牌的秘密 起点：卷首语·算法童话

版权声明：本文为作者原创，受著作权法保护。未经授权禁止转载、搬运、摘编、改编及任何形式的二次创作；个人学习引用请注明作者与原文出处。转载授权请联系作者（CSDN 私信）。侵权必究。