跳到主要内容

递归 — 在它自己身上找出一个小一号的它自己

这一章讲三件事: 一道乱糟糟的题怎么被「缩小规模」拆开; 「用自己解释自己」为什么不会绕成死循环; 以及找出那个「小一号的自己」有没有固定动作可循。

它在全书链条里的位置: 第 08 章的数学归纳法是「从小推到大」, 这一章是同一件事反过来走:从大缩到小。 第 12 章会拿同一把钥匙再开两把锁, 第 13、14 章会发现这条路上藏着一个可怕的东西(每缩一层就翻一倍)。 需要的基础: 会乘法;写过程序会更亲切,但不写也能读。

1. 先看现象:六个圆盘的汉诺塔​

三根柱子 A、B、C。A 柱上套着 6 个圆盘,从大到小自下而上摞着。 要把它们全部搬到 B 柱上,规矩两条1:

   ┌─┐              规矩一:一次只能搬最上面的 1 个圆盘
   ├─┤              规矩二:小圆盘上不能放大圆盘
   ├─┤
   ├─┤              问:最少要搬多少次?
   ├─┤
   ├─┤
  ═╧═╧═   ═══   ═══
    A      B     C

  图说:全章的主走查就是这一摞 —— 6 个圆盘,从 A 搬到 B。
       答案是 63 次,而这一章的正题是「63 是怎么算出来的」。

这个游戏是数学家爱德华·卢卡斯在 1883 年发明的2。

你可以现在就试着想一下六个圆盘怎么搬。 大多数人会立刻乱掉—— 因为搬到中途,你得同时记住「哪几个已经在哪儿」和「接下来该动谁」。

2. 第一步:先把规模缩小​

这一节回答:乱掉的时候该干什么。

原书的动作是:先别管 6 个,改看 3 个3。

三层的解法多试几次就找得到,一共 7 步4:

  ① A→B   ② A→C   ③ B→C   ④ A→B   ⑤ C→A   ⑥ C→B   ⑦ A→B

7 次。这是主走查的第一步。

但真正的收获不是 7 这个数,是在搬的过程中那种「怎么老在重复类似的动作」的感觉5。 原书特意点了这一句:这种感觉很重要——它来自人「发现规律的能力」。

具体重复在哪儿? 把上面七步里的 ①②③ 和 ⑤⑥⑦ 并排看6:

  • ①②③:三步,把 2 个圆盘从 A 挪到了 C;
  • ⑤⑥⑦:三步,把 2 个圆盘从 C 挪到了 B。

目的地不同,但这两段动作是同一件事——它们都是「两层汉诺塔」的解法。

3. 看出结构:六层 = 五层 + 一次 + 五层​

这一节是这一章的核心,请慢读。

按上一节那个发现往上推一层,六层的解法是这样三步7:

  ┌──────────────────────────────────────────────────┐
  │ ① 先把上面 5 个圆盘从 A 挪到 C   ← 这是「五层汉诺塔」│
  │ ② 把最大的那个圆盘从 A 挪到 B    ← 只有这一步是真的搬 │
  │ ③ 再把那 5 个圆盘从 C 挪到 B     ← 又是「五层汉诺塔」│
  └──────────────────────────────────────────────────┘

  图说:六层的解法里,有两段整个就是五层的解法。
       中间那一步是唯一「新增」的动作 —— 挪最大的那一个。

这是主走查的第二步。

为什么必须这样? 因为要把最大的圆盘从 A 挪到 B, A 柱上压在它上面的那 5 个必须先全部离开,而且不能挡在 B 上——只能去 C8。 这不是一种解法,这是唯一的走法,所以它同时也是最少的次数。

同样的话可以一层层往下说: 五层要用四层的解法、四层要用三层的解法…… 一层汉诺塔只要搬 1 次就完了9。

「在问题自己身上找出一个小一号的它自己」,这件事就叫递归。 原书把这个动作提炼成一句可以随身带走的话:

能不能把复杂的问题,转换成较为简单的同类问题?10

4. 用自己解释自己,为什么不会绕成死循环​

这一节回答一个必须回答的疑问。

「解六层要用解五层」——这听起来像用自己解释自己,不是在绕圈吗?

不是。因为每绕一次,问题都小一号11。

  6 层 → 5 层 → 4 层 → 3 层 → 2 层 → 1 层 → 0 层
                                              ↑
                                    到这里停:什么也不用做

  图说:每往右一步,规模就减 1。因为规模不能无限减下去,
       所以这条链一定会在某处停住 —— 那个停住的地方叫「底」。

