从汉诺塔看分治与递归：问题分解、代码实现与复杂度解析（Hello 算法 源码级讲解）

汉诺塔（Tower of Hanoi）是递归与分治思想的经典载体。本篇基于《Hello 算法》开源仓库中 汉诺塔问题章节 展开，结合仓库内 15 种语言的 hanota 示例源码，从最朴素的基础情形出发，逐步推导出通用分治策略，并给出可运行的递归代码与时间复杂度证明。读完本文，你将掌握“把一个规模为 n 的问题拆成两个规模为 n−1 的子问题”的建模方式，以及递归函数中源柱、缓冲柱、目标柱三者轮换的精髓。

汉诺塔之所以被放在“分治”章节的收尾位置，是因为它与前文（归并排序、构建二叉树）展示的分治策略形成鲜明对比：归并排序等把原问题拆成两个“各占一半”的子问题，而汉诺塔则是把 f(n) 拆成两个 f(n−1) 与一个 f(1)，这提示我们分治的“划分比例”并不总是均匀的。阅读时可先通读同章的前置内容 分治算法总论 与 二分查找（递归版）、构建二叉树问题 以获得完整的章节脉络。

问题定义：三根柱子、三条规则

题目描述如下：给定三根柱子，记为 A、B、C。初始时柱子 A 上堆叠了 n 个圆盘，自上而下尺寸递增（即顶部最小、底部最大）。任务是把这 n 个圆盘整体搬运到柱子 C，并保持原有顺序。移动过程必须遵循三条规则：

1. 每次只能从某根柱子的顶部取下一个圆盘，放到另一根柱子的顶部；
2. 一次只能移动一个圆盘；
3. 任意时刻，小圆盘必须位于大圆盘之上（即柱子上的圆盘自顶向下必须严格递增）。

文中把“规模为 i 的汉诺塔问题”记作 f(i)，例如 f(3) 表示把 3 个圆盘从 A 移到 C。仓库中对应源码与文档位于：

• 文档：en/docs/chapter_divide_and_conquer/hanota_problem.md（中文版见 docs/chapter_divide_and_conquer/hanota_problem.md）；
• 图集：hanota_problem.assets 内含基础情形、逐步移动与递归树等全部插图。

先看基础情形：f(1) 与 f(2)

情形 f(1)：当 A 上只有一个圆盘时，规则完全不受限，直接把它从 A 移到 C 即完成，仅需 1 次移动。这是整个递归的最小单元（base case）。

情形 f(2)：当有两个圆盘时，问题开始变得有“讲究”。由于小盘必须始终压在大盘之上，我们必须借用 B 作为中转，否则无法把大盘从 A 底下抽出来。标准三步走为：

1. 先把小盘从 A 移到 B；
2. 再把大盘从 A 移到 C；
3. 最后把小盘从 B 移到 C。

这一过程可概括为：借助 B 把两个圆盘从 A 移到 C。其中 C 被称为“目标柱”（target），B 被称为“缓冲柱”（buffer）。缓冲柱的角色只存在于某一层调用的局部视角中——在下一层调用里，角色会随参数轮换，这正是后续代码注释易读性的关键。

从 f(3) 中悟出分治：把顶部的 n−1 个圆盘“看成一个整体”

对于 f(3)，直接手工推演会变得繁琐，但既然 f(1)、f(2) 的解法已知，就可以用分治的眼光来审视：把 A 顶部的两个圆盘“打包成整体”处理，执行如下三个步骤：

1. 以 B 为目标柱、C 为缓冲柱，把两个圆盘从 A 移到 B（这本身就是一个 f(2)）；
2. 把 A 上剩余的最大圆盘直接移到 C（一个 f(1)）；
3. 以 C 为目标柱、A 为缓冲柱，把两个圆盘从 B 移到 C（又一个 f(2)）。

由此，f(3) 被拆解为两个 f(2) 子问题与一个 f(1) 子问题。这三个子问题按顺序求解、彼此独立、解可合并，恰好印证了分治思想中“子问题相互独立、可分别求解后合并”的核心性质。这与归并排序“等分后归并”的划分方式不同——它是非均匀划分的典型分治实例。

通用分治策略：f(n) → 2 × f(n−1) + f(1)

把 f(3) 的经验推广到任意规模 n，可归纳出如下三步分治策略：

1. 借助 C，把 A 顶部 n−1 个圆盘移到 B（子问题 f(n−1)）；
2. 把 A 剩余的那 1 个圆盘直接移到 C（子问题 f(1)）；
3. 借助 A，把 B 上的 n−1 个圆盘移到 C（子问题 f(n−1)）。

对两个 f(n−1) 子问题，用同样的方式继续递归分解，直到触底到已知的最小问题 f(1)——它只需 1 次移动。也就是说，整个问题的合法性由递归不变量保证：在任一时刻，源柱上的盘恰好都大于缓冲柱/目标柱上“等待叠放”的盘，因此任何一次 move 都不会违反“小盘在上”的规则。

代码实现：dfs 三参轮换的精髓

仓库中用统一的递归骨架实现了该算法。核心函数为 dfs(i, src, buf, tar)，语义是：借助缓冲柱 buf，把源柱 src 顶部的 i 个圆盘搬到目标柱 tar。以 Python 实现（codes/python/chapter_divide_and_conquer/hanota.py）为例：

def move(src: list[int], tar: list[int]):
    """移动一个圆盘"""
    # 从 src 顶部拿出一个圆盘
    pan = src.pop()
    # 将圆盘放入 tar 顶部
    tar.append(pan)

