汉诺塔递归算法图解教程

说起汉诺塔，很多人第一反应就是“递归经典题”，但真让自己动手画一遍或者写代码，又觉得脑子转不过弯来。我当初学的时候也是，看了好几篇文章，代码抄得下来，但问它为什么这么递归，就卡住了。后来我干脆自己拿纸画盘子移动过程，画着画着就通了。这篇汉诺塔递归算法图解教程，就是想把当时那个“通了”的过程分享给你，咱们不用公式硬背，就靠看图、数步骤，把递归那点事儿彻底搞明白。

汉诺塔到底在玩什么规则？先看最基础的三根柱子

汉诺塔游戏里有三根柱子，左边一根柱子上从下往上叠着大小不一的圆盘，大的在下、小的在上。目标是把所有圆盘挪到右边那根柱子上，中间那根当辅助。规则就两条：一次只能挪一个盘子；大盘子永远不能压在小盘子上面。就这么简单，但盘子一多，人就容易乱。其实你只要记住，每一步都在做“把上面的n-1个盘子挪开，把最大的盘子挪过去，再把n-1个盘子挪上去”这件事，就抓住了汉诺塔递归算法的命根子。

我第一次自己手动挪4个盘子的时候，挪到第10步就忘了自己挪到哪了，后来我干脆在纸上标好每一步的移动方向，比如“1号盘从A到C”，慢慢数着走，才终于没乱。你学的时候也可以这样，别光盯着代码，拿笔在纸上画，或者用现实里的积木模拟一下，印象会深得多。

单盘和双盘：递归的“地基”长什么样？

咱们从最少的盘子开始看。如果你只有1个盘子，那就直接把它从A挪到C，一步搞定，这就是递归的终止条件当n等于1时，不需要再拆了，直接移动。那如果有2个盘子呢？你得先把小盘子从A挪到B，然后把大盘子从A挪到C，最后把小盘子从B挪到C。这个过程里，其实你已经用了一次“借助中间柱子”的技巧，只是盘子少，你感觉不到递归的存在。但汉诺塔递归算法的核心思想就藏在这三步里：先挪上面的n-1个到辅助柱，再挪最底下的到目标柱，最后把那n-1个从辅助柱挪到目标柱。

我当时看代码时总纠结“为什么递归函数要调用自己两次”，后来画了2个盘子的移动顺序，才发现第一次递归调用是“把上面的小盘子挪到B”，第二次递归调用是“把小盘子从B挪回C”，中间那次移动是直接操作最大的盘子。这么一想，递归函数其实就是在重复“把n-1个盘子整体搬个家”的动作，只不过每次搬家的起点和终点在变而已。

三盘以上怎么推？用“整体搬家”的视角看递归

到了3个盘子，你可能觉得复杂了，但我教你一个偷懒的办法：别盯着每个盘子，而是把上面2个盘子看成一个“整体包裹”。第一步，把这个包裹从A挪到B（借助C），第二步，把最大的那个盘子从A挪到C，第三步，再把包裹从B挪到C（借助A）。你看，这就又变成了“三步走”。那包裹怎么挪？其实包裹内部又套着同样的三步，只是规模变成了2个盘子。这就是汉诺塔递归算法的精髓：每一次递归都是在处理“把n-1个盘子从某根柱搬到另一根柱”的小一号问题，直到n等于1，直接搬。

我见过很多人学递归时，总想着把每一层调用都展开成完整的步骤序列，其实没必要。你只需要相信“递归函数能帮我搬好n-1个盘子”，别去管它内部怎么折腾。我第一次写代码时，试着在脑子里模拟3层递归，结果模拟到第二层就乱了，后来我干脆只关注“当前层做了什么”，把底下的交给递归，反而一下子就写对了。你写代码时也一样，先写好终止条件，再写“搬n-1、搬最大、搬n-1”这三行，基本就八九不离十了。

代码怎么写最顺手？附上我调试过的Python版本

光说理论可能还差点意思，我把自己调试过的代码贴出来给你参考。我用的是Python，因为它的缩进结构特别适合表达递归的层级感。函数里我加了打印语句，这样你能直观看到每一步移动的具体操作，对理解汉诺塔递归算法特别有帮助。

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"把盘子1从 {source} 移到 {target}")
        return
    hanoi(n-1, source, auxiliary, target)  # 把上面n-1个盘子从源柱搬到辅助柱
    print(f"把盘子{n}从 {source} 移到 {target}")  # 把最大的盘子从源柱搬到目标柱
    hanoi(n-1, auxiliary, target, source)  # 把n-1个盘子从辅助柱搬到目标柱

