1. 先把三根柱子的规则拆干净汉诺塔也有人写成“汉罗塔”这道题我最早是在一本算法入门书里看到的当时觉得规则简单得有点幼稚三根柱子一堆大小不一的圆盘从 A 搬到 C一次搬一个大盘不能压小盘。三行递归代码写完跑 n3 输出了 7 行看着挺对就翻篇了。真正让我重新回来啃它的是后来在带新人的时候被反问了一句“为什么你的递归里两次调用要交换参数如果我把参数顺序写反n1 和 n2 居然还能跑出结果这怎么回事”那一刻我才意识到汉诺塔这道题的价值根本不在“写出代码”而在于它把递归最容易被糊弄过去的那部分——状态的角色转移——赤裸裸地摆在你面前。它是递归思想的照妖镜你觉得你懂了其实你只是背下来了。这篇内容我想写给两类人一类是刚接触递归想真正搞明白“为什么这样拆”的初学者另一类是写过很多遍汉诺塔但从来没深究过复杂度、迭代解法、变形题的开发者。下面这些都是我在实际写代码、带人、做练习时踩出来的理解不是课本上的标准答案。1.1 那条“大盘不能压小盘”到底约束了什么很多人把这条规则当成一个“限制”其实它是一条结构性约束它直接决定了每一步可选的移动数量极少。你可以在纸上试一下n3 时除了第一步有 3 种选择之后每一步真正合法的移动往往只有 1 到 2 种。这不是巧合而是因为每条柱子在任意时刻都是一个“从大到小”的有序序列任何时刻你只能拿走最上面那个。把这个观察说清楚一点柱子不是普通的容器它是栈。你只能从顶部取只能往顶部放而且放入的元素必须比当前顶部更小。这个“后进先出 单调递减”的组合正好是递归和显式栈能够相互模拟的根本原因。后面讲迭代解法时你会发现代码能这么写全靠这一点。理解了这一层你就能回答一个常见疑问为什么汉诺塔不能用“贪心”蒙混过去因为合法的下一步往往有多个选择而且选错一步并不会立刻违规而是会在几步之后把你堵死。这种“局部合法、全局死路”的结构恰恰是深度优先搜索和递归要处理的东西。1.2 n3 时暴露的思维惯性从第一步想到最后一步新手拿到 n3第一反应几乎都是“第一个盘子放哪根柱子”。这个思路本身没错但它在 n3 之后会迅速失控因为分支太多你没法在脑子里穷举。正确的切入方向是反过来的先看最后一步。最大的那个盘子最后一定落在目标柱 C 上而它一旦移动就必须直接从 A 到 C中间不能借道 B因为任何一根柱子上都不会有比它更大的盘子来承载它。所以最大的盘只移动一次而且是在“前 n-1 个盘子全部搬到 B、C 已经空出来”的那一刻。这个“倒着想”的视角切换是汉诺塔教给我们的第一课也是整个分治思想的雏形不要问第一步做什么要问为了完成最后一步前面必须准备成什么样。很多人学完汉诺塔记住的是代码其实真正该记住的是这个“从终态倒推前置条件”的习惯后面写归并排序、写树的后序遍历、写任何要“先准备好子树再动根”的逻辑用的都是同一套思维。2. 递归的落点把 n 拆成 n-1 的具体动作递归这两个字被讲得太玄了。剥离掉所有包装它就是一个动作把当前问题改成规模更小、但结构完全一样的问题然后假装它已经被解决了。汉诺塔之所以是经典教材案例是因为它的“缩小一号”拆得非常干净没有歧义没有边界模糊。n 个盘子从 A 搬到 C拆成三步把上面 n-1 个从 A 搬到 B把最大的那个从 A 搬到 C把 n-1 个从 B 搬到 C。这三步里第一步和第三步都是“n-1 个盘子从某柱搬到某柱”的问题结构一模一样只是柱子的名字换了。这就是递归成立的依据。2.1 三个调用的参数换位是全部难点所在我见过最多的错误不在递归思想上而在参数传递上。下面这个写法是标准的注意每一行注释里角色的变化def hanoi(n, src, aux, dst): if n 0: return hanoi(n - 1, src, dst, aux) # 上面 n-1 个从 src 搬到 auxdst 临时当辅助 print(f{src} - {dst}) # 最大盘从 src 直接到 dst hanoi(n - 1, aux, src, dst) # 那 n-1 个从 aux 搬到 dstsrc 临时当辅助第一次调用时dst变成了临时的辅助柱aux反而成了目的地第二次调用时src变成了辅助柱。这两个位置的交换是整个函数里唯一需要动脑的地方剩下的都是机械展开。顺便提一个真实的坑Python 里from是关键字不能当参数名。我见过不少人写def hanoi(n, from, to, via)然后对着 SyntaxError 发愣。用src / aux / dst或者start / mid / end都可以别图省事。还有一个更隐蔽的错误模式参数写反了n1 时依然能输出正确结果n2 时结果看起来“也是三步”直到 n3 才发现某一行的src和aux对不上。这个坑之所以难查是因为它不报错只出错序。我的建议是别靠肉眼验证后面第 6 节会给一个自动校验器。2.2 终止条件写 n1 还是 n0这是个小分歧但能看出一个人对递归边界的理解程度。写n 1的版本好处是语义直观只剩一个盘子时直接从源柱搬到目标柱然后返回。写n 0的版本好处是统一不用在终止分支里再写一次移动逻辑整个函数体只剩三条语句逻辑上更干净。我现在的习惯是写n 0直接 return。原因是 n0 时“不需要做任何事”这个语义在数学上是自洽的递归展开到最后会自动收敛不会多出一层特判。而且当你要把这段逻辑移植到别的语言、或者改成求移动次数时n0 版本能省掉一处重复代码。代价是如果真有人传 n0 进来你的函数会安静地什么都不做。对于教学示例来说这没问题对于库函数级别的代码最好在入口处加一个assert n 0。2.3 2^n-1 的推导与量级感知移动次数记为 T(n)从拆解方式能直接写出递推式T(n) 2·T(n-1) 1T(1) 1。展开一下T(n) 2^(n-1) 2^(n-2) ... 1 2^n - 1。用数学归纳法验证只需要两行n1 时 1 2^1 - 1 成立假设 T(k) 2^k - 1则 T(k1) 2(2^k - 1) 1 2^(k1) - 1成立。数字本身不吓人吓人的是指数。n10 是 1023 步n20 是 1048575 步n30 已经超过 10 亿步。那个流传很广的古老传说里说某处有 64 个金盘僧侣每天搬一个世界终结之日就是搬完之时——按每秒一步、全年无休算2^64 - 1 秒大约是 5849 亿年而宇宙年龄的常见估计只有 138 亿年左右差了四十多倍。这个量级感知很有用。以后你写任何嵌套两层的递归、或者看到 O(2^n) 的复杂度标注脑子里应该立刻浮现出“n 超过 30 就不要指望跑完了”这个红线而不是等到程序卡死才反应过来。3. 换三条路走同一道题栈模拟与二进制取盘递归写完了不等于这题吃透了。汉诺塔有三种风格完全不同的解法把这三种都实现一遍你对“递归本质上是栈”这句话的理解会从抽象变成具体。3.1 手写栈把调用摊平递归为什么能在不手动管理栈的情况下完成“回到上一层继续干活”因为函数调用帧本身就是压在一个栈上的。既然如此我们完全可以自己造一个栈把三件事做完左子树、移动大盘、做完右子树显式排好队。def hanoi_iter(n, src, aux, dst): # 栈元素: (规模, 源, 辅助, 目标, 阶段) # 阶段 0: 还没展开阶段 1: 左子树已完成该移动大盘了 stack [(n, src, aux, dst, 0)] while stack: k, s, a, d, stage stack.pop() if k 0: continue if stage 0: stack.append((k, s, a, d, 1)) # 先压待移动标记 stack.append((k - 1, s, d, a, 0)) # 再压左子树保证它先被处理 else: print(f{s} - {d}) stack.append((k - 1, a, s, d, 0)) # 展开右子树关键在于压栈顺序是逻辑执行顺序的逆序。因为栈是后进先出你想让左子树先跑就得把它压在标记之后。这个技巧在写非递归的中序遍历、非递归的快排时一模一样属于那种“掌握一次到处复用”的通用手法。这段代码还顺便解释了一个现象递归版本那么短是因为编译器/解释器帮你做了压栈这堆脏活。你在写递归时的每一次“函数调用”底层都在做上面这堆append / pop。3.2 第 k 步动哪个盘子最低位 1 的位置汉诺塔有一个特别漂亮的二进制性质第 k 步移动的盘子编号等于 k 的二进制表示中最低位 1 所在的位置从 1 开始计数。k1001动盘 1k2010动盘 2k3011动盘 1k4100动盘 3k5101动盘 1k6110动盘 2k7111动盘 1。对照 n3 的真实移动序列 1,2,1,3,1,2,1完全吻合。代码只有一行def disk_at_step(k): # k 从 1 开始返回该步应该移动的盘子编号 return (k -k).bit_length()k -k是取最低位 1 的经典位运算bit_length()给出它的位置。这个性质在 n 很大时特别有用你想知道第 10 亿步动的是哪个盘子不需要模拟前面 10 亿步直接算就行。为什么会有这个规律直观解释是第 1 号盘每隔一步动一次第 2 号盘每隔两步动一次第 j 号盘每隔 2^(j-1) 步动一次。整个移动序列就是一张“二进制计数器”每走一步相当于加一进位时才会轮到更大的盘子。这个类比一旦建立汉诺塔的很多性质就不用背了。3.3 方向规律与“每两步必动最小盘”还有一个不用记公式的规律最小盘永远在循环移动而且方向是固定的。n 为奇数时最小盘按 src → dst → aux → src 的顺序跑n 为偶数时顺序反过来src → aux → dst → src。剩下的每一步除了最小盘之外只有一种合法的移动方式照做即可。这个规律背后是奇偶性在起作用盘子的总数决定了整体“旋转”的方向。我一般在教学时会先让人手动模拟 n3 和 n4 各一次把最小盘的运动轨迹画出来那个循环模式就自己跳出来了。把这三条路递归、手写栈、二进制都写一遍你会发现它们描述的是同一个过程的三个不同投影。递归版本描述“结构”栈版本描述“执行”二进制版本描述“序列”。以后再遇到任何递归题试试用这三个视角各看一遍理解会陡增。4. 优化之前先分清哪些提速是真的讲到这里很多人会本能地想“能不能优化一下”。这是个好习惯但汉诺塔这题的优化空间有个非常反直觉的特点有些优化在某种问法下有意义在另一种问法下纯属自欺。分不清这一点你写的代码看起来更高级实际什么都没省。4.1 记忆化在求次数和求序列上的两种命运先说结论再说原因。你的目标记忆化是否有用原因只求最少移动次数有用朴素递归会重复计算同一个规模加缓存能把 O(2^n) 降到 O(n)输出完整的移动序列没用输出本身就有 2^n - 1 行任何算法都逃不掉求第 k 步动哪个盘不适用直接用 3.2 的位运算O(1) 解决为什么“求序列”时记忆化是无用功因为缓存里存的东西是一串长度为 2^k - 1 的移动指令每次复用缓存都要把这串指令复制出来复制成本同样是 2^k - 1。你省下了“计算”但没省下“输出”总工作量不变反而多占了一份缓存内存。这是个非常典型的例子优化的前提是先搞清楚瓶颈在哪。如果瓶颈是 I/O那么任何算法层面的花招都不会有肉眼可见的效果。我当年就在这上面浪费过一个下午。给汉诺塔加了lru_cache跑 n20发现加不加耗时几乎一样还以为是缓存没生效查了半天。后来用不打印的版本一对比才明白真正的耗时全在print上。4.2 递归深度、栈帧与输出瓶颈三个实打实的注意点都是我在实际跑代码时撞出来的。第一递归深度不等于 n而是 n。汉诺塔的递归是“先钻左边到底再回溯”栈的最大深度正好是 n 层。所以 n500 就需要 500 层栈帧。Python 默认的递归上限是 1000sys.setrecursionlimit能改但这个设置只影响解释器的计数真正的 C 层调用栈可能更早就爆掉报一个RecursionError或者直接段错误。稳妥做法是n 超过几百就别用递归了换 3.1 的手写栈。第二测试性能时一定要关掉打印。n20 是一百多万行输出光是终端滚动就能拖慢几个数量级。我一般的做法是把print换成一个计数器自增最后断言计数器等于2**n - 1这样既验证了逻辑又不被 I/O 拖累。第三别拿 n 很大的情况去“验证正确性”。n25 的序列没人能肉眼检查正确的验证方式是小 n 手工推演 自动校验器见 6.1。我见过有人在 n15 的输出里找规律找了两个小时最后发现是校验逻辑本身写错了。5. 变形题才是试金石单把三柱汉诺塔写对说明你掌握了基本递归。但真正能检验理解深度的是题目规则稍微一改你还剩多少招。5.1 四柱汉诺塔与 Frame-Stewart 的取舍加一根柱子问题从“有唯一拆分方式”变成“需要选择拆分点”。四柱时你不再是把 n-1 个搬走而是搬 k 个到某根柱子上k 取多少可以自己定然后让剩下的 n-k 个在“三柱环境”里搬到目标最后把那 k 个搬过去。总步数是 2·T4(k) (2^(n-k) - 1)。from functools import lru_cache lru_cache(maxsizeNone) def hanoi4(n): if n 1: return n return min(2 * hanoi4(k) (2 ** (n - k) - 1) for k in range(1, n))这里的 k 不能拍脑袋取 n-1那样反而退化成三柱解法。最优 k 会随着 n 增长而缓慢变化整体复杂度大约在 2 的 √(2n) 次方这个量级比三柱的 2^n 好太多。这个思路通常被称为 Frame-Stewart 算法它给出的结果被广泛认为是最优的但严格证明至今没有完全解决——这一点很值得玩味一道小学玩具级别的题目加一根柱子就变成了数学上的开放问题。我在实际写这段代码时踩过的坑是hanoi4内部调用2 ** (n - k)n 稍大一点比如 n60就会产生巨大的整数虽然 Python 能算但循环里的 min 比较会明显变慢。所以这类题在工程里只适合验证小规模真要算大数得用大整数库或者放弃求精确值。5.2 单向移动版本里的唯一合法步另一个常见的变形是只允许按固定方向移动比如只能 A→C→B→A 这样循环问还能不能完成任务、最少多少步。这题的解法反而比原版更简单因为每一步的合法移动几乎都被唯一确定了。规则是最小盘永远按固定方向走一步在剩下的两根柱子之间只存在一种合法移动要么不合法要么唯一。这个“唯一合法步”的策略不需要搜索也不需要递归一个 while 循环就完事。但要注意一个陷阱判断“剩下的两根柱子之间哪种移动合法”时必须同时检查“源柱非空”和“目标柱顶部更大或为空”。只检查一半是我见过最常见的错误表现是程序半天不动或者搬出一个违规序列。这类变形题的价值在于训练你对“约束强度”的敏感度。原版汉诺塔的约束是中等强度所以有多个选择单向版本约束极强所以退化成确定性过程四柱版本约束变弱所以需要搜索或动态规划。同一个问题的不同变体正好覆盖了“无搜索—启发式—穷举”这一整条谱系。6. 调试与迁移从看得见到用得上最后聊两块怎么把执行过程变得肉眼可见以及这题到底能迁移到哪些真实场景。6.1 缩进打印调用树与合法性校验器调试递归最有效的手段是打印带缩进的调用树。在函数入口加一个深度参数每次递归加一打印时按深度补空格def trace(n, src, aux, dst, depth0): pad * depth if n 0: return print(f{pad}hanoi({n}, {src}, {aux}, {dst})) trace(n - 1, src, dst, aux, depth 1) print(f{pad} MOVE {src} - {dst}) trace(n - 1, aux, src, dst, depth 1)跑 n3你会看到一棵完整的树。我特别建议你盯住hanoi(1, ...)那几行看它们的参数是不是每一步都不同这一步能立刻抓出参数写反的问题。比打印更狠的是写一个独立校验器把算法输出的移动序列当作黑盒输入逐条验证def validate(moves, n): pegs {A: list(range(n, 0, -1)), B: [], C: []} for i, (a, b) in enumerate(moves, 1): assert pegs[a], f第 {i} 步{a} 柱是空的 disk pegs[a].pop() if pegs[b]: assert pegs[b][-1] disk, f第 {i} 步大盘 {disk} 压到了小盘 {pegs[b][-1]} pegs[b].append(disk) assert len(moves) 2 ** n - 1, f步数不对应为 {2 ** n - 1}实为 {len(moves)} assert pegs[C] list(range(n, 0, -1)), 最终状态不对 print(序列合法)这段代码几十行但它把“看起来对”变成“可证明对”。而且它是通用的不管你的解法是递归、迭代还是自己瞎想的都能拿它当裁判。我在改写四柱版本时就是靠它省了大量时间。6.2 轮换备份、资源释放与指数直觉汉诺塔离实际工程不算远只是平时不容易联想到。轮换备份是最像的一个场景。传统的“祖父—父—子”三代备份策略本质上就是三根柱子新数据写入前必须先把占用的介质腾出来而腾出来的顺序是有约束的——你不能直接把父介质覆盖掉否则就失去了回滚能力。介质数量有限时“先保哪一份、后覆盖哪一份”的决策逻辑和汉诺塔里的“先搬 n-1 再动大盘”是同一个约束结构。资源释放顺序也类似。有些系统中资源之间存在嵌套依赖外层资源必须等内层全部释放完才能回收而回收过程中又不能破坏已有的引用关系。把这种依赖建模成树或柱子用后序的方式处理写出来的代码天然不会漏。指数直觉可能是最实用的一点。做过这道题之后你看到一个方案的复杂度带 2^n会本能地先估一下 n 的取值范围而不是直接上手实现。我见过不少项目在这里翻车设计阶段觉得“最多也就几十个元素全排列嘛”真跑起来才发现 30 个元素就是 10 亿级别只能重做。汉诺塔用最简单的形式把这个教训刻进脑子里代价比在真实项目里翻车低太多。还有个不算冷门但很少被提的用途这题常被用作认知心理学里的问题解决测验用它来观察人面对“需要逆向规划”的任务时的策略差异。这一点挺有意思——同一道题有人上来就动手挪有人先画终态再倒推两种风格的差异在后面的复杂任务里会持续放大。7. 一些埋在细节里的经验写到这里还有一些零碎的东西值得单独拎出来都是那种“文档里不会提、但真写起来会卡住”的点。关于编码习惯递归函数的参数顺序我的建议是固定成“规模、源、辅助、目标”这个次序并且在文件头注释里写清楚。原因是这个顺序一旦确定了你在调试时读每一行调用都能对得上号而如果今天按这个顺序、明天按那个顺序出问题时你连自己写的代码都要重新推理一遍。关于验证策略我的原则是小规模全流程大规模只看统计量。n ≤ 5 时把每一步打印出来逐行检查n ≥ 10 时只检查步数、首步、末步和最终状态中间过程交给校验器。关于边界值n1 是最容易被忽略的很多错误参数顺序的代码在 n1 时都能跑通因为那时候根本用不到辅助柱。所以测试一定要从 n2 或 n3 开始n1 只能证明你没写错函数签名。关于学习路径如果你是第一次学递归建议顺序是——先手推 n1 到 n3 的全过程把每次移动写成表格再照着表反推代码然后把代码的参数全部打乱看能不能通过输出来判断哪一版是对的最后写迭代版和校验器。走完这一圈递归这块基本上就扎实了。关于心态汉诺塔的代码短到可以背下来但背下来的东西换个壳子你就认不出来了。真正值得带走的是那个“先确定终态的前置条件再把问题缩一号”的思路以及“写个校验器当裁判”的习惯。这两样东西比那三行代码值钱得多。最后再分享一个我个人的小技巧每当我觉得某个递归写对了但心里不踏实我就会把它翻译成手写栈的版本。翻译过程中那些含糊的边界、想当然的参数顺序、没想清楚的终止条件会全部暴露出来——因为栈不会帮你兜底它会忠实记录你压进去的每一条指令。能顺利翻译过去才算真的懂了。
1. 先把三根柱子的规则拆干净汉诺塔也有人写成“汉罗塔”这道题我最早是在一本算法入门书里看到的当时觉得规则简单得有点幼稚三根柱子一堆大小不一的圆盘从 A 搬到 C一次搬一个大盘不能压小盘。三行递归代码写完跑 n3 输出了 7 行看着挺对就翻篇了。真正让我重新回来啃它的是后来在带新人的时候被反问了一句“为什么你的递归里两次调用要交换参数如果我把参数顺序写反n1 和 n2 居然还能跑出结果这怎么回事”那一刻我才意识到汉诺塔这道题的价值根本不在“写出代码”而在于它把递归最容易被糊弄过去的那部分——状态的角色转移——赤裸裸地摆在你面前。它是递归思想的照妖镜你觉得你懂了其实你只是背下来了。这篇内容我想写给两类人一类是刚接触递归想真正搞明白“为什么这样拆”的初学者另一类是写过很多遍汉诺塔但从来没深究过复杂度、迭代解法、变形题的开发者。下面这些都是我在实际写代码、带人、做练习时踩出来的理解不是课本上的标准答案。1.1 那条“大盘不能压小盘”到底约束了什么很多人把这条规则当成一个“限制”其实它是一条结构性约束它直接决定了每一步可选的移动数量极少。你可以在纸上试一下n3 时除了第一步有 3 种选择之后每一步真正合法的移动往往只有 1 到 2 种。这不是巧合而是因为每条柱子在任意时刻都是一个“从大到小”的有序序列任何时刻你只能拿走最上面那个。把这个观察说清楚一点柱子不是普通的容器它是栈。你只能从顶部取只能往顶部放而且放入的元素必须比当前顶部更小。这个“后进先出 单调递减”的组合正好是递归和显式栈能够相互模拟的根本原因。后面讲迭代解法时你会发现代码能这么写全靠这一点。理解了这一层你就能回答一个常见疑问为什么汉诺塔不能用“贪心”蒙混过去因为合法的下一步往往有多个选择而且选错一步并不会立刻违规而是会在几步之后把你堵死。这种“局部合法、全局死路”的结构恰恰是深度优先搜索和递归要处理的东西。1.2 n3 时暴露的思维惯性从第一步想到最后一步新手拿到 n3第一反应几乎都是“第一个盘子放哪根柱子”。这个思路本身没错但它在 n3 之后会迅速失控因为分支太多你没法在脑子里穷举。正确的切入方向是反过来的先看最后一步。最大的那个盘子最后一定落在目标柱 C 上而它一旦移动就必须直接从 A 到 C中间不能借道 B因为任何一根柱子上都不会有比它更大的盘子来承载它。所以最大的盘只移动一次而且是在“前 n-1 个盘子全部搬到 B、C 已经空出来”的那一刻。这个“倒着想”的视角切换是汉诺塔教给我们的第一课也是整个分治思想的雏形不要问第一步做什么要问为了完成最后一步前面必须准备成什么样。很多人学完汉诺塔记住的是代码其实真正该记住的是这个“从终态倒推前置条件”的习惯后面写归并排序、写树的后序遍历、写任何要“先准备好子树再动根”的逻辑用的都是同一套思维。2. 递归的落点把 n 拆成 n-1 的具体动作递归这两个字被讲得太玄了。剥离掉所有包装它就是一个动作把当前问题改成规模更小、但结构完全一样的问题然后假装它已经被解决了。汉诺塔之所以是经典教材案例是因为它的“缩小一号”拆得非常干净没有歧义没有边界模糊。n 个盘子从 A 搬到 C拆成三步把上面 n-1 个从 A 搬到 B把最大的那个从 A 搬到 C把 n-1 个从 B 搬到 C。这三步里第一步和第三步都是“n-1 个盘子从某柱搬到某柱”的问题结构一模一样只是柱子的名字换了。这就是递归成立的依据。2.1 三个调用的参数换位是全部难点所在我见过最多的错误不在递归思想上而在参数传递上。下面这个写法是标准的注意每一行注释里角色的变化def hanoi(n, src, aux, dst): if n 0: return hanoi(n - 1, src, dst, aux) # 上面 n-1 个从 src 搬到 auxdst 临时当辅助 print(f{src} - {dst}) # 最大盘从 src 直接到 dst hanoi(n - 1, aux, src, dst) # 那 n-1 个从 aux 搬到 dstsrc 临时当辅助第一次调用时dst变成了临时的辅助柱aux反而成了目的地第二次调用时src变成了辅助柱。这两个位置的交换是整个函数里唯一需要动脑的地方剩下的都是机械展开。顺便提一个真实的坑Python 里from是关键字不能当参数名。我见过不少人写def hanoi(n, from, to, via)然后对着 SyntaxError 发愣。用src / aux / dst或者start / mid / end都可以别图省事。还有一个更隐蔽的错误模式参数写反了n1 时依然能输出正确结果n2 时结果看起来“也是三步”直到 n3 才发现某一行的src和aux对不上。这个坑之所以难查是因为它不报错只出错序。我的建议是别靠肉眼验证后面第 6 节会给一个自动校验器。2.2 终止条件写 n1 还是 n0这是个小分歧但能看出一个人对递归边界的理解程度。写n 1的版本好处是语义直观只剩一个盘子时直接从源柱搬到目标柱然后返回。写n 0的版本好处是统一不用在终止分支里再写一次移动逻辑整个函数体只剩三条语句逻辑上更干净。我现在的习惯是写n 0直接 return。原因是 n0 时“不需要做任何事”这个语义在数学上是自洽的递归展开到最后会自动收敛不会多出一层特判。而且当你要把这段逻辑移植到别的语言、或者改成求移动次数时n0 版本能省掉一处重复代码。代价是如果真有人传 n0 进来你的函数会安静地什么都不做。对于教学示例来说这没问题对于库函数级别的代码最好在入口处加一个assert n 0。2.3 2^n-1 的推导与量级感知移动次数记为 T(n)从拆解方式能直接写出递推式T(n) 2·T(n-1) 1T(1) 1。展开一下T(n) 2^(n-1) 2^(n-2) ... 1 2^n - 1。用数学归纳法验证只需要两行n1 时 1 2^1 - 1 成立假设 T(k) 2^k - 1则 T(k1) 2(2^k - 1) 1 2^(k1) - 1成立。数字本身不吓人吓人的是指数。n10 是 1023 步n20 是 1048575 步n30 已经超过 10 亿步。那个流传很广的古老传说里说某处有 64 个金盘僧侣每天搬一个世界终结之日就是搬完之时——按每秒一步、全年无休算2^64 - 1 秒大约是 5849 亿年而宇宙年龄的常见估计只有 138 亿年左右差了四十多倍。这个量级感知很有用。以后你写任何嵌套两层的递归、或者看到 O(2^n) 的复杂度标注脑子里应该立刻浮现出“n 超过 30 就不要指望跑完了”这个红线而不是等到程序卡死才反应过来。3. 换三条路走同一道题栈模拟与二进制取盘递归写完了不等于这题吃透了。汉诺塔有三种风格完全不同的解法把这三种都实现一遍你对“递归本质上是栈”这句话的理解会从抽象变成具体。3.1 手写栈把调用摊平递归为什么能在不手动管理栈的情况下完成“回到上一层继续干活”因为函数调用帧本身就是压在一个栈上的。既然如此我们完全可以自己造一个栈把三件事做完左子树、移动大盘、做完右子树显式排好队。def hanoi_iter(n, src, aux, dst): # 栈元素: (规模, 源, 辅助, 目标, 阶段) # 阶段 0: 还没展开阶段 1: 左子树已完成该移动大盘了 stack [(n, src, aux, dst, 0)] while stack: k, s, a, d, stage stack.pop() if k 0: continue if stage 0: stack.append((k, s, a, d, 1)) # 先压待移动标记 stack.append((k - 1, s, d, a, 0)) # 再压左子树保证它先被处理 else: print(f{s} - {d}) stack.append((k - 1, a, s, d, 0)) # 展开右子树关键在于压栈顺序是逻辑执行顺序的逆序。因为栈是后进先出你想让左子树先跑就得把它压在标记之后。这个技巧在写非递归的中序遍历、非递归的快排时一模一样属于那种“掌握一次到处复用”的通用手法。这段代码还顺便解释了一个现象递归版本那么短是因为编译器/解释器帮你做了压栈这堆脏活。你在写递归时的每一次“函数调用”底层都在做上面这堆append / pop。3.2 第 k 步动哪个盘子最低位 1 的位置汉诺塔有一个特别漂亮的二进制性质第 k 步移动的盘子编号等于 k 的二进制表示中最低位 1 所在的位置从 1 开始计数。k1001动盘 1k2010动盘 2k3011动盘 1k4100动盘 3k5101动盘 1k6110动盘 2k7111动盘 1。对照 n3 的真实移动序列 1,2,1,3,1,2,1完全吻合。代码只有一行def disk_at_step(k): # k 从 1 开始返回该步应该移动的盘子编号 return (k -k).bit_length()k -k是取最低位 1 的经典位运算bit_length()给出它的位置。这个性质在 n 很大时特别有用你想知道第 10 亿步动的是哪个盘子不需要模拟前面 10 亿步直接算就行。为什么会有这个规律直观解释是第 1 号盘每隔一步动一次第 2 号盘每隔两步动一次第 j 号盘每隔 2^(j-1) 步动一次。整个移动序列就是一张“二进制计数器”每走一步相当于加一进位时才会轮到更大的盘子。这个类比一旦建立汉诺塔的很多性质就不用背了。3.3 方向规律与“每两步必动最小盘”还有一个不用记公式的规律最小盘永远在循环移动而且方向是固定的。n 为奇数时最小盘按 src → dst → aux → src 的顺序跑n 为偶数时顺序反过来src → aux → dst → src。剩下的每一步除了最小盘之外只有一种合法的移动方式照做即可。这个规律背后是奇偶性在起作用盘子的总数决定了整体“旋转”的方向。我一般在教学时会先让人手动模拟 n3 和 n4 各一次把最小盘的运动轨迹画出来那个循环模式就自己跳出来了。把这三条路递归、手写栈、二进制都写一遍你会发现它们描述的是同一个过程的三个不同投影。递归版本描述“结构”栈版本描述“执行”二进制版本描述“序列”。以后再遇到任何递归题试试用这三个视角各看一遍理解会陡增。4. 优化之前先分清哪些提速是真的讲到这里很多人会本能地想“能不能优化一下”。这是个好习惯但汉诺塔这题的优化空间有个非常反直觉的特点有些优化在某种问法下有意义在另一种问法下纯属自欺。分不清这一点你写的代码看起来更高级实际什么都没省。4.1 记忆化在求次数和求序列上的两种命运先说结论再说原因。你的目标记忆化是否有用原因只求最少移动次数有用朴素递归会重复计算同一个规模加缓存能把 O(2^n) 降到 O(n)输出完整的移动序列没用输出本身就有 2^n - 1 行任何算法都逃不掉求第 k 步动哪个盘不适用直接用 3.2 的位运算O(1) 解决为什么“求序列”时记忆化是无用功因为缓存里存的东西是一串长度为 2^k - 1 的移动指令每次复用缓存都要把这串指令复制出来复制成本同样是 2^k - 1。你省下了“计算”但没省下“输出”总工作量不变反而多占了一份缓存内存。这是个非常典型的例子优化的前提是先搞清楚瓶颈在哪。如果瓶颈是 I/O那么任何算法层面的花招都不会有肉眼可见的效果。我当年就在这上面浪费过一个下午。给汉诺塔加了lru_cache跑 n20发现加不加耗时几乎一样还以为是缓存没生效查了半天。后来用不打印的版本一对比才明白真正的耗时全在print上。4.2 递归深度、栈帧与输出瓶颈三个实打实的注意点都是我在实际跑代码时撞出来的。第一递归深度不等于 n而是 n。汉诺塔的递归是“先钻左边到底再回溯”栈的最大深度正好是 n 层。所以 n500 就需要 500 层栈帧。Python 默认的递归上限是 1000sys.setrecursionlimit能改但这个设置只影响解释器的计数真正的 C 层调用栈可能更早就爆掉报一个RecursionError或者直接段错误。稳妥做法是n 超过几百就别用递归了换 3.1 的手写栈。第二测试性能时一定要关掉打印。n20 是一百多万行输出光是终端滚动就能拖慢几个数量级。我一般的做法是把print换成一个计数器自增最后断言计数器等于2**n - 1这样既验证了逻辑又不被 I/O 拖累。第三别拿 n 很大的情况去“验证正确性”。n25 的序列没人能肉眼检查正确的验证方式是小 n 手工推演 自动校验器见 6.1。我见过有人在 n15 的输出里找规律找了两个小时最后发现是校验逻辑本身写错了。5. 变形题才是试金石单把三柱汉诺塔写对说明你掌握了基本递归。但真正能检验理解深度的是题目规则稍微一改你还剩多少招。5.1 四柱汉诺塔与 Frame-Stewart 的取舍加一根柱子问题从“有唯一拆分方式”变成“需要选择拆分点”。四柱时你不再是把 n-1 个搬走而是搬 k 个到某根柱子上k 取多少可以自己定然后让剩下的 n-k 个在“三柱环境”里搬到目标最后把那 k 个搬过去。总步数是 2·T4(k) (2^(n-k) - 1)。from functools import lru_cache lru_cache(maxsizeNone) def hanoi4(n): if n 1: return n return min(2 * hanoi4(k) (2 ** (n - k) - 1) for k in range(1, n))这里的 k 不能拍脑袋取 n-1那样反而退化成三柱解法。最优 k 会随着 n 增长而缓慢变化整体复杂度大约在 2 的 √(2n) 次方这个量级比三柱的 2^n 好太多。这个思路通常被称为 Frame-Stewart 算法它给出的结果被广泛认为是最优的但严格证明至今没有完全解决——这一点很值得玩味一道小学玩具级别的题目加一根柱子就变成了数学上的开放问题。我在实际写这段代码时踩过的坑是hanoi4内部调用2 ** (n - k)n 稍大一点比如 n60就会产生巨大的整数虽然 Python 能算但循环里的 min 比较会明显变慢。所以这类题在工程里只适合验证小规模真要算大数得用大整数库或者放弃求精确值。5.2 单向移动版本里的唯一合法步另一个常见的变形是只允许按固定方向移动比如只能 A→C→B→A 这样循环问还能不能完成任务、最少多少步。这题的解法反而比原版更简单因为每一步的合法移动几乎都被唯一确定了。规则是最小盘永远按固定方向走一步在剩下的两根柱子之间只存在一种合法移动要么不合法要么唯一。这个“唯一合法步”的策略不需要搜索也不需要递归一个 while 循环就完事。但要注意一个陷阱判断“剩下的两根柱子之间哪种移动合法”时必须同时检查“源柱非空”和“目标柱顶部更大或为空”。只检查一半是我见过最常见的错误表现是程序半天不动或者搬出一个违规序列。这类变形题的价值在于训练你对“约束强度”的敏感度。原版汉诺塔的约束是中等强度所以有多个选择单向版本约束极强所以退化成确定性过程四柱版本约束变弱所以需要搜索或动态规划。同一个问题的不同变体正好覆盖了“无搜索—启发式—穷举”这一整条谱系。6. 调试与迁移从看得见到用得上最后聊两块怎么把执行过程变得肉眼可见以及这题到底能迁移到哪些真实场景。6.1 缩进打印调用树与合法性校验器调试递归最有效的手段是打印带缩进的调用树。在函数入口加一个深度参数每次递归加一打印时按深度补空格def trace(n, src, aux, dst, depth0): pad * depth if n 0: return print(f{pad}hanoi({n}, {src}, {aux}, {dst})) trace(n - 1, src, dst, aux, depth 1) print(f{pad} MOVE {src} - {dst}) trace(n - 1, aux, src, dst, depth 1)跑 n3你会看到一棵完整的树。我特别建议你盯住hanoi(1, ...)那几行看它们的参数是不是每一步都不同这一步能立刻抓出参数写反的问题。比打印更狠的是写一个独立校验器把算法输出的移动序列当作黑盒输入逐条验证def validate(moves, n): pegs {A: list(range(n, 0, -1)), B: [], C: []} for i, (a, b) in enumerate(moves, 1): assert pegs[a], f第 {i} 步{a} 柱是空的 disk pegs[a].pop() if pegs[b]: assert pegs[b][-1] disk, f第 {i} 步大盘 {disk} 压到了小盘 {pegs[b][-1]} pegs[b].append(disk) assert len(moves) 2 ** n - 1, f步数不对应为 {2 ** n - 1}实为 {len(moves)} assert pegs[C] list(range(n, 0, -1)), 最终状态不对 print(序列合法)这段代码几十行但它把“看起来对”变成“可证明对”。而且它是通用的不管你的解法是递归、迭代还是自己瞎想的都能拿它当裁判。我在改写四柱版本时就是靠它省了大量时间。6.2 轮换备份、资源释放与指数直觉汉诺塔离实际工程不算远只是平时不容易联想到。轮换备份是最像的一个场景。传统的“祖父—父—子”三代备份策略本质上就是三根柱子新数据写入前必须先把占用的介质腾出来而腾出来的顺序是有约束的——你不能直接把父介质覆盖掉否则就失去了回滚能力。介质数量有限时“先保哪一份、后覆盖哪一份”的决策逻辑和汉诺塔里的“先搬 n-1 再动大盘”是同一个约束结构。资源释放顺序也类似。有些系统中资源之间存在嵌套依赖外层资源必须等内层全部释放完才能回收而回收过程中又不能破坏已有的引用关系。把这种依赖建模成树或柱子用后序的方式处理写出来的代码天然不会漏。指数直觉可能是最实用的一点。做过这道题之后你看到一个方案的复杂度带 2^n会本能地先估一下 n 的取值范围而不是直接上手实现。我见过不少项目在这里翻车设计阶段觉得“最多也就几十个元素全排列嘛”真跑起来才发现 30 个元素就是 10 亿级别只能重做。汉诺塔用最简单的形式把这个教训刻进脑子里代价比在真实项目里翻车低太多。还有个不算冷门但很少被提的用途这题常被用作认知心理学里的问题解决测验用它来观察人面对“需要逆向规划”的任务时的策略差异。这一点挺有意思——同一道题有人上来就动手挪有人先画终态再倒推两种风格的差异在后面的复杂任务里会持续放大。7. 一些埋在细节里的经验写到这里还有一些零碎的东西值得单独拎出来都是那种“文档里不会提、但真写起来会卡住”的点。关于编码习惯递归函数的参数顺序我的建议是固定成“规模、源、辅助、目标”这个次序并且在文件头注释里写清楚。原因是这个顺序一旦确定了你在调试时读每一行调用都能对得上号而如果今天按这个顺序、明天按那个顺序出问题时你连自己写的代码都要重新推理一遍。关于验证策略我的原则是小规模全流程大规模只看统计量。n ≤ 5 时把每一步打印出来逐行检查n ≥ 10 时只检查步数、首步、末步和最终状态中间过程交给校验器。关于边界值n1 是最容易被忽略的很多错误参数顺序的代码在 n1 时都能跑通因为那时候根本用不到辅助柱。所以测试一定要从 n2 或 n3 开始n1 只能证明你没写错函数签名。关于学习路径如果你是第一次学递归建议顺序是——先手推 n1 到 n3 的全过程把每次移动写成表格再照着表反推代码然后把代码的参数全部打乱看能不能通过输出来判断哪一版是对的最后写迭代版和校验器。走完这一圈递归这块基本上就扎实了。关于心态汉诺塔的代码短到可以背下来但背下来的东西换个壳子你就认不出来了。真正值得带走的是那个“先确定终态的前置条件再把问题缩一号”的思路以及“写个校验器当裁判”的习惯。这两样东西比那三行代码值钱得多。最后再分享一个我个人的小技巧每当我觉得某个递归写对了但心里不踏实我就会把它翻译成手写栈的版本。翻译过程中那些含糊的边界、想当然的参数顺序、没想清楚的终止条件会全部暴露出来——因为栈不会帮你兜底它会忠实记录你压进去的每一条指令。能顺利翻译过去才算真的懂了。