零层汉诺塔的解法是「什么也不做」12。这个「什么也不做」不是敷衍, 它是整条链的落脚点——就像第 08 章里那句「先推倒第 0 张骨牌」。

5. 写成式子:从 H(0) 一路算到 63​

这一节把上面那条结构变成能算的东西。

把「解 n 层汉诺塔最少要搬几次」记作 H(n)。 那么第 3 节那三步就变成13:

  H(n) = H(n−1)  +  1  +  H(n−1)
         └─ ① ─┘   └②┘  └─ ③ ─┘
         挪走上面    挪最大  再挪回来
         n−1 个      那一个   n−1 个

再加上落脚点 H(0) = 0,这个式子就完整了。 这种「拿上一层表示这一层」的式子,叫递推公式14。

有了它就能一行一行往上算15:

n算式结果
0——0
10 + 1 + 01
21 + 1 + 13
33 + 1 + 37 ← 和第 2 节手工试出来的一致
47 + 1 + 715
515 + 1 + 1531
631 + 1 + 3163

63 次。这是主走查的第三步,答案出来了16。

注意第 3 行:7 这个数是第 2 节用手试出来的,现在它是算出来的。 两条路对上了,说明那条结构没看错。

6. 再抽一层:2ⁿ − 1​

这一节回答:每次都要从 0 一行行算上来,有没有更直接的。

盯着那一列结果看:0、1、3、7、15、31、63。 每一个都比 2 的某次方小 117:

   0 = 1 − 1 = 2⁰ − 1
   1 = 2 − 1 = 2¹ − 1
   3 = 4 − 1 = 2² − 1
   7 = 8 − 1 = 2³ − 1
  63 = 64 − 1 = 2⁶ − 1

所以 H(n) = 2ⁿ − 1。这种只用 n 就能直接算出结果的式子,叫解析式18。 这是主走查的第四步。

递推公式和解析式的分工要分清:

递推公式解析式
长什么样H(n) = 2 × H(n−1) + 1H(n) = 2ⁿ − 1
怎么用从 0 一行行算上来代进 n 直接出结果
好不好找容易——看出结构就有了难——常常根本找不到

原书的态度很实在:能总结出解析式当然最便捷,但找不到也没关系, 只建立递推公式一样非常有用19——因为它已经能算出具体数值,也已经抓住了问题的本质。

顺带记一个数:2ⁿ − 1 里那个 2ⁿ,就是第 09 章那 32 个灯泡的同一个东西。 64 个圆盘的汉诺塔要搬 2⁶⁴ − 1 次——这条路通向第 13 章。

7. 写成程序:十行​

这一节走主走查的最后一步。

第 3 节那三步几乎就是伪代码,所以翻成 C 语言非常直接20:

void hanoi(int n, char x, char y, char z)   // 把 n 个圆盘从 x 挪到 y,借道 z
{
    if (n == 0) {
        /* 什么也不做 */                     // ← 落脚点
    } else {
        hanoi(n - 1, x, z, y);              // ① 上面 n−1 个:从 x 挪到 z
        printf("%c->%c, ", x, y);           // ② 最大的那个:从 x 挪到 y
        hanoi(n - 1, z, y, x);              // ③ 那 n−1 个:从 z 挪到 y
    }
}

跑 hanoi(6, 'A', 'B', 'C'),它会打印出全部步骤;数一数,正好 63 步21。 主走查到这里走完了:从「乱糟糟的 6 个圆盘」到「63 次」到「十行代码」。

这段代码值得看的地方是它的形状:一个 if 分两半—— 上半是「什么也不做」的落脚点,下半是「调用小一号的自己」。 几乎所有递归程序都长这个样子。

8. 找递归结构的固定动作,以及 0! = 1 的账​

这一节回答:汉诺塔是特例吗,还是有套路。

有套路,而且只有两句话22:

  ① 从整个问题里,遮住一部分
  ② 看剩下的是不是「小一号的同一道题」

  图说:遮住的那部分,就是「这一层新增的动作」;
       剩下那部分,就是可以直接拿来用的「小一号的自己」。

拿汉诺塔套一遍:遮住「挪最大的那一个」,剩下的正是两次五层汉诺塔。

另起一处走查,拿阶乘再套一遍。 第 10 章说 5! = 5 × 4 × 3 × 2 × 1, 用递归的说法就是23:

  n! = 1                 (n = 0 时)      ← 落脚点
  n! = n × (n−1)!        (n ≥ 1 时)      ← 小一号的自己

