递归的分解思维：汉诺塔与斐波那契

前半场 · 汉诺塔

1 一句话问题

三根柱子 A、B、C。A 上从下到上套着 n 个盘子，越往上越小。 把它们全部搬到 C 上，规则两条：

1. 一次只能搬一个盘子（而且只能搬某根柱子最上面的那个）
2. 任何时候，大盘子都不能压在小盘子上面

输出每一步怎么搬。

输入 3
输出 盘 1: A -> C
     盘 2: A -> B
     盘 1: C -> B
     盘 3: A -> C
     盘 1: B -> A
     盘 2: B -> C
     盘 1: A -> C
     共 7 步

2 先用纸笔手算一遍

真的拿三本书摞起来试一次，比看十遍讲解都管用。

n = 1   直接把它从 A 搬到 C。1 步。

n = 2   小盘 A→B，大盘 A→C，小盘 B→C。3 步。
        注意中间那一步：为了搬大盘，必须先把小盘挪到「不碍事的地方」。

n = 3   ？ 这里绝大多数人开始卡壳 —— 因为想在脑子里同时管住三个盘子。

卡住的时候，换一个问法。不要问「第一步搬哪个」，要问「最大的那个盘子什么时候动」。

它只可能动一次（动多了纯属浪费），而它要从 A 搬到 C，那一刻的棋盘必须长这样：

A: [3]          只剩最大的那个
B: [2][1]       上面两个全在这儿呆着
C: (空)         腾干净了，等着接

这张图一画出来，整件事就没有悬念了：

① 先把上面 2 个盘子从 A 搬到 B      ← 这是「把 2 个盘子从一根柱子搬到另一根」
② 把盘 3 从 A 搬到 C                ← 一步真活
③ 再把那 2 个盘子从 B 搬到 C        ← 又是「把 2 个盘子从一根柱子搬到另一根」

① 和 ③ 是什么？是同一道题，只是盘子少了一个。

3 ★ 关键的一步

// 职责：把 from 柱最上面的 k 个盘子搬到 to 柱，中途可以借用 via 柱
void hanoi(int k, char from, char to, char via) {
    if (k == 0) return;                  // 边界：没有盘子，什么都不用做
    hanoi(k - 1, from, via, to);         // ① 上面 k-1 个：挪去 via
    cout << "盘 " << k << ": " << from << " -> " << to << "\n";   // ② 真正搬一次
    hanoi(k - 1, via, to, from);         // ③ 那 k-1 个：从 via 搬到 to
}

4 递归写法

点「运行 ▶」看结果

有效代码就那三行。请对着它，把第 3 步那段「① ② ③」再念一遍。

5 把分解过程打印出来

点「运行 ▶」看结果

盯住带 ★ 的那些行 —— 它们才是真正搬了盘子的地方，一共 7 行。 其余全是「拆问题」的过程，一个盘子都没动。

6 单步看它怎么拆

播放的时候，主要看右边那根递归栈，不要只顾着看盘子飞来飞去：

• 栈里每一层后面都标着它停在「① / ② / ③」哪一步 —— 那就是代码里的那三行。
• 一层「进入」时立刻分成三步，然后第 ① 步又生出新的一层…… 这就是分解。
• 真正搬盘子的帧（第 ② 步）只有 2ⁿ-1 帧，其余全在拆问题。

把盘子数改成 4、5 各看一遍。你会发现代码一个字都没变， 但拆出来的层数自动变了 —— 这正是第 3 章那句「递归把循环层数交给了运行期」。

7 不用递归行不行？

行。下面这份没有任何递归，输出和递归版一模一样：

8 ★ 对拍验证

值得故意写错的地方，每一个都是真实高频错误：

• hanoi(k-1, from, via, to) 里的三个柱子写错顺序（比如写成 from, to, via） → 步数居然还是对的，但搬法完全不合法。这就是为什么要比对整个序列，而不是只比步数。
• 两次递归调用之间的 cout 挪到最前面（先搬大的再挪小的）→ 顺序全错
• 边界写成 if (k == 1) return; → 最小的那个盘子永远搬不动，少一堆步骤

9 这 2ⁿ 步是省不掉的

递归版慢吗？n = 20 要跑一百多万步，确实不快。但请分清楚是谁在慢：

点「运行 ▶」看结果

后半场 · 斐波那契

10 同样的分解，写出来却慢得莫名其妙

斐波那契数列：f(0) = 0，f(1) = 1，之后每一项都是前两项之和。

分解思维用在这儿再自然不过 —— 题目本身就是按「大问题 = 两个小问题」定义的：

long long fib(int n) {
    if (n < 2) return n;                 // 边界
    return fib(n - 1) + fib(n - 2);      // 递推：拆成两个更小的同类问题
}

职责、边界、递推，三要素齐活，而且它完全正确。点下面的「开始对比」：

本机实测：

11 慢在哪：把重复次数数出来

不要猜，数出来。下面这份给每个 fib(k) 装了个计数器：

点「运行 ▶」看结果

跑 n = 20 的结果（截取）：

  k    被调用次数
-----  ----------
 20             1
 19             1
 18             2
 17             3
 16             5
 15             8
 14            13
 ...
  1          6765
  0          4181

调用次数本身又是一串斐波那契数 —— 很漂亮，也很吓人。全表汇总：

n = 40 时，一共只有 41 个不同的值要算，程序却调用了 3.3 亿次。 其中每一次算出来的结果都和之前某一次一模一样。

12 ★ 关键的一步：子问题重不重叠

把两道题的分解并排画出来，差别一眼就看见了：

汉诺塔 hanoi(3, A→C)                    斐波那契 fib(5)
├── hanoi(2, A→B)                       ├── fib(4)
│   ├── hanoi(1, A→C)                   │   ├── fib(3)
│   └── hanoi(1, C→B)                   │   │   ├── fib(2)   ← 和右边那个
└── hanoi(2, B→C)                       │   │   └── fib(1)   
    ├── hanoi(1, B→A)                   │   └── fib(2)   ← 一模一样，重算了
    └── hanoi(1, A→C)                   └── fib(3)   ← 整棵子树又重算了一遍

左右两棵子树在搬「不同的盘子、不同的柱子」    左右两棵子树大面积重叠
每个任务都只出现一次                        同一个 fib(k) 出现无数次

long long f[100]; bool vis[100];

long long fib(int n) {
    if (n < 2) return n;
    if (vis[n]) return f[n];             // ← 查表：算过就直接还回去
    vis[n] = true;                       // ← 存表
    return f[n] = fib(n-1) + fib(n-2);
}

13 循环版 + ★ 对拍验证

回过头看斐波那契的循环版，和汉诺塔的循环版是完全不同的境遇：

long long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long long c = a + b; a = b; b = c; }

这个谁都想得到 —— 从小往大一项项推过去就完了，天然不会重复。 汉诺塔的循环版要靠魔法规律，斐波那契的循环版是常识。同样是「改成循环」，难度天差地别。

必踩的坑，试一个：

• 边界写成 if (n <= 1) return 1; → f(0) 返回 1，一对拍就抓住。 这是最常见的错误，因为「斐波那契从 1 1 2 3 开始」这个印象太深了。
• 写成 fib(n-1) + fib(n-1) → 得到 2ⁿ，还挺快，就是全错
• 循环版写成 a = b; b = a + b;（顺序错了，a 已经被改掉）→ 也是错的

14 自测