我第一次系统地啃汉诺塔是在准备算法面试的那段时间。网上能找到的讲解不少但要么只有几行递归代码看完“感觉懂了”换个数一跑又懵了要么推导过程跳步太多不知道那个2^n - 1到底怎么蹦出来的。“汉诺塔”这三个字说起来简单三根柱子一堆盘子一次搬一个大不压小。但真正想把它讲透——从图解演算、数学推导再到Python实现——你会发现它其实串起了递归、分治、递推、二进制好几块硬核内容而且彼此之间环环相扣。这篇内容就是想把这根链条完整走一遍适合正在学算法的学生、准备面试的开发者以及任何想彻底搞懂递归的人。我会用三盘、四盘的具体移动过程做图解演算再用数列推导出最少步数最后给出可直接运行的Python实现。1. 问题的规则与核心思路先看懂“它在做什么”很多教程一上来就甩递归代码这是个很大的误区。汉诺塔看着短但如果你不知道每一步在干什么递归就只是个背诵下来的“魔法”。先把问题本身拆干净。1.1 规则还原三条铁律汉诺塔的设定我这里再确认一遍有三根柱子通常叫A源柱、B辅助柱、C目标柱。初始时n个大小不同的盘子全部套在A柱上从上到下依次变大。每次只能移动一个盘子且只能取某根柱子最顶上的那个盘子。任何时刻大盘子不能压在小盘子上面也就是说每根柱子上的盘子从下往上必须是从大到小。目标把A柱上全部n个盘子原样搬到C柱可以借助B柱。换成人话三根柱子A是仓库C是目的地B是临时中转区。你不是直接把整摞盘子端过去而是一次只能搬一块还得保证任何时候下面都比上面大。这个规则最坑的地方在于一旦n稍大一点比如6个盘子就需要63次移动8个盘子需要255次。人类靠“灵机一动”去试基本试不出最优解。所以必须找到一种“机械式”的套路让每一步都有章可循。1.2 关键观察n和n-1的关系这是整个汉诺塔问题的“题眼”。先玩一个最小规模只有1个盘子。那太简单了直接把A上的盘子挪到C完事。那如果有2个盘子呢手动试一下就知道了小盘子 A → B大盘子 A → C小盘子 B → C一共3步。注意一个结构第2步其实隐含了一个动作——为了能把最大的盘子从A挪到C必须先把上面那个小盘子“清场”到B。这个“清场”动作本质上就是“把1个盘子从A移到B”。如果有3个盘子呢我们脑子先别想着具体怎么动而是先做一个“抽象”思考目标是把最底下那个最大的盘子从A挪到C。但它在最底下上面还压着两个盘子所以必须先想办法把上面两个盘子整体挪到B。等最大盘子到了C再把B上的两个盘子整体挪到C。看到了吗“把上面两个盘子挪到B”这一步本身就是一个规模为2的汉诺塔问题只不过目标柱从C换成了B“再把两个盘子从B挪到C”又是一个规模为2的汉诺塔问题只不过源柱换成了B。这个过程完全不需要知道“两个盘子具体怎么挪”只需要知道“反正有办法能挪过去”。于是n个盘子的任务就被拆成了解决n-1个盘子的子问题A → B借助C移动第n个大盘子A → C解决n-1个盘子的子问题B → C借助A这就是递归的核心思想不解决全部问题只解决一个“降级”后的小一点问题并相信小问题可以同样方式再降级直到降成1个盘子的最简情况。注意这一步理解到位了后面递归代码就是把这个“三步拆分”直接翻译成函数调用。这也是为什么汉诺塔被当作递归教学第一题因为它示范的“自我包含”递归写起来几乎不需要思考。2. 图解演算三盘实例一步一步走给你看光说抽象步骤不够我把3个盘子的完整过程全部列出来盘子的编号约定为1号最小2号中间3号最大。初始状态是A柱从上到下依次为3、2、1这里描述的是从柱底往上数的存储顺序实际操作时取顶端。2.1 三盘全程推演7步我用“A→C”表示把一个盘子从A柱移到C柱。过程如下步数动作执行后A柱执行后B柱执行后C柱这一步在做什么初始-3,2,1空空全部盘子都在A11号 A→C3,2空1腾出B不对这里是为了给2号开路把1号挪到C22号 A→B31空2号从A挪到B1号暂时“占”在C31号 C→B32,1空把1号叠到2号上B柱现在是一摞完整的“2,1”43号 A→C空2,13最大的3号终于可以动了挪到目标柱C51号 B→A123开始把B上的小规模汉诺塔转移过去1号先挪到A62号 B→C1空3,22号挪到C压在3号上面71号 A→C空空3,2,1最后1号归位完成这7步如果你拿着笔和纸画一下会看到一个非常漂亮的对称结构第1~3步其实就是“把2个盘子从A挪到B”这一整体目标借助C。第4步是移动最大的3号。第5~7步是“把2个盘子从B挪到C”这一整体目标借助A。完全印证了前面的三步拆分法。更重要的是你会注意到7步 3步 1步 3步。而移动2个盘子要3步所以T(3) 2*T(2) 1这里的“1”就是移动3号的那一步。2.2 四盘推演的关键节点中间态长什么样4个盘子全程要15步我不逐条列出了但把几个关键节点列出来你能更直观感受递归的“分层”前7步把上面3个盘子从A整体挪到B借助C。此时最大4号还在AB柱从上到下是3、2、1注意顺序C柱为空。第8步4号从A挪到C。此刻最大的盘子已经到位之后它再也不用动了。后7步把B上3个盘子整体挪到C借助A。完成。你会发现整个求解过程像不像“先清空、再移底、后还原”所有步骤都围绕最大盘子的移动展开。第4号盘子只需移动1次3号盘子移动2次2号盘子移动4次1号盘子移动8次。移动次数恰好是2的幂。2.3 图解演算的实操技巧我自己在纸上演算时有一个特别好用的方法把三根柱子画成三个圈用数字表示盘子在柱子上的自底向上顺序。比如初始A柱写“4 3 2 1”B柱空C柱空。每走一步就用橡皮擦掉旧顺序、写上新顺序。走几个来回之后你会自然形成一种“手感”当你在挪一个k号盘子时k号以上的所有盘子永远保持着“从大到小”的相对顺序这些盘子的移动规律是完全确定的。建议自己把4盘、5盘各推演一遍。这个过程的收益不在于“记住15步/31步”而在于亲身体会递归分层。很多同学总问“递归到底怎么递归的”答案不在脑子里想而是在纸上画出来。画三遍递归就“通”了。3. 数学推导最少步数为什么是 2^n - 1看完图解我们已经从直觉上感觉到n个盘子的步数像是“2的幂减1”。现在就来严格推导用的是高中数学就够用的一阶递推数列。3.1 递推关系的建立设T(n)为把n个盘子从一根柱子移到另一根柱子所需的最少移动次数。按照前面三步拆分的思路先把上面n-1个盘子从源柱挪到辅助柱需要T(n-1)步。把最底下的第n个盘子从源柱挪到目标柱需要1步。再把辅助柱上的n-1个盘子挪到目标柱又需要T(n-1)步。所以得到递推式T(n) 2 * T(n-1) 1边界条件T(1) 1一个盘子直接挪。这个式子非常干净也很好理解。它说明每一步解决方向的“成本”都由两个更小的子问题组成。3.2 递推式的完整求解有了T(n) 2*T(n-1) 1怎么得到通项公式有三种常见解法。方法一反复展开迭代法把递推式不断代入T(n) 2*T(n-1) 1 2*[2*T(n-2) 1] 1 4*T(n-2) 2 1 8*T(n-3) 4 2 1 ... 2^(n-1) * T(1) 2^(n-2) ... 2 1代入T(1)1得到T(n) 2^(n-1) 2^(n-2) ... 2 1这是一个等比数列公比为2项数恰好n项。用等比数列求和公式T(n) 2^n - 1方法二构造等比数列这是比较优雅的代数技巧。对递推式两边同时加1T(n) 1 2*T(n-1) 2 2*(T(n-1) 1)令S(n) T(n) 1则S(n) 2*S(n-1)且S(1) T(1)1 2。一个首项为2、公比为2的等比数列通项S(n) 2^n。所以T(n) S(n) - 1 2^n - 1。这个构造方法一气呵成也是最推荐在面试现场使用的因为它书写量少不易出错。方法三数学归纳法证明如果已知结论是T(n) 2^n - 1可以直接验证基础步T(1) 2^1 - 1 1成立。归纳步假设T(n-1) 2^(n-1) - 1则T(n) 2*T(n-1) 1 2*(2^(n-1) - 1) 1 2^n - 2 1 2^n - 1成立。归纳法适合用来“验证”答案而不太适合“发现”答案。实际做题时先用展开法或构造法算出结果再用归纳法检查即可。3.3 二进制视角步数与位运算的巧合推导出T(n)2^n-1之后有个特别好玩的延伸。你看二进制下2^n - 1的二进制表示是n个连续的1比如2^3 - 1 7二进制就是111。这个事实对应一个很有意思的现象把汉诺塔的n个盘子各看成一个二进制位从0开始每移动一次就将整个二进制数加1。某个盘子移动的时机恰好就是对应位的“翻转”时机。最小的1号盘子每两步动一次2号盘子每四步动一次以此类推。我第一次发现这个关联时挺惊喜的。递归的“分层推进”和二进制“进位”本质上是同一种节奏。以后你写汉诺塔的迭代算法非递归版本其实就是在模拟这个二进制计数器。4. Python实现递归版、迭代版与可视化验证数学推导完了代码就水到渠成。先写最经典的递归版再写一个迭代版然后给一个可视化验证方法。4.1 递归实现与逐行解析直接上代码def hanoi(n, source, target, auxiliary): 将 n 个盘子从 source 柱移到 target 柱借助 auxiliary 柱 :param n: 盘子数量 :param source: 源柱名称 :param target: 目标柱名称 :param auxiliary: 辅助柱名称 if n 1: print(f将 1 号盘子从 {source} 移到 {target}) return # 第一步把上面 n-1 个盘子从 source 移到 auxiliary hanoi(n - 1, source, auxiliary, target) # 第二步把第 n 个盘子从 source 移到 target print(f将 {n} 号盘子从 {source} 移到 {target}) # 第三步把 auxiliary 上的 n-1 个盘子移到 target hanoi(n - 1, auxiliary, target, source)调用方式hanoi(3, A, C, B)运行结果将 1 号盘子从 A 移到 C 将 2 号盘子从 A 移到 B 将 1 号盘子从 C 移到 B 将 3 号盘子从 A 移到 C 将 1 号盘子从 B 移到 A 将 2 号盘子从 B 移到 C 将 1 号盘子从 A 移到 C和前面图解的7步完全一致。核心是理解参数的作用hanoi(n, source, target, auxiliary)里的三个柱子名称在每次递归调用时会发生角色转换。第一次递归sourceA、targetB、auxiliaryC因为这一步的“目标”变成了B“第一步里的辅助柱”变成了C。很多初学者在这卡住就是因为没有意识到这三个参数在每一层递归里代表的是变化的角色而不是固定的“A柱B柱C柱”。4.2 递归深度与调用栈Python默认递归深度是1000层左右。汉诺塔的递归深度是n层。所以n999以上就会报RecursionError。一般演示用n不超过10就够了因为移动次数随n指数暴涨。如果你需要跑大n可以手动提高递归限制import sys sys.setrecursionlimit(2000)但这只是绕开了限制系统栈依然可能溢出。实践中汉诺塔更多是教学场景完全没有必要追求超大n。4.3 迭代实现二进制解法递归的瓶颈是栈深度想完全跳过递归可以基于二进制计数写迭代版本。思路是n个盘子的汉诺塔一共要移动2^n - 1步把步数k从1遍历到2^n - 1每次根据k的二进制最低位1的位置决定移动哪个盘子。具体规则如果n是偶数最小盘子的循环方向是 A→B→C→A。如果n是奇数最小盘子的循环方向是 A→C→B→A。除最小盘子外另两个合法柱子之间只能有一种合法移动把较小的那个盘子放到较大的上面。以下是迭代版实现def hanoi_iterative(n, source_nameA, target_nameC, auxiliary_nameB): # 用列表表示柱子列表尾部作为栈顶 rods { source_name: list(range(n, 0, -1)), # 初始自底向上 n, n-1, ..., 1 auxiliary_name: [], target_name: [], } total_moves (1 n) - 1 # 2^n - 1 if n % 2 0: clockwise [source_name, auxiliary_name, target_name] else: clockwise [source_name, target_name, auxiliary_name] for step in range(1, total_moves 1): # 判断这一步移动哪个盘子根据 step 二进制最低位 1 的位置 disk ((step -step).bit_length()) # 最低位1的位置即盘子编号 if disk 1: # 最小盘顺时针移动到下一根柱子 current next(idx for idx, rod in enumerate(clockwise) if rods[rod]) nxt (current 1) % 3 src clockwise[current] dst clockwise[nxt] if rods[dst] and rods[dst][-1] rods[src][-1]: src, dst dst, src # 如果目标柱顶更小反向移动 else: # 非最小盘找出它当前所在柱子和另一个非空柱子的栈顶做合法移动 src dst None for rod in rods: if rods[rod] and rods[rod][-1] disk: src rod break for rod in rods: if rod ! src and (not rods[rod] or rods[rod][-1] disk): dst rod break if dst is None: for rod in rods: if rod ! src and rods[rod]: dst rod break # 执行移动 moved rods[src].pop() rods[dst].append(moved) print(f将 {moved} 号盘子从 {src} 移到 {dst})这段代码比递归版复杂但它揭示了一个事实汉诺塔本质上是一个确定性的顺序问题并不依赖“回溯”。递归是把它“想”清楚迭代是把它“走”明白。面试时我通常先写递归版再主动提一句“还可以用二进制迭代实现”会是不错的加分项。4.4 用可视化快速验证教学和调试时我想看到每步之后三根柱子的实际状态而不是只有一行打印。可以这样写def hanoi_with_state(n, source, target, auxiliary, rods): if n 1: rods[target].append(rods[source].pop()) print(f移动 1 号盘子{source} - {target}) print(f当前状态A{rods[A][::-1]}, B{rods[B][::-1]}, C{rods[C][::-1]}) return hanoi_with_state(n - 1, source, auxiliary, target, rods) rods[target].append(rods[source].pop()) print(f移动 {n} 号盘子{source} - {target}) print(f当前状态A{rods[A][::-1]}, B{rods[B][::-1]}, C{rods[C][::-1]}) hanoi_with_state(n - 1, auxiliary, target, source, rods) def run_visual(n): rods {A: list(range(n, 0, -1)), B: [], C: []} print(f初始状态A{rods[A][::-1]}, B{rods[B][::-1]}, C{rods[C][::-1]}) hanoi_with_state(n, A, C, B, rods)注意我在打印状态时做了[::-1]因为rod内部存的是自底向上的顺序展示时反转为自顶向下更直观。这样每跑一步都能对照前面的图解。5. 常见问题与排查把递归的“坑”填平很多人在自己写汉诺塔时会遇到各种问题。这里把高频问题集中整理一下并给出排查思路。5.1 运行结果“多一步”或“少一步”最常见的是盘子编号不对或者移动方向和预期不一致。排查方法画出n3的期望7步表和程序输出对照。检查递归调用时三个参数顺序特别是第一个递归调用是不是hanoi(n-1, source, auxiliary, target)第三个是不是hanoi(n-1, auxiliary, target, source)。确认“第二步”打印的是“第n号盘子”而不是“第1号盘子”。很多人会写反辅助柱和目标柱。一个简单的记忆口诀第一步的目的地是辅助柱第三步的出发地是辅助柱。也就是说“辅助柱用两次、目标柱当一次主角”。5.2RecursionError递归太深n超过默认递归限制报错信息一般是RecursionError: maximum recursion depth exceeded in comparison解决方式前面说过了。但更值得说明的是千万不要为了“跑通大数”而盲目调高递归限制因为Python的调用栈本身有硬件和操作系统层面的约束。汉诺塔的移动次数是指数级增长就算递归不报错打印输出也会让你等到天荒地老。真想验证数学结论直接算2**n - 1就行。5.3 打印和返回值的混淆有些人会写一个“返回移动次数”的递归函数却在里面用了print导致结果混乱。正确的写法是把“返回次数”和“打印步骤”分开def hanoi_count(n): if n 1: return 1 return 2 * hanoi_count(n - 1) 1这个函数不打印具体步骤只返回步数。而你如果想要步骤再单独写带print的版本。职责分离在递归函数里同样重要。5.4 参数命名带来的理解障碍我看到很多初学者用a, b, c作为参数名然后越看越糊涂。因为汉诺塔的精髓是“角色的实时变化”建议命名用source、target、auxiliary一眼就能看出这层递归里谁在扮演什么角色。参数语义化比代码行数更重要。5.5 大整数与性能2**64 - 1在Python里不会溢出Python的整数是任意精度的。所以理论上你算几千个盘子的总步数也没问题。但你不可能真的去模拟移动几千个盘子的过程那需要宇宙级别的步数。做题时记住代码能跑通的是“规则”数字上验证的是“公式”这二者要分开看待。6. 汉诺塔思想的延伸它不止是一道递归题搞清楚汉诺塔以后你会突然发现很多算法的骨架跟它是同一个思路。6.1 分治思想的典型缩影“分而治之”是计算机算法里的核心思想汉诺塔就是最直观的例子。它的三步走是“拆小问题、解决子问题、合并子问题”。这个模式反复出现在归并排序、快速排序、二分搜索中。区别在于后者的子问题拆分与合并是有数据交换的而汉诺塔的“合并”本身就体现在子问题的串行完成上。6.2 状态空间的启发汉诺塔的所有合法状态可以构成一个图n个盘子的合法状态数正好是3^n其实不是是3^n个“理论上可放置”但其中只有部分合法。全部合法状态恰好是一个“汉诺塔图”从初始状态到目标状态的最短路径长度就是2^n - 1。这在算法竞赛里偶尔会变着花样考比如“给出当前状态判断是否合法”“给定状态求最短步数”之类。6.3 变体问题的一瞥四柱汉诺塔是一个经典变体多了一根辅助柱后最少步数不再是2^n - 1而需要用“Frame-Stewart算法”递推形式是T(n) min(2*T(k) T(n-k))的优化问题。双色汉诺塔则限制颜色不能混杂。这些变体在面试或竞赛中偶有出现但核心一定还是你从基础汉诺塔中建立的“状态转移”和“递归拆解”思维。6.4 工程上的隐喻汉诺塔还经常被用来解释“迁移”问题把某个系统从一个基础设施迁移到另一个中间必须经过一个临时的过渡设施并且要保证任意时刻“主流程不混乱”。你在做数据迁移、服务切换时本质上就是在设计一套“先小批迁移、再切换主体、再迁移剩余”的分步方案。这也是为什么很多系统架构师喜欢拿汉诺塔举例它不仅是算法题还是工程策略的简化模型。我个人在实际操作中最受益的不是背下来递归代码而是老老实实画过一次4盘推演。画完之后“递归到底是怎么一层层展开的、每层的参数为什么互换”一下子就有了肌肉记忆。后来写归并排序、树的遍历我再也没怕过递归。如果你刚开始学建议按这个顺序走先亲手推演4盘并记录步骤再对照递推式自己解一遍最后让Python代码帮你验证。三件事做完汉诺塔这道题就真正归你了。之后如果遇到四柱变体或者其他任何递归题回来再看看这篇的思路你会有新的体会。