把 3! 一层层展开24:

  3! = 3 × 2!
     = 3 × 2 × 1!
     = 3 × 2 × 1 × 0!
     = 3 × 2 × 1 × 1        ← 最后那个 1 就是 0!
     = 6

第 10 章挂的那笔账,在这里还了:0! 为什么必须是 1? 因为如果 0! 不是 1,上面这条展开就到不了底、也算不对25。 又一次是同一条准绳:值是被定义出来的,准绳是让规则不分叉。

9. 递归和归纳,是同一件事的两个方向​

这一节把这一章和第 08 章接起来。

你大概已经发现,阶乘的递归定义和数学归纳法长得很像26:

数学归纳法(第 08 章)递归(这一章)
起点证 P(0) 成立(基底)n = 0 时直接给出答案(落脚点)
一步由 P(k) 推出 P(k+1)由「小一号的自己」拼出这一层
方向从小往大推从大往小缩

原书说得很干脆:递归和归纳在本质上是相同的,都是「将复杂问题简化」, 只是方向不同27。它还把第 08 章那个 prove 函数用递归的写法重写了一遍—— 同一个证明,一个写成循环,一个写成递归28。

10. 作者的判断、我们的判断,以及这一章的边界​

说法书里给了什么
六层要 63 次给了完整走查:三层试出 7 次 → 结构 → 递推式 → 逐行算到 63 → 程序验证
这是最少的次数给了理由:要挪最大的那个,上面的必须先全部让开
找不到解析式也没关系是作者的态度,理由是递推式已经能算出数值、也能把握本质
找递归结构的两句话给了动作,而且在阶乘、组合数、图形上各验了一遍
递归与归纳只是方向不同是作者的说法,并给了一段脚注出处(Paul Hudak 的书)

判断(我们的,不是书里的):这一章最该带走的是「先缩小规模」这个动作, 而不是「会写递归函数」。 递归函数在实际工程里常常被改写成循环(怕栈溢出), 但「先解一个小一号的、再看大的能不能靠它拼出来」这个思路, 在拆需求、排查故障、设计一段程序对外怎么用的时候,同样管用。 如果错,会错在: 有一类问题缩小之后并不同构(小规模有特殊结构、大规模没有), 这时「先试小的」反而会误导。判据是:你缩小之后那道题,规则有没有变。

这一章的边界:

  • 没有讲递归的代价:每递一层都要占一份栈空间,层数太深会崩——原书完全没提;
  • 没有讲重复计算的问题(第 12 章的斐波那契用递归写会慢得离谱,原书也没提);
  • 没有证明「63 次是最少的」,只给了「必须先让开」这个直觉理由;
  • 解析式 2ⁿ − 1 只是「看出来的」,原书说可以用数学归纳法证明,但没有证;
  • 递归与循环怎么互相改写,只给了一个例子,没有讲一般做法。

11. 可带走的​

  1. 乱掉的时候,先把规模缩小——六个圆盘想不动,就先解三个;
  2. 三层要 7 步,而更值钱的是搬的过程中那种「怎么老在重复」的感觉;
  3. 六层 = 先解五层 + 挪一次最大的 + 再解五层——这就是那个「小一号的自己」;
  4. 在问题身上找出小一号的它自己,这叫递归;
  5. 不会绕成死循环,因为每绕一次规模就减 1,减到 0 层时「什么也不做」;
  6. 递推公式 H(n) = H(n−1) + 1 + H(n−1),从 H(0)=0 一行行算到 H(6) = 63;
  7. 解析式 H(n) = 2ⁿ − 1;递推式容易找、解析式常常找不到,找不到也够用;
  8. 递归程序的形状都一样:一个 if,上半是落脚点,下半是调用小一号的自己;
  9. 找递归结构的动作:遮住一部分,看剩下的是不是小一号的同一道题;
  10. 0! = 1 的理由在这里:不这么定,阶乘的递归展开就到不了底;
  11. 递归和归纳是同一件事的两个方向:一个从大缩到小,一个从小推到大。

12. 原文地图​