def dfs(i: int, src: list[int], buf: list[int], tar: list[int]):
    """求解汉诺塔问题 f(i)"""
    # 若 src 只剩下一个圆盘，则直接将其移到 tar
    if i == 1:
        move(src, tar)
        return
    # 子问题 f(i-1)：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
    dfs(i - 1, src, tar, buf)
    # 子问题 f(1)：将 src 剩余一个圆盘移到 tar
    move(src, tar)
    # 子问题 f(i-1)：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
    dfs(i - 1, buf, src, tar)

def solve_hanota(A: list[int], B: list[int], C: list[int]):
    """求解汉诺塔问题"""
    n = len(A)
    # 将 A 顶部 n 个圆盘借助 B 移到 C
    dfs(n, A, B, C)

理解这段代码的关键在于观察每次递归调用时参数的错位轮换：

• 第一步 dfs(i - 1, src, tar, buf)：源柱仍是 src，但缓冲柱变成 tar、目标柱变成 buf——即“借助 C，把 A 的 n−1 盘搬到 B”；
• 第二步 move(src, tar)：对应“把最大盘从 A 直移到 C”；
• 第三步 dfs(i - 1, buf, src, tar)：源柱变为 buf、缓冲柱变为 src——即“借助 A，把 B 的 n−1 盘搬到 C”。

三个实参在调用间循环换位，而在顶层入口 solve_hanota 处传入的则是初始角色（A 为源、B 为缓冲、C 为目标）。驱动代码把每根柱子建模成一个“尾部为柱顶”的列表，例如 A = [5, 4, 3, 2, 1] 表示柱顶是 1、柱底是 5，pop()/append() 天然对应“取顶盘/放顶盘”。

同一逻辑在仓库内几乎每个语言目录下都有实现，且函数签名与递归骨架完全对齐，便于横向对照：

语言	文件
Python	codes/python/chapter_divide_and_conquer/hanota.py
Java	codes/java/chapter_divide_and_conquer/hanota.java
C++	codes/cpp/chapter_divide_and_conquer/hanota.cpp
C	codes/c/chapter_divide_and_conquer/hanota.c
Go	codes/go/chapter_divide_and_conquer/hanota.go

不同语言在数据结构上略有取舍，但算法核心完全一致：例如 C 语言版（hanota.c）用定长数组加 *Size 指针模拟栈顶；Go 版（hanota.go）用标准库 container/list，以链表尾部充当柱顶，src.Back() 取出顶部元素后再 Remove。这说明汉诺塔的递归骨架不依赖任何特定容器，只要容器支持“取顶部 + 放顶部”两种操作即可落地。

运行与验证

驱动代码会在搬移前打印 A/B/C 的初始状态，调用 solve_hanota 后再打印最终状态，用于目视验证“全部圆盘已按原顺序到达 C”。Python 版可直接运行验证：

cd codes/python/chapter_divide_and_conquer
python3 hanota.py

Go 版还额外提供了单元测试入口（codes/go/chapter_divide_and_conquer/hanota_test.go），在 TestHanota 中构造 A = [5,4,3,2,1]、B/C 为空，调用 solveHanota 后打印三根柱子的最终内容，与 Python 驱动代码的验证思路如出一辙。

复杂度分析：时间 O(2^n)、空间 O(n)

汉诺塔的递归调用会展开成一棵高度为 n 的递归树，根节点是 f(n)，每个节点对应一次 dfs() 调用：根节点的两个 f(n−1) 子节点各带一个 f(1) 叶节点，逐层分裂直到全部触底到 f(1)。

• 时间复杂度 O(2^n)：设移动次数为 T(n)，由代码结构可得递推式 T(n) = 2·T(n−1) + 1，且 T(1) = 1。展开后 T(n) = 2^n − 1，即每次移动对应一次基本操作，故总时间为 O(2^n)。以文中图例规模验证：f(1) 需 1 次、f(2) 需 3 次、f(3) 需 7 次，恰好符合 2^n − 1。
• 空间复杂度 O(n)：递归树高度为 n，系统调用栈最深为 n 层，再加上若干常数级的容器开销，故空间为 O(n)。

从工程角度，这也解释了汉诺塔“数学优雅但工程昂贵”的特性——n 每增加 1，移动次数就翻倍再加 1，因此教科书与源码中的示例普遍只演示 n 为个位数的规模。

延伸：关于“世界末日”的古老传说

章节末尾引用了汉诺塔的著名传说：古印度一座寺庙里，僧侣们不停地移动 64 片金盘，相信当最后一片金盘被正确放置时世界便会终结。基于上面的 2^n − 1 结论可以做一道简单的算术：即便僧侣每秒钟移动一片，搬完 64 片也需要 2^64 ≈ 1.84×10^19 秒，约 5850 亿年，远超目前对宇宙年龄的估计。因此若传说属实，我们也无需担心世界末日——这一趣闻恰好让抽象的指数复杂度变得可感可知。

本章回顾与进一步阅读

本章在仓库中的配套资源非常完整，建议按如下顺序深入：

• 基础理论：先读同章 divide_and_conquer.md，理解分治三步骤“分解—求解—合并”的一般框架；
• 另外两个分治案例：二分查找（递归） 展示均匀划分，构建二叉树问题 展示如何用递归建树，与汉诺塔并置可形成对比；
• 巩固练习：章节习题 与 章节小结；
• 可视化复盘：可配合 PythonTutor 版汉诺塔步骤笔记 逐帧观察圆盘与参数的移动轨迹，这是理解三柱角色轮换最直观的方式。

一句话总结：汉诺塔用一个极简的递归函数，把“n 个盘”压缩成“n−1 个盘 + 1 个盘”，通过 dfs(i, src, buf, tar) 中三个参数的循环换位实现了分治、递归与规则约束的完美统一；读懂它，你就同时读懂了递归基、子问题分解和指数复杂度三个核心概念。