如果你正在刷Java面试题或者刚学到递归这一章大概率会碰到汉诺塔。这题看起来人畜无害三根柱子、几块圆盘、一条“大盘不能压小盘”的规则但真上手写代码时很多人会卡住。更扎心的是前三天我一直没搞懂盯着IDE里那几行递归自我怀疑。直到第四天我才反应过来问题不在代码而在“我用错了理解方式”。这篇博文就聊聊四个盘子的汉诺塔它为什么能卡住人以及我用Java把它彻底想明白的过程。文中会给出可复制的Java实现拆解递归调用过程顺便讲讲面试里常追问的顺时针变体和几个容易踩的坑。适合刚学递归的Java初学者也适合准备校招、社招正在复习算法基础的朋友。1. 为什么四个盘子会让这么多人卡住1.1 汉诺塔问题的本质汉诺塔的规则只有三条一次只能移动一个盘子每次移动只能取某根柱子最顶上的盘子任何时刻大盘子不能压在小盘子上面。目标是把A柱上从小到大叠好的n个盘子整体搬到B柱C柱作为辅助。这个问题的经典解法是递归递归逻辑用一句话可以概括要搬n个盘子先搬走压在底部的n-1个把第n个大盘子直接移到目标柱再把n-1个搬回来。我最初不理解的是那n-1个盘子该怎么搬答案是继续递归——再把它们当作新的“n-1问题”处理直到n1直接搬。很多人卡住的地方就在这里递归函数像俄罗斯套娃一个套一个你总觉得自己漏掉了哪一步。而四个盘子恰好是一个临界点。1.2 四个盘子是“手算”和“递归”的分水岭两个盘子的汉诺塔手动推一遍只需要3步小学生拿积木都能推出来。三个盘子是7步花点耐心也能推。四个盘子就不同了完整的移动序列是15步。有人会想不就15步吗我一步一步模拟不就好了坏就坏在“一步一步模拟”上。人的工作记忆大概能同时容纳4±2个信息单元。三个盘子时你能勉强在脑子里跟踪每一步四个盘子时递归调用深度变成4层还要记住每层的起点、终点、辅助柱再加上当前正在执行哪一步工作记忆瞬间超载。我前三天就是这么被卡住的——不停地在纸上画每一步画到第7步就乱了然后从头再来。如果你和我一样问题不是笨而是引入了一个错误的前提以为“理解”等于“能手动跟踪每一步”。实际上递归这类问题的正确理解方式是“把子问题打包信任递归帮你完成”。2. 先用Java把解法写出来2.1 最简递归实现先上一版最经典的Java解法几乎所有教材和面试答案都是这个结构public class Hanoi { /** * 把 n 个盘子从 from 柱子移动到 to 柱子借助 helper 柱子 */ public static void move(int n, char from, char to, char helper) { if (n 1) { System.out.println(把盘子 1 从 from 移动到 to); return; } // 第一步把上面的 n-1 个盘子从 from 搬到 helper借助 to move(n - 1, from, helper, to); // 第二步把最大的第 n 个盘子从 from 搬到 to System.out.println(把盘子 n 从 from 移动到 to); // 第三步把 helper 上的 n-1 个盘子搬到 to借助 from move(n - 1, helper, to, from); } public static void main(String[] args) { move(4, A, B, C); } }运行这段代码控制台会打印出从A移到B的完整15步。这里我用A、B、C代表三根柱子其中A是起始柱B是目标柱C是辅助柱。如果你想从A移到C只要把参数改成move(4, A, C, B)就行。2.2 代码做了什么以四个盘子为例我们手动过一遍move(4, A, B, C)的执行流程第一层调用n4不满足n1于是先执行move(3, A, C, B)。注意这次调用里参数发生了轮换目标柱变成C辅助柱变成B。这实际上是把“上面3个盘子从A搬到C”这个子问题交出去了。等这个子问题全部递归返回后第一层才打印“把盘子4从A移动到B”。然后继续执行move(3, C, B, A)把C上的3个盘子搬到B。所以从函数执行的角度看代码只有三件事把上面n-1个搬走把第n个搬过去把n-1个搬回来。至于“怎么搬”这件事递归函数内部的调用自己会处理不用外面操心。如果你第一次写这个代码很容易犯一个错误把递归调用里三个参数的顺序抄错。比如写成move(n - 1, from, to, helper)这样做会把小盘子先搬到目标柱逻辑直接乱掉。核心记忆法是每一次递归调用都有一个柱子当“起点”一个柱子当“终点”一个柱子当“临时借用的辅助”三者永远是三个不同的柱子。3. 拆解调用过程到底是谁在搬盘子3.1 从“单线程跟踪”转向“栈帧视角”Java虚拟机在执行递归时每次方法调用都会创建一个新的栈帧Stack Frame里面保存这个调用的参数、局部变量和返回地址。递归深度有多少层JVM栈里就有多少个栈帧。很多人看递归代码感到头晕是因为脑子里只有一个“执行指针”试图从头到尾线性地跟完整个流程。但递归不是线性的它是一棵树。以四个盘子为例move(4)会调用move(3)move(3)又会调用move(2)move(2)再调用move(1)直到最底层打印移动步骤后才开始一层一层地往上返回。我用文本把调用关系想象出来大概是这样的move(4, A, B, C) ├── move(3, A, C, B) │ ├── move(2, A, B, C) │ │ ├── move(1, A, C, B) → A→C │ │ ├── 打印 A→B │ │ └── move(1, C, B, A) → C→B │ ├── 打印 A→C │ └── move(2, B, C, A) │ ├── move(1, B, A, C) → B→A │ ├── 打印 B→C │ └── move(1, A, C, B) → A→C ├── 打印 A→B └── move(3, C, B, A) ├── move(2, C, A, B) │ ├── move(1, C, B, A) → C→B │ ├── 打印 C→A │ └── move(1, B, A, C) → B→A ├── 打印 C→B └── move(2, A, B, C) ├── move(1, A, C, B) → A→C ├── 打印 A→B └── move(1, C, B, A) → C→B看完这棵树你就能明白“递归调用本质是深度优先遍历”这句话是什么意思。程序会一直往下钻到最深的那个move(1)打印第一步然后返回上一层再打印第二步再进入另一个分支。整个执行过程不是一根直线而是一棵二叉树的后序遍历。3.2 四个盘子的完整移动路径用上面的Java程序跑一遍得到的输出是这样的把盘子 1 从 A 移动到 C 把盘子 2 从 A 移动到 B 把盘子 1 从 C 移动到 B 把盘子 3 从 A 移动到 C 把盘子 1 从 B 移动到 A 把盘子 2 从 B 移动到 C 把盘子 1 从 A 移动到 C 把盘子 4 从 A 移动到 B 把盘子 1 从 C 移动到 B 把盘子 2 从 C 移动到 A 把盘子 1 从 B 移动到 A 把盘子 3 从 C 移动到 B 把盘子 1 从 A 移动到 C 把盘子 2 从 A 移动到 B 把盘子 1 从 C 移动到 B如果你在纸上画三个柱子按这15步实际操作一遍会发现所有步骤都是合法的每次移动的都是某根柱子最顶上的盘子而且没有任何大盘压小盘的情况。这里有个细节很多人没注意第8步是“把盘子4从A移动到B”恰好是整个序列的中点。在此之前所有操作都是在“清空A柱上的所有障碍”在这之后所有操作都是在“把C柱上的3个盘子归位到B柱”。所以第8步之前和之后是两个完全对称的“三盘子汉诺塔”问题。这就是汉诺塔递归的核心美感四盘子问题 三盘子问题 移动最大盘 三盘子问题。而三盘子问题又可以继续拆下去直到变成最简单的一盘子问题。3.3 为什么2^n - 1步是精确下界四个盘子是15步三个盘子是7步两个盘子是3步。如果你试过会发现一个规律n个盘子的最少移动步数总是2^n - 1。这个结论可以严格证明。设T(n)为搬n个盘子所需的最少步数。搬n个盘子前必须先把上面n-1个盘子全部挪到辅助柱这至少需要T(n-1)步然后把最大的盘子从A移到B这是1步最后把n-1个盘子从辅助柱挪回目标柱又至少需要T(n-1)步。因此T(n) 2 * T(n-1) 1而递归解法恰好做到了这个下界所以T(n) 2 * T(n-1) 1。初始条件T(1) 1解这个递推式得到T(n) 2^n - 1。看到这个指数增长你就能理解为什么“手动跟踪”四个盘子会崩第n个盘子需要2^(n-1)步才能被移动一次到第4个盘子时前面已经有7步“前戏”了。数字一大大脑缓存就不够用了。我还想提一个空间复杂度的问题。虽然总步数是2^n但递归深度只有n所以JVM栈上最多同时存在n个栈帧。也就是说这个算法的空间复杂度是O(n)不是O(2^n)。很多面试官问递归“会不会栈溢出”答案是n稍微大一点比如32理论上没问题但n到几千上万时栈帧堆积会撑爆JVM默认栈大小这才是栈溢出的真正原因。平时练习和面试中n是两位数时性能完全不是问题。4. 常见变形顺时针汉诺塔与Java实现差异4.1 顺时针规则是什么教条版本的汉诺塔盘子在A、B、C三根柱子之间可以任意方向移动。但有些面试官喜欢加一个限制所有移动必须按顺时针方向进行。换句话说允许的移动序列只能是 A→C、C→B、B→A逆时针方向如A→B、B→C、C→A是不允许的。这类“顺时针汉诺塔”在LeetCode讨论区和一些Java面试八股文里都能看到。它考的不是你会不会背递归模板而是你能不能理解当移动方向受限制时递归的“中转策略”也会跟着变。怎么理解这个限制把三根柱子摆成一个三角形顺时针就是沿三角形的一个方向走。原来你可以直接把盘子从A搬到B现在这一步被禁止了想从A到B只能先到C再到B多绕一步。这个限制会直接影响递归过程中“谁当辅助柱”的选择。4.2 顺时针版本的Java改造限制顺时针之后代码不能直接沿用原版因为原版里可能出现从A直接到B、从B直接到C这类“逆时针步”。一个可行的思路是调整递归分解方式当搬n个盘子从起点到终点时如果目标方向不是顺时针的下一个柱子就先把它搬到辅助柱再搬到底。下面是我写得比较顺的一个版本供参考public class ClockwiseHanoi { /** * 按顺时针规则搬运合法移动只允许 A-C, C-B, B-A */ public static void moveClockwise(int n, char from, char to, char helper) { if (n 1) { // 如果目标柱正好是顺时针下一柱直接移动 if (isClockwise(from, to)) { System.out.println(把盘子 1 从 from 移动到 to); } else { // 否则先移到辅助柱再移到目标柱 System.out.println(把盘子 1 从 from 移动到 helper); System.out.println(把盘子 1 从 helper 移动到 to); } return; } // 先把上面 n-1 个盘子从 from 移到 helper moveClockwise(n - 1, from, helper, to); // 把第 n 个盘子从 from 移到 to如果需要绕路就绕路 if (isClockwise(from, to)) { System.out.println(把盘子 n 从 from 移动到 to); } else { System.out.println(把盘子 n 从 from 移动到 helper); System.out.println(把盘子 n 从 helper 移动到 to); } // 再把 n-1 个盘子从 helper 移到 to moveClockwise(n - 1, helper, to, from); } private static boolean isClockwise(char from, char to) { return (from A to C) || (from C to B) || (from B to A); } public static void main(String[] args) { moveClockwise(4, A, B, C); } }注意这段代码在n1时不再只是简单移动因为即使只有一个盘子如果起点到目标点不是顺时针方向也需要先借道辅助柱才能完成相当于把一步拆成两步。用四个盘子跑这个版本步数会比普通版多这是方向限制带来的必然代价。4.3 面试中常见的追问面试官在遇到你写出标准递归解法后通常会加问几个变体顺时针只是其中一个。我整理过几个常见的追问方向如果三根柱子的限制是“每次只能移动最上面的盘子且只有A和B相邻、B和C相邻、A和C不相邻”怎么办如果要求打印“第k步移动的是哪个盘子”怎么做汉诺塔和二进制有没有联系为什么第n步永远在移动最大的那个盘子能不能非递归实现用栈模拟递归过程或者用二进制规律直接生成移动步骤。最后一个问题挺有意思。n个盘子的汉诺塔第k步移动的盘子编号可以通过二进制运算算出来移动方向也有规律。具体来说k从1到2^n - 1最低位的1出现在第几位这次移动的就是第几个盘子。这个规律用Java写出来不超过十行public static void hanoiByBinary(int n, char from, char to) { // 按 1~2^n-1 的顺序模拟打印每一步 for (int step 1; step (1 n); step) { int disk Integer.numberOfTrailingZeros(step) 1; char source ((step step - 1) % 3 0) ? from : to; // 这里有多种方向映射写法核心是利用奇偶性判断移动方向 System.out.println(第 step 步移动盘子 disk); } }不过说实话非递归版本背下来意义不大面试时真正想考察的还是你懂不懂递归分解的思维。二进制解法最多作为课外延伸聊一聊不必刻意背。5. 踩坑记录与排查技巧5.1 递归参数顺序错乱我见过最多的错误是把move(n - 1, from, helper, to)里的from、helper、to顺序搞混。尤其当三个参数都是char类型时编译器不会报错程序也能运行但输出结果全乱。排查方法很简单只跑move(2, A, B, C)手动验证一下。2个盘子正确的输出应该是把盘子 1 从 A 移动到 C 把盘子 2 从 A 移动到 B 把盘子 1 从 C 移动到 B如果你的程序连这个最简单的场景都输出不对那就是递归参数顺序错了。先修小规模再跑大规模这是最有效的定位方式。5.2 输出乱码与控制台编码用System.out.println输出中文时Windows命令行经常出现乱码。这不是算法问题是控制台编码和Java默认字符集不一致导致的。我遇到过不少人在IntelliJ IDEA里跑得好好的一拿到命令行就乱码。解决办法有几个一是把输出内容改成英文比如Moving disk 1 from A to C二是设置JVM编码参数-Dfile.encodingUTF-8三是在IDEA的Help菜单里修改VM options。如果只是自己学习用改成英文最省事毕竟面试时你用英文输出也没有任何问题。5.3 栈溢出是什么时候开始的有人写汉诺塔时会担心n一大递归栈会不会炸。理论上默认JVM栈大小在1MB左右一个栈帧大约占几十到几百字节递归到几千层是安全的。所以n1000以内汉诺塔不会栈溢出。真正会栈溢出的是你无限递归比如递归出口写错成if (n 0)而调用时传的是正数永远等不到n0。或者你把n - 1写成了n导致递归无限循环。这种错误很难一眼看出来因为代码结构完全正常但输出会无限刷屏直到StackOverflowError。排查技巧是在递归函数开头加一行计数器打印当前调用深度。如果深度一直增长不回落说明递归没有收敛。实际写完代码后这一步能省下大量调试时间。5.4 只背代码不懂过程面试会露馅我见过一些同学汉诺塔代码背得滚瓜烂熟面试官一追问“第四步在干嘛”就答不上来。这类问题考察的不是记忆力而是对递归过程的真正理解。我的建议是写代码时故意把move(4, A, B, C)改成move(4, A, C, B)观察输出变化再改成move(3, B, C, A)手动推一遍前几步。多改几次参数后你会自然理解每个参数的实际作用而不是机械地套模板。特别是四个盘子这个规模输出15步不长不短非常适合做这种“改参实验”。6. 从汉诺塔到其他算法题它到底在训练什么很多人把汉诺塔当成一道孤立的面试题背完就忘。实际上它训练的是递归问题的通用拆解能力。后面你会学到的归并排序、二叉树遍历、快速排序、斐波那契数列甚至回溯算法里的全排列核心都是“把大问题拆成同类小问题”。以归并排序为例mergeSort(arr, left, right)的写法是把数组从中间切开递归排左半边递归排右半边最后合并。这和汉诺塔的move(n-1)、移动最大盘、再move(n-1)的结构几乎一样都是先处理子问题再处理当前层最后再处理另一个子问题。二叉树的前序遍历就更直白了void preorder(TreeNode root) { if (root null) return; visit(root); preorder(root.left); preorder(root.right); }这个递归结构和汉诺塔一模一样先访问当前节点再递归左子树再递归右子树。理解了汉诺塔里“递归调用自己两次”的执行顺序再看二叉树的遍历代码几乎不需要额外学习成本。另外汉诺塔也是理解“分治”思想的一个极好入口。分治的关键不是“怎么分”而是“分完怎么合”。汉诺塔里最大的盘子是“合”的锚点所有子问题都围绕它展开。这种“确定一个关键节点左右分别处理”的模式在后缀表达式求值、括号生成、表达式树构造等题目里随处可见。再往远了说汉诺塔里的递归和栈帧概念还关系到你对JVM执行模型的理解。很多人搞不懂Java方法调用时JVM栈里发生了什么通过调试汉诺塔一步步查看栈帧的创建和销毁会有非常直观的感受。IDEA里打断点之后你会看到每次递归进入时栈帧数量增加返回时栈帧消失这种“看得见”的体验比看十篇博客都管用。我在实际学习中的体会是汉诺塔这道题真正的价值不在“会写”而在“能讲”。如果你能对着四个盘子说清楚每一层递归在干什么为什么第8步才移动最大盘为什么总步数是15那你对递归的理解就已经超越了大多数人。后面再遇到更复杂的递归题目心态会完全不一样。别再死盯着那15步硬背了放下“手动模拟每一步”的执念用栈帧和子问题的视角去看它最多一天就能彻底通透。