主题原书章原文位置
汉诺塔的规矩与出处第6章　递归text/11-ch06.txt:36(搜「爱德华·卢卡斯」) · :51(搜「1 次只能移动柱子最上端的 1 个圆盘」)
先解三层、发现重复第6章　递归text/11-ch06.txt:67(搜「移动 7 次可解决问题」) · :93(搜「在重复做相似的事情」) · :97(搜「移动 3 次将 2 个圆盘从 A 柱移到了 C 柱」)
六层的三步分解第6章　递归text/11-ch06.txt:124(搜「首先，将 5 个圆盘从 A 柱移到 C 柱」) · :140(搜「就必须将上」)
n 层的一般写法第6章　递归text/11-ch06.txt:158(搜「将 n 个圆盘从 x 柱」) · :159(搜「当 n = 0 时」)
递推公式与 63第6章　递归text/11-ch06.txt:190(搜「称为递推公式」) · :194(搜「H(0) = 0」) · :202(搜「答案：63 次」)
解析式第6章　递归text/11-ch06.txt:222(搜「H(n) = 2n − 1」) · :224(搜「叫作解析式」) · :307(搜「如果能够总结出解析式自然最为」)
汉诺塔程序第6章　递归text/11-ch06.txt:239(搜「void hanoi(int n, char x, char y, char z)」) · :273(搜「确实是 63 次」)
找递归结构的动作第6章　递归text/11-ch06.txt:292(搜「能将复杂问题转换为较为简单的同类问题吗」) · :769(搜「从 n 层的整体问题中隐去部分问题」)
阶乘的递归定义与 0!第6章　递归text/11-ch06.txt:321(搜「这可称为阶乘的递推公式」) · :336(搜「从阶乘的递归定义出发来看一下 3!」) · :361(搜「若 0! 不是 1」)
递归与归纳第6章　递归text/11-ch06.txt:386(搜「在本质上是相同的」) · :403(搜「递归和归纳，只是方向不同」)

