汉诺塔递归自用——这是我当初在算法笔记第一页写下的标题。那会儿刚学递归每天被各种“递推公式终止条件”搞得晕头转向直到把汉诺塔的递归思路彻底想通才算真正摸到递归的门。这篇文章不打算写成教科书而是把我复盘时理顺的完整思路整理出来从三根柱子的规则到递归三步法怎么写代码再到调用栈怎么一层层摊开看最后把64阶汉诺塔这个吓人的数字用数学算一遍。内容适合两类人被递归折磨的初学者以及想快速复习汉诺塔递归本质的老手。看完你至少能徒手写出正确代码并且知道为什么步骤数是2^n减1而不是背模板。1. 汉诺塔问题三根柱子与“搬家的限制规则”1.1 规则速览与生活类比汉诺塔的游戏规则其实很简单有三根柱子A、B、CA上从大到小叠了N个圆盘最大的在底部最小的在顶部目标是把这一摞盘子整体搬到C柱规则只有两条一次只能移动一个圆盘任何时刻大盘子不能压在小盘子上面。B柱允许作为临时中转而且盘子的数量不受限制。我习惯把这个规则类比成“整理碗柜”A柜子里有一摞从大到小的碗你要把它们全部搬到C柜厨房台面B可以临时放碗。你一次只能拿一个碗而且任何时候大碗都不能压在小碗上。汉诺塔的“中转柱”就是那个临时台面它看起来不起眼却是整个问题能解的关键。没有B柱你连三个盘子都搬不动。很多初学者会觉得这个游戏就是“人肉模拟移动”盘子少的时候确实可以靠试错但盘子一多人脑的短期记忆根本扛不住。N3还能硬试N5就开始头晕N8以上基本只能靠算法了。这正是汉诺塔作为递归入门题的价值它把“看起来需要全局规划”的问题变成了一个可以机械化执行的“自我重复”过程。1.2 为什么递归是这道题的“天选解法”递归的核心思路可以这样理解不要直接想“怎么一口气把N个盘子从A搬到C”而是定义一个带有“中转信息”的任务——把n个盘子从起点柱子搬到终点柱子中间借助一根中转柱子。这个任务一旦定义好你只需要解决三件事把上面n减1个盘子搬到中转柱把最底下那个大盘子直接搬到终点柱再把中转柱上的n减1个盘子搬到终点柱。这三件事里“把n减1个盘子搬过去”这件事的结构和原问题一模一样只是规模缩小了1而且起点、终点、中转的角色变了。这样一层一层缩小下去直到n等于1时直接搬一个盘子就行。这就是标准的递归解体结构自相似、规模递减、有基例。为什么说递归是“天选”因为汉诺塔最麻烦的地方在于“不能破坏大盘压小盘的规则”而递归通过“先把上面的n减1个清走”这个动作天然保证了大号盘子出发时顶部是空的到达时目标柱上要么是空、要么只有更大的盘子。你完全不需要在代码里维护“当前每根柱子上有哪些盘子”的全局状态递归替你处理了这些约束。这就是它优雅的地方几行代码就能描述一个指数级别复杂的搬移过程。2. 递归三步法从抽象思路到能跑的代码2.1 把递归函数读成一句话参数顺序就不会乱递归代码里最容犯糊涂的就是参数顺序。我自己的习惯是先给函数一个明确的语义注释再写代码。定义一个函数def hanoi(n, src, dst, aux): 把 n 个盘子从 src 柱子搬到 dst 柱子 aux 柱子作为中转。 if n 1: print(fMove disk 1 from {src} to {dst}) return hanoi(n - 1, src, aux, dst) # 第一步n-1 个盘子从 src 挪到 auxdst 当中转 print(fMove disk {n} from {src} to {dst}) # 第二步最大的盘直接到 dst hanoi(n - 1, aux, dst, src) # 第三步aux 上的 n-1 个盘子再搬到 dstsrc 当中转写这段代码时我建议你把hanoi(n, src, dst, aux)这段话在心里默念一遍“把n个盘子从src搬到dst允许用aux做中转”。然后你再去看递归调用比如第一步写成hanoi(n - 1, src, aux, dst)意思就是“把n减1个盘子从src搬到aux中转柱是dst”。参数顺序不是靠记而是靠语义推导。这个习惯能帮你绕开一大半参数错乱的问题。调用方式很简单hanoi(3, A, C, B)表示3个盘子从A搬到CB作中转。运行后你会看到7行移动记录正好是3个盘子的最少步数。如果你想真正看到“盘子移动”而不是只有打印可以把print换成真实的数据结构操作。用三个列表模拟三根柱子列表尾部是柱子顶部def hanoi_with_rods(n, src, dst, aux, rods): if n 1: disk rods[src].pop() rods[dst].append(disk) print(fMove disk {disk}: {src} - {dst}) return hanoi_with_rods(n - 1, src, aux, dst, rods) disk rods[src].pop() rods[dst].append(disk) print(fMove disk {disk}: {src} - {dst}) hanoi_with_rods(n - 1, aux, dst, src, rods) rods {A: list(range(5, 0, -1)), B: [], C: []} hanoi_with_rods(5, A, C, B, rods)这种版本我推荐新手跑一次观察三根柱子的状态变化比单纯打印直观得多。2.2 3个盘子完整手推把调用栈摊开看这一步是理解递归的关键。我当初卡了很久就是因为光看代码想不通“到底先移哪个、后移哪个”。解决办法只有一个拿3个盘子把调用过程一步一步手推出来。下面是最小规模的展开hanoi(3, A, C, B) ├── hanoi(2, A, B, C) │ ├── hanoi(1, A, C, B) → Move disk 1: A - C │ ├── Move disk 2: A - B │ └── hanoi(1, C, B, A) → Move disk 1: C - B ├── Move disk 3: A - C └── hanoi(2, B, C, A) ├── hanoi(1, B, A, C) → Move disk 1: B - A ├── Move disk 2: B - C └── hanoi(1, A, C, B) → Move disk 1: A - C对应的完整移动序列是A到C、A到B、C到B、A到C、B到A、B到C、A到C一共7步和2的3次方减1完全吻合。看这个展开图时最容易晕的是hanoi(1, A, C, B)这种调用。记住当n等于1时函数直接打印“从src到dst”完全不管aux是谁。所以hanoi(1, A, C, B)就是“1号盘从A搬到C”而hanoi(1, B, A, C)就是“1号盘从B搬到A”。把“参数名”和“盘号”分开看不要混在一起追踪起来就清爽多了。你还会发现一个规律递归树里的“移动大盘子”的打印永远出现在两次递归调用之间。这在树的术语里叫中序遍历——左子树、根节点、右子树。汉诺塔的整个移动序列其实就是这棵递归树的中序遍历结果。这个视角对理解“递归顺序”很有帮助。2.3 高频错误自查先把这三个坑绕过去我见过很多人包括我自己在写汉诺塔时踩坑最常见的有三个。第一个坑基例里忘记写return。当n等于1时打印完盘子后程序还会继续往下走执行hanoi(n - 1, src, aux, dst)也就是传入n等于0甚至负数导致无限递归最后撑爆调用栈报RecursionError。基例必须既“处理结果”又“结束本次调用”。第二个坑递归调用时参数顺序写反。比如有人会把第一步写成hanoi(n - 1, src, dst, aux)那语义就变成“把n减1个盘子从src搬到dstaux当中转”——这和你的目标完全不是一回事跑出来的移动序列会乱套。每次写递归调用前心里默念一遍函数语义就不会搞错。第三个坑把“移动最大盘的打印”放在了递归调用之前。正确顺序必须是“先把n减1个盘挪走再移动最大盘最后把n减1个盘挪回来”。如果提前打印移动大号盘输出步骤数可能还是那个数量级但盘子的位置规则会被打破序列并不合法。自查方法很简单跑n等于3人工检查每一步是否符合“大盘不能压小盘”并且确认总步数等于7。如果步数不对多半是参数顺序问题如果规则被破坏多半是打印顺序问题。3. 复杂度与64阶汉诺塔指数爆炸的直观冲击3.1 移动步数递推式T(n)2^n减1是怎么推出来的汉诺塔的步数有个非常漂亮的递推公式。设T(n)表示把n个盘子从一根柱子搬到另一根柱子所需的最少步数那么T(1)等于1。对于n大于等于2的情况整个过程拆成三块先移动n减1个盘子到中转柱要花T(n减1)步再把最大的盘子直接搬到目标柱花1步最后把n减1个盘子从中转柱搬到目标柱又花T(n减1)步。所以递推式写成T(n) 2乘以T(n减1)加1。这个递推式的解很好求。把两边都加1得到T(n)加1 2乘以(T(n减1)加1)。也就是说T(n)加1本身构成了一个首项为T(1)加1等于2、公比为2的等比数列所以T(n)加1等于2的n次方最终T(n)等于2^n减1。具体数值可以感受一下n等于1时1步n等于2时3步n等于3时7步n等于4时15步n等于5时31步n等于10时就到1023步了。注意这个增长速度每多一个盘子步数翻倍再加1。这就是指数增长前期看着温和后期直接起飞。3.2 64阶汉诺塔到底要多少年算给你看网上流传着一个经典传说梵天创造世界时在一根柱子上放了64片金盘僧侣们按照汉诺塔的规则日夜不停地搬运当所有盘子都移到另一根柱子上的那一刻世界将在一声霹雳中毁灭。这个故事很唬人但你真去算一下64阶汉诺塔的步数就会发现所谓的“世界末日”远得离谱。n等于64时总步数T(64)等于2的64次方减1也就是18,446,744,073,709,551,615步大约1.8446744乘以10的19次方。假设僧侣每秒移动一个盘子换算成年份的话1.8446744乘以10的19次方秒除以每年约3.156乘以10的7次方秒约等于5.846乘以10的11次方年也就是大约5850亿年。你知道宇宙年龄才138亿年左右吗这个数字是宇宙年龄的40多倍。哪怕每秒能移动10亿个盘子也要大约585年才能跑完。也就是说这个故事里的“世界末日”在物理上比太阳的寿命还长得多得多。我给个更直观的对比如果你每秒手动移一个盘子连续不停地搬从宇宙大爆炸搬到现在也只完成了大约2的38次方步。64阶汉诺塔需要的步数是彻底超出人类经验尺度的数字。所以“64阶汉诺塔跑不完”不是算法不行而是问题本身要求输出的步骤数量就天文数字级别换成任何编程语言、任何机器都无解。3.3 递归深度和时间复杂度别搞混有个容易混淆的点64阶汉诺塔递归调用层数其实只有64层不是2的64次方层。递归深度指的是“同时存在多少层函数调用”因为在递归链中每向下调一层上一层并没有返回所以最深时会同时存在n个未返回的调用帧。n等于64时深度就是64这在绝大多数编程语言里完全没问题Python默认递归深度限制是100064远远不到。真正吓人的是时间复杂度。总执行步骤是2^n时间上完完全全的指数爆炸。所以64阶汉诺塔的瓶颈从来不是递归深度而是总步骤数本身。递归深度决定“会不会爆栈”时间复杂度决定“要跑多久”两者是不同维度的问题。如果硬要跑更大的n比如n等于2000递归深度会先撞上Python默认的1000层限制报RecursionError。用sys.setrecursionlimit把限制调高后程序又会因为步骤数指数增长而跑到死循环一样停不下来。简单说汉诺塔问题在n比较小的时候比如n小于20非常适合演示递归再往上就只能讨论数学意义没法实际执行。4. 不走递归的汉诺塔二进制规律与显式栈模拟4.1 第i步移动几号盘看二进制的lowbit汉诺塔的移动序列里藏着一个非常有意思的二进制规律第k步移动的盘子编号等于k的二进制表示中最低位的1所在的位置加1。也就是说你只需要算出k的二进制里最低位那个1在哪一位就能知道这一步轮到几号盘动。Python里可以用位运算快速得到这个编号def disk_to_move(step): return (step -step).bit_length()它的原理是step -step能取出step二进制中最低位的1对应的数值再用bit_length()取这个数值的二进制位数。比如step等于3时最低位的1在第0位3 -3等于1bit_length()等于1代表1号盘step等于4时4 -4等于4bit_length()等于3代表3号盘。用n等于3的7步来验证步数1二进制001移1号盘步数2二进制010移2号盘步数3二进制011移1号盘步数4二进制100移3号盘步数5二进制101移1号盘步数6二进制110移2号盘步数7二进制111移1号盘。得到的盘号序列是1、2、1、3、1、2、1和前文手推的移动序列完全一致。移动方向也有规律当n为奇数时最小盘沿“源柱、目标柱、中转柱”的顺序循环移动当n为偶数时最小盘沿“源柱、中转柱、目标柱”的顺序循环移动。其余盘子的方向不需要记忆因为它不能放在更小的盘子上所以合法方向通常只有一个。这个规律很多人面试时会遇到属于“递归地推汉诺塔”之外的加分项。4.2 用显式栈重写递归理解系统调用栈的压栈弹栈如果面试官追问“能不能不用递归实现汉诺塔”或者你想加深对调用栈的理解可以用显式栈模拟系统递归。思路很直接把每次函数调用的参数打包成一个元组扔进自己的栈里模拟系统自动完成的压栈、弹栈。def hanoi_stack(n, src, dst, aux): # 元组结构n, src, dst, aux, 阶段标记 stack [(n, src, dst, aux, expand)] while stack: n, src, dst, aux, phase stack.pop() if n 1: print(fMove disk 1 from {src} to {dst}) elif phase expand: # 注意压栈顺序与递归执行顺序相反 stack.append((n, src, dst, aux, move)) stack.append((n - 1, aux, dst, src, expand)) stack.append((n - 1, src, aux, dst, expand)) else: print(fMove disk {n} from {src} to {dst})这段代码的核心在于压栈顺序。系统栈是后进先出所以为了让hanoi(n - 1, src, aux, dst)先执行你必须最后压它。把“expand”阶段当作“继续展开递归”把“move”阶段当作“执行移动最大盘的打印”就能完全复刻原来的递归效果。这个版本的执行结果和递归版一模一样但它不依赖系统调用栈适合在递归深度受限、或你想看清“压栈弹栈到底发生了什么”的场景。运行一次n等于3的例子观察stack的变化你会对递归本质有非常直观的体会。4.3 递归vs迭代什么场景才值得换写法看到这里你可能会问既然有二进制规律和显式栈是不是以后写汉诺塔就不要用递归了我的答案很明确不需要。汉诺塔递归版的可读性远高于迭代版几行代码就表达了“递次缩小问题规模”的核心思想别人一看就懂。而二进制规律更多是数学趣味显式栈版本更多是教学工具它们的价值在于帮你理解递归而不是取代递归。真正需要换写法的场景是某个问题本质上可以用递归解决但递归深度可能非常大比如遍历一棵特别深的树时系统调用栈可能不够用。这时候改成显式栈迭代才能在不爆栈的情况下完成任务。工程上的原则是“优先用递归保证代码清晰遇到栈溢出再考虑迭代”。5. 学递归的三个私房技巧与复盘体会5.1 别背代码背“语义”我见过太多人背汉诺塔的代码模板换个参数名就不会写了。这没用。你真正要记的只有一句话hanoi(n, src, dst, aux)的意思是“把n个盘子从src搬到dst用aux中转”。无论递归调用怎么变化你只要套这个语义参数顺序自然就对了。具体做法是拿到任意递归函数先给它写一行“语义注释”再动笔写代码。汉诺塔只有三行核心逻辑但很多人写错就是因为没有先定义清楚这个函数的“契约”。一旦定义清楚了后面所有的递归调用都是对这个契约的机械套用。5.2 手画一次调用树之后都不用再翻代码我强烈建议新手花10分钟用纸笔把n等于3的汉诺塔调用树完整画一遍就像2.2节那样。画的时候不要看代码只凭语义推hanoi(3, A, C, B)先调用了什么、打印了什么、又调用了什么。画完一次你就形成了对“递归先深入再回溯”的肌肉记忆。之后再遇到任何递归算法比如二叉树遍历、快速排序、斐波那契你都可以在脑中自动展开调用树而不是靠死记。这一步练习的回报率极高只花一顿午饭的时间却能把递归从“玄学”变成“机械操作”。5.3 能口头讲明白才算真正会了检验自己是否真的理解递归我有一个简单粗暴的标准不看代码把汉诺塔的过程讲给另一个人听。如果你能说出“n个盘子先把上面n减1个搬到中转柱再搬最大的最后把中转柱上的n减1个搬到目标柱”并且能回答对方“那中转柱是哪根”这种追问说明你抓住了递归的精髓。按照我个人的复盘经验汉诺塔这道题最大的价值不在于“能写出能跑的代码”而在于它让我第一次真切感受到递归是“把复杂问题化简成更小的同样问题”的一种思维方式。看再多的讲解不如自己推演一遍、讲一遍。把那层窗户纸捅破之后后面再学树的遍历、回溯算法、动态规划都会顺很多。这也是为什么我会把这份笔记整理出来——它是我真正学会递归的一座里程碑。