★ FEATURED ARTICLE 最近和一个朋友聊起递归他卡在汉诺塔上很久总觉得代码能看懂但让我自己想就写不出来。这让我想起自己当年学这块的经历翻了不少资料大部分要么只贴一段代码要么上来就抛一个数学归纳法的结论很少有人把怎么从问题推导出解法这个过程讲透。所以这篇文章我打算完整走一遍汉诺塔的图解演算、公式推导和Python实现。内容主要围绕三件事一为什么汉诺塔的递归结构长这样每一步到底在干什么二移动次数2^n-1是怎么从递推式推出来的三递归版本、非递归版本各有什么优缺点实际写代码时需要注意哪些坑。1. 汉诺塔的问题描述与递归结构为什么三根柱子天然适合递归汉诺塔的规则一句话就能说清有三根柱子A、B、CA柱上有n个从大到小叠放的圆盘目标是把所有圆盘移到C柱过程中始终保持大盘不能压在小盘上而且每次只能移动最顶上的一个盘子。这个规则看起来简单但n稍大一点手动推步骤就会懵。我最初尝试手推4层、5层的时候经常移到一半就忘记哪个盘该去哪了。后来我意识到问题不在于记忆力而在于没有找到问题的结构。汉诺塔的结构恰恰最适合用递归来描述。原因是不管n有多大最底下的第n号盘永远只可能移动一次而且在它移动之前上面n-1个盘必须先全部离开A柱、并且不能挡住它去C柱的路。换句话说上面n-1个盘必须整体搬到B柱上。这个整体搬走的子问题和整个问题完全同构——只是盘子数量少了1目标柱从C变成了B。所以标准递归思路就出来了把n个盘子从A移到C等价于——先把n-1个盘子从A移到B借助C再把第n号盘从A移到C最后把n-1个盘子从B移到C借助A。这里借助的柱子是空闲的那根。写成Python就是def hanoi(n, source, target, auxiliary): if n 1: print(fMove disk 1 from {source} to {target}) return hanoi(n - 1, source, auxiliary, target) print(fMove disk {n} from {source} to {target}) hanoi(n - 1, auxiliary, target, source)我最初写这段代码时总是把参数顺序搞混。后来总结了一个好记的口诀每次递归调用都是从当前源柱移到当前目标柱而剩下的那根柱子就是辅助柱。第一次递归想做的事情是把上面的盘子全部挪到辅助柱去所以这时的辅助柱变成了下一次递归的目标柱第二次递归想做的事情是把辅助柱上的盘子挪到最终目标柱所以这时的辅助柱变成了下一次递归的源柱。这样理解之后参数传递就不再是死记硬背而是每次都在回答同一个问题这一步我要把哪几个盘子从哪根柱子搬到哪根柱子借助哪根柱子2. 图解演算用递归树手动推演3层汉诺塔的7步移动纸上推演汉诺塔最直观的方法是画递归树而不是一直盯着柱子发呆。以3层为例目标是从A移到C辅助柱是B。整个调用过程可以画成下面这棵二叉树hanoi(3, A, C, B) / | \ hanoi(2, A, B, C) move 3:A-C hanoi(2, B, C, A) / | \ / | \ hanoi(1,A,C,B) move2:A-B hanoi(1,C,B,A) hanoi(1,B,A,C) move2:B-C hanoi(1,A,C,B)把每个叶子节点的移动动作按从左到右的顺序列出来就是盘1A → C盘2A → B盘1C → B盘3A → C盘1B → A盘2B → C盘1A → C一共7步。很多人在第5步会卡一下为什么盘1要从B移到A而不是直接移到C原因是当执行到后半段时子问题是把2个盘子从B移到C借助A所以B上的小盘必须先挪到A把B柱腾出来给盘2移动。理解了这个整个递归逻辑就通了。我自己做图解时喜欢把柱子的参数变化单独列一行。每一层递归from、to、aux到底对应哪根柱子写下来之后会发现它们总是在三根柱子之间轮转。这也就是为什么很多汉诺塔动画里盘子的移动方向看起来总是循环的。3. 数学推导移动次数为什么是2^n-1汉诺塔另一个经典结论是n个盘子最少需要2^n-1步。这个结论可以用递推公式严格推导出来。设f(n)表示把n个盘子从一根柱子移到另一根柱子所需的最少步数。根据前面说的递归结构移动n个盘子需要先把n-1个盘子移到辅助柱这是f(n-1)步再把最大的盘子移到目标柱这是1步再把n-1个盘子从辅助柱移到目标柱这又是f(n-1)步。所以f(n) 2 * f(n-1) 1初始条件f(1) 1。从递推式可以推出通项公式f(n) 1 2 * (f(n-1) 1)令g(n) f(n) 1则g(n) 2 * g(n-1)且g(1) 2。所以g(n) 2^n于是f(n) 2^n - 1。还有一个更直观的归纳版本假设f(n-1) 2^(n-1) - 1那么f(n) 2*(2^(n-1)-1)1 2^n-1。从f(1)1出发一步步推到f(2)3f(3)7f(4)15很快就能发现规律。很多初学者看到2^n-1这个结果会疑惑为什么不是2^(n-1)之类原因在于每一层递归都产生了两个规模为n-1的子问题所以总量是指数增长的。这正好也体现了汉诺塔问题的时间复杂度是O(2^n)——如果你想用程序输出64层的移动步骤哪怕每秒输出一万条也需要几万年才能跑完。这个指数爆炸的直觉比背公式重要得多。4. Python实现详解递归版本、动画版本与测试验证代码实现方面不同的写法对应不同的侧重点。我实际写过三种版本分享下各自的适用场景。4.1 标准递归版本就是上面那段代码。它的优点是和数学推导完全对应逻辑清晰最适合用来理解递归。缺点是当n很大时会受Python递归深度限制。Python默认递归深度是1000层所以如果直接跑n1000的汉诺塔会报RecursionError。当然实际工作中很少有人会真的去移动1000个盘子但作为面试题或者算法考察至少要意识到这个限制。4.2 可视化版本turtle实现只打印文字步骤不够直观我后来写了一个turtle版本可以直观看到盘子移动过程。基本思路是创建三根柱子的坐标位置用一个列表表示每根柱子上的盘子堆盘子用矩形块表示在递归函数里当移动盘子时让对应柱子的最顶部盘子弹起来平移到目标柱上方再放下去。turtle实现有个小坑动画速度和递归不同步。如果不做控制整个动画会瞬间完成根本看不清过程。我的做法是在每次盘子移动后加一个小延时time.sleep或使用turtle的ontimer控制刷新节奏。加延时之后7步的移动过程大约需要几秒看起来就舒服多了。4.3 测试验证写完代码后我习惯用几个用例验证正确性当n1时输出Move disk 1 from A to C只有一步当n2时输出3步顺序是盘1 A→B盘2 A→C盘1 B→C当n3时输出7步顺序同前面图解统计输出步数断言等于2^n-1。这样的验证比肉眼检查更可靠。5. 避坑指南理解递归的常见误区与调试建议汉诺塔代码虽然短但初学者最容易在几个地方踩坑。这里把我见到的问题集中梳理一下。误区一试图手动跟踪每一层递归很多初学者拿到递归代码后总想把每一层调用都展开在脑子里像迭代一样从头到尾走一遍。结果递归深度一深立刻混乱。正确做法是相信递归不要展开。你要做的只是确认两件事基线条件是否正确递归调用是否让问题规模变小。只要这两点成立递归一定能结束而且能返回正确结果。汉诺塔的n一直在减小所以递归一定能到达n1的终点。误区二参数顺序混淆hanoi(n-1, source, auxiliary, target)和hanoi(n-1, auxiliary, target, source)这两行很多人写反。一个比较稳妥的办法是不要记顺序而是每次写递归调用前先在心里问这一步的目的是把哪些盘子从哪里搬到哪里然后把三个实参按源、目标、辅助的顺序填进去。误区三认为递归效率低就完全不用递归版本的汉诺塔确实会生成2^n-1次函数调用但每个函数调用都是O(1)操作时间复杂度和非递归版本没有本质区别。递归真正的局限是栈深度而不是时间。所以对于n较小的情况递归实现完全可以接受对于n较大的情况更重要的是思考这个问题本身就要求指数级输出步骤所以任何实现都跑不完而不是单纯责怪递归。调试建议如果代码输出不对我的调试套路是先跑n1再跑n2再跑n3。n2的输出如果有问题几乎一定是递归参数写错了n3的输出如果有问题那很可能是对辅助柱的语义理解有偏差。你还可以在递归函数开头打印当前的source、target、auxiliary观察每层调用的参数变化这样能很快定位到出错的那一层。6. 变体与进阶任意起始状态、多柱汉诺塔与相关算法题汉诺塔不是只有标准三柱、初始全在一根柱这一种玩法。搞懂标准问题后有几个变体值得了解它们对加深理解很有帮助。变体一任意起始状态假设三根柱子上盘子的分布不是全在一根柱上而是随意分布问最少多少步能把全部盘子移到指定目标柱。这个问题不能直接套2^n-1公式但递归思路依然有效。关键想法是从最大的盘子开始看如果最大的盘子已经在目标柱上就不用移动它只需要递归处理剩下的盘子如果不在则需要把比它小的所有盘子先移到第三根柱子再移动大盘再把小盘子移回来。这个思路本质上和标准汉诺塔一致只是不同的初始位置会裁剪掉一部分递归分支。变体二四柱汉诺塔当柱子数增加到4根时经典递归就不适用了因为多出来的辅助柱可以把整体搬迁分成多个批次减少移动。四柱情况下的最优解通常使用Frame-Stewart算法思想是先选择一部分盘子用四柱方式移动到某根空闲柱上剩余大盘子用三柱方式移动到目标柱再把这部分盘子用四柱方式移到目标柱。具体划分的数量需要通过动态规划或枚举来找到最优值。虽然四柱汉诺塔的完整推导比较复杂但理解为什么柱子多了能减少步数这个直觉比记住具体算法更有价值。变体三算法题中的汉诺塔很多算法面试题不会直接问写个汉诺塔而是会换一种包装。比如给定一个数组表示每个盘子的位置判断当前状态是否合法或者给一个移动序列判断是否会违反规则。这类题目本质上都在考察对状态空间的理解。处理时可以用递归或栈模拟重点是明确盘的编号越大越晚移动这一原则。7. 从汉诺塔到工程思维递归在真实场景中的意义很多初学会问学了汉诺塔除了应付作业还有什么用我的答案是它培养的是一种把大问题拆成同构小问题的思维方式。在真实开发里我们经常需要处理类似结构的问题。比如遍历文件夹目录本质上就是处理当前目录下的所有子目录和汉诺塔的递归结构一致再比如解析嵌套的JSON数据每一层的数据结构相同只是深度不同处理方式也可以用递归。汉诺塔把这些场景的通用逻辑抽象到了一个极其精简的例子里。如果让我给学习路径提一个建议我会说先手推3层的7步再写递归代码再用数学归纳法理解2^n-1最后尝试改一改变体。走完这条路递归对你来说就从一个需要背的模板变成了一个可以随手应用的工具。这也是这篇图解和推导的意义所在不是教你背代码而是帮你建立从直觉到代码的完整通路。
阅读完成 · 觉得有帮助？