Footnotes​

  1. 出处:「第6章　递归——自己定义自己」第 42 段(text/11-ch06.txt:42,搜「A 柱上套着 6 个圆盘」)与第 51 段(text/11-ch06.txt:51,搜「1 次只能移动柱子最上端的 1 个圆盘」)。 ↩

  2. 出处:「第6章　递归——自己定义自己」第 36 段(text/11-ch06.txt:36,搜「爱德华·卢卡斯」)。原文的原话是:「汉诺塔」是一个由数学家爱德华·卢卡斯(Édouard Lucas)于 1883 年发明的游戏。 ↩

  3. 出处:「第6章　递归——自己定义自己」第 59 段(text/11-ch06.txt:59,搜「所以我们先缩小问题的规模」)。「先缩小规模」这个动作在第 06、10 章也用过,是全书最常出现的一招。 ↩

  4. 出处:「第6章　递归——自己定义自己」第 67 段(text/11-ch06.txt:67,搜「移动 7 次可解决问题」)。原书图 6-3 把七步一步步画了出来。 ↩

  5. 出处:「第6章　递归——自己定义自己」第 93 段(text/11-ch06.txt:93,搜「在重复做相似的事情」)。原文说:之所以会产生这种感觉,是因为我们有「发现规律的能力」,这种感觉很重要。 ↩

  6. 出处:「第6章　递归——自己定义自己」第 97 段(text/11-ch06.txt:97,搜「移动 3 次将 2 个圆盘从 A 柱移到了 C 柱」)与第 117 段(text/11-ch06.txt:117,搜「但这 2 个动作是非常相似的」)。 ↩

  7. 出处:「第6章　递归——自己定义自己」第 124 段(text/11-ch06.txt:124,搜「首先，将 5 个圆盘从 A 柱移到 C 柱」)起的三行。 ↩

  8. 出处:「第6章　递归——自己定义自己」第 140 段(text/11-ch06.txt:140,搜「就必须将上」)。原文的原话是:因为要把最大的圆盘从 A 柱移到 B 柱,就必须将上面的 5 个圆盘都先移到 C 柱——这也是原书用来说明「这是移动次数最少的解法」的全部理由。 ↩

  9. 出处:「第6章　递归——自己定义自己」第 149 段(text/11-ch06.txt:149,搜「只要移动 1 次圆盘就」)。 ↩

  10. 出处:「第6章　递归——自己定义自己」第 292 段(text/11-ch06.txt:292,搜「能将复杂问题转换为较为简单的同类问题吗」)。原文紧接着写:这就是递归的思维方式。 ↩

  11. 出处:「第6章　递归——自己定义自己」第 334 段(text/11-ch06.txt:334,搜「却不会循环无解」)。原文讲的是阶乘,理由同样适用于汉诺塔:因为使用了比 n 低一层的规模来定义 n。 ↩

  12. 出处:「第6章　递归——自己定义自己」第 159 段(text/11-ch06.txt:159,搜「当 n = 0 时」)与第 160 段(text/11-ch06.txt:160,搜「不用做任何动作」)。 ↩

  13. 出处:「第6章　递归——自己定义自己」第 188 段(text/11-ch06.txt:188,搜「解出 n 层汉诺塔的移动次数」)。原书把这个式子的三段各自标了注:解出 n−1 层的次数、移动最大圆盘的次数、再解出 n−1 层的次数。 ↩

  14. 出处:「第6章　递归——自己定义自己」第 190 段(text/11-ch06.txt:190,搜「称为递推公式」)。原书给的英文是 recursion relation / recurrence。 ↩

  15. 出处:「第6章　递归——自己定义自己」第 194 段(text/11-ch06.txt:194,搜「H(0) = 0」)起的七行,原书把每一行的算式和结果都写了出来。 ↩

  16. 出处:「第6章　递归——自己定义自己」第 202 段(text/11-ch06.txt:202,搜「答案：63 次」)。 ↩

  17. 出处:「第6章　递归——自己定义自己」第 210 段(text/11-ch06.txt:210,搜「直觉敏锐的人或许已经找到了下述规律」)起的七行。 ↩

  18. 出处:「第6章　递归——自己定义自己」第 222 段(text/11-ch06.txt:222,搜「H(n) = 2n − 1」)与第 224 段(text/11-ch06.txt:224,搜「叫作解析式」)。原文还说,这个解析式可以用数学归纳法来证明——但书里没有证。 ↩

  19. 出处:「第6章　递归——自己定义自己」第 307 段(text/11-ch06.txt:307,搜「如果能够总结出解析式自然最为」)。原文说:若找不到解析式,只建立递推公式也是非常有用的,因为它是得出具体数值的线索,同时也能帮我们把握问题的本质。 ↩

  20. 出处:「第6章　递归——自己定义自己」第 239 段(text/11-ch06.txt:239,搜「void hanoi(int n, char x, char y, char z)」)。这是原书的代码清单 6-1,注释是我们加的。 ↩

  21. 出处:「第6章　递归——自己定义自己」第 257 段(text/11-ch06.txt:257,搜「A->C, A->B, C->B」)与第 273 段(text/11-ch06.txt:273,搜「确实是 63 次」)。原书把 63 步的输出全部印了出来。 ↩

  22. 出处:「第6章　递归——自己定义自己」第 769 段(text/11-ch06.txt:769,搜「从 n 层的整体问题中隐去部分问题」)与第 770 段(text/11-ch06.txt:770,搜「判断剩余部分是否是 n − 1 层的问题」)。原书把这两句称为「发现递归结构的要领」。 ↩

  23. 出处:「第6章　递归——自己定义自己」第 321 段(text/11-ch06.txt:321,搜「这可称为阶乘的递推公式」)。原文说这样定义「既能明晰 0! 的值,又能省略上面式子中的『…』部分」。 ↩

  24. 出处:「第6章　递归——自己定义自己」第 336 段(text/11-ch06.txt:336,搜「从阶乘的递归定义出发来看一下 3!」)起的几行。 ↩

  25. 出处:「第6章　递归——自己定义自己」第 361 段(text/11-ch06.txt:361,搜「若 0! 不是 1」)。原文的原话是:若 0! 不是 1,就无法顺利进行上述递归定义。 ↩

  26. 出处:「第6章　递归——自己定义自己」第 362 段(text/11-ch06.txt:362,搜「大家是否发现阶乘的递归定义和第 4 章学过的数学归纳法比较类似」)。原文明确对应:n = 0 时相当于步骤 1(基底),n ≥ 1 时相当于步骤 2(归纳)。 ↩

  27. 出处:「第6章　递归——自己定义自己」第 386 段(text/11-ch06.txt:386,搜「在本质上是相同的」)与第 403 段(text/11-ch06.txt:403,搜「递归和归纳，只是方向不同」)。原书这一节挂了一条脚注,说内容参考了 Paul Hudak 的《The Haskell School of Expression》。 ↩

  28. 出处:「第6章　递归——自己定义自己」第 392 段(text/11-ch06.txt:392,搜「void prove(int n)」)。这是代码清单 6-2:同一个 prove 函数,第 4 章用循环写,这里用递归写。 ↩