# 测试3个盘子的情况
hanoi(3, 'A', 'C', 'B')

你看，代码量很少，但每一行都对应前面说的“三步走”。运行这段代码，它会打印出7步移动指令，正好是3个盘子所需的最少步数（2的3次方减1）。如果你把n改成4，就会打印15步。我当时运行完这个程序，又对照着自己画的步骤图看，发现完全一致，那种“豁然开朗”的感觉特别爽。你也试试，把n改成5、6，看看步数是不是每次翻倍再加一，这样你就更理解为什么汉诺塔递归算法的时间复杂度是O(2^n)了。

不过我得提醒你一句，别拿太大的n去跑，比如n=30，那会打印2的30次方减1条消息，屏幕能刷半天。我以前手贱试过n=20，结果刷了100多万行，电脑都卡了。想验证大数目的步数，可以直接算公式，别真的去打印。

递归调用顺序图解：为什么是“先左后右”的穿插感？

很多人看汉诺塔递归代码时，最晕的就是搞不清递归调用到底先执行哪边。其实你可以把递归调用想象成“任务清单”的嵌套。比如hanoi(3, 'A', 'C', 'B')，它先执行hanoi(2, 'A', 'B', 'C')，这个内部又会先执行hanoi(1, 'A', 'C', 'B')，直接打印“把盘子1从A移到C”，然后返回，再打印“把盘子2从A移到B”，接着执行hanoi(1, 'C', 'B', 'A')……就这样一层一层地套。我建议你画一棵“递归调用树”，把每个节点标记为“从哪移到哪”，这样整个汉诺塔递归算法的执行顺序就一目了然了。

我自己画的时候，发现一个规律：奇数盘的第一步总是把最小的盘子移到目标柱，偶数盘的第一步则是移到辅助柱。这个规律在代码里没体现，但如果你手动模拟，可以帮你快速验证步骤对不对。比如3个盘子，最小盘第一步是A到C，正好符合奇数盘规律。我当时发现这个，兴奋得跟朋友炫耀了半天，虽然可能没什么用，但真的让人对递归的对称美有更深的感觉。

如果你还是觉得抽象，那就找三个不同大小的书本，或者用三个不同颜色的杯子当盘子，在地上标出A、B、C三个位置，亲手按代码的步骤挪一遍。我试过用三本厚薄不同的书模拟，挪到第5步的时候突然就懂了，因为你能亲眼看到“上面两本被当作一个整体移来移去”。这种体验是纯看代码给不了的。

汉诺塔递归的实用价值：不只会解题，还能锻炼抽象思维

有人可能会问，我学汉诺塔递归算法除了应付面试，到底有什么用？我告诉你，用处可大了。递归思想在很多算法里都有体现，比如树的遍历、快速排序、目录文件扫描，甚至解析带括号的数学表达式，背后都是这种“把大问题拆成小问题，自己调用自己”的套路。你学汉诺塔，其实是在练一种“分而治之”的思维模式，等你以后遇到更复杂的问题，会更容易想到递归解法。

我当初学数据结构和算法时，很多递归题目都看不懂，但自从把汉诺塔彻底搞明白后，再看二叉树的前中后序遍历，发现就是一个简单的递归模板，心里踏实多了。所以你千万别觉得这只是个游戏题，它其实是帮你打开递归思维的一把钥匙。建议你学完这个教程后，自己试着不用辅助打印，只写一个移动步数的函数，再试试写非递归版本（用栈模拟），那样你对递归的理解会更上一层楼。

好了，这篇汉诺塔递归算法图解教程就说到这。你只要跟着我上面的思路，先手动画一画2个盘、3个盘的移动图，再对照代码跑一遍，最后自己试着改改参数，我相信你很快就能彻底掌握。如果哪一步卡住了，就回头看看我提到的“整体搬家”那一段，把大问题拆小，一切就都顺了。希望我的这些踩坑经验能帮到你，祝你早日与递归“和解”！