汉诺塔这玩意儿，学编程的十有八九都遇到过。我当年第一次看汉诺塔递归算法的时候，脑袋里全是浆糊，什么A柱B柱C柱，什么大盘子不能压小盘子，看着代码倒是不长，但就是搞不懂它咋就自己动起来了。后来自己手推了好几遍，又踩了不少坑，才算真正弄明白。今天咱就抛开那些绕来绕去的官方定义，用大白话把汉诺塔递归算法这事聊透，你看完再上手敲两遍，基本就稳了。
汉诺塔到底是个啥问题
先简单说下背景，不然没接触过的朋友可能直接懵。汉诺塔（也叫河内塔）是个老游戏，有三根柱子，一根柱子上从下往上按从大到小叠了一摞盘子。目标是把整摞盘子挪到另一根柱子上，规矩就两条：一次只能动一个盘子，而且大盘子永远不能压在小盘子上面。听起来简单吧？盘子一多，手动挪就懵了。而汉诺塔递归算法，就是计算机解决这个问题的经典思路。
很多人一开始想用循环硬解，比如三个盘子还好，四个五个就开始乱套了。其实汉诺塔这问题天生就是递归的料，因为它可以把大问题拆成同样规则的小问题。啥意思呢？比如说你有n个盘子要挪到目标柱，那你能不能先把上面n-1个盘子挪到中间那根柱子上？然后最底下那个大盘子直接挪到目标柱？最后再把那n-1个盘子从中间柱子挪到目标柱？你看，这不就把一个n的问题拆成了两个n-1的问题嘛。递归这东西，本质上就是自己调用自己，把问题规模一步步缩小，缩到只剩一个盘子的时候，直接挪就完事了。
代码到底咋写，一行行拆给你看
光说理论没用，咱直接上代码。下面这段是C语言版的汉诺塔递归实现，网上各种语言写法都差不多，逻辑核心就这几行：
void hanoi(int n, char A, char B, char C) {
if (n == 1) {
printf("把盘子从 %c 移到 %c\n", A, C);
return;
}
hanoi(n - 1, A, C, B);
printf("把盘子从 %c 移到 %c\n", A, C);
hanoi(n - 1, B, A, C);
}我第一次看这代码的时候，心里直犯嘀咕：这不就三步吗？咋就能解决所有盘子？其实你仔细捋一下就行。假设n=3，程序会先执行hanoi(2, A, C, B)，注意这里参数顺序变了，意思是要把两个盘子从A借助C挪到B。进去之后，又执行hanoi(1, A, B, C)，这时候n等于1了，直接打印从A移到C。然后回到上一层，打印从A移到B。再执行hanoi(1, C, A, B)，打印从C移到B。你看，这就把上面两个盘子成功挪到B柱上了。接着回到最外层，打印从A移到C，也就是把最大的那个盘子挪到目标柱。最后再执行hanoi(2, B, A, C)，用同样的方式把B上的两个盘子挪到C上。整个过程你拿笔在纸上画一画，跟着代码走一遍，绝对能通。
递归的坑，我替你们踩过了
敲代码的时候有几个地方特别容易出错。第一个就是参数顺序搞混。汉诺塔递归函数那三个参数，代表的可不是固定的柱子，而是“源柱”、“借助柱”、“目标柱”。每次递归调用的时候，它们的角色都在变。你要是死记硬背A是源柱C是目标柱，那代码一跑就乱套。第二个坑就是忘记写递归终止条件。没有那个if (n == 1)，函数就会无限调用自己，最后栈溢出崩掉。刚开始学的时候，我就犯过这毛病，还纳闷程序咋没反应，其实控制台早就刷屏了。
还有个容易忽略的点是移动次数的计算。n个盘子的汉诺塔，最少需要2的n次方减1步。这个公式你可以自己验证一下，1个盘子1步，2个盘子3步，3个盘子7步。用递归写的话，你会发现这个次数天然就是对的，因为递归本身就是按这个逻辑展开的。有时候面试官会问这个，你直接说公式就行，但最好也能解释清楚为什么。
汉诺塔递归的实用价值
可能有人问，学这玩意儿除了应付作业和面试，还有啥用？说实话，实用性确实不直接，但它是理解递归思想的一个超级经典的入门例子。递归在编程里用得特别多，比如树的遍历、快速排序、文件目录扫描，底层思路跟汉诺塔递归算法是一模一样的。你把汉诺塔搞明白了，以后再遇到那种“自己调用自己”的代码，心里就有底了。
另外，汉诺塔还能帮你练脑子。比如你可以试试不用递归，纯用循环和栈来模拟这个过程，那对数据结构的理解要求就更高了。我当初就试过用栈手动模拟汉诺塔递归算法，搞了一下午才弄对，但弄完以后对递归和栈的理解直接上了一个台阶。你要是学有余力，不妨也试试。
多语言版本对照，挑你熟的看
有些朋友可能不写C，我把Python版也贴出来，逻辑一模一样，就是语法有点差别。Python版写起来更简洁：
def hanoi(n, A, B, C):
if n == 1:
print(f"把盘子从 {A} 移到 {C}")
return
hanoi(n-1, A, C, B)
print(f"把盘子从 {A} 移到 {C}")
hanoi(n-1, B, A, C)你看，核心就那三行。Java版也差不多，无非是把printf换成System.out.println。所以我说，汉诺塔递归算法关键在于理解那三步的逻辑，而不是死背某种语言的语法。你用熟了以后，随便换语言都能几分钟写出来。我建议你拿到代码先别急着跑，自己拿张纸，画三根柱子，摆几个硬币当盘子，手动模拟一遍程序执行的过程。真的，这比你看十遍教程都有用。
还有个小技巧，调试的时候可以把盘子数设小一点，比如4个或者5个，然后在代码里加打印，看看每一步参数是怎么变的。我当时就是这么干的，打印出来以后一目了然，比光看代码瞎猜强得多。等你能预测出程序下一步会打印啥的时候，说明你基本就吃透汉诺塔递归算法了。
好了，关于汉诺塔递归算法就聊到这儿。这东西看再多遍不如自己动手敲一遍，你今天抽个十几分钟，照着上面的代码打一遍，再手动推演一遍，肯定比光收藏吃灰强。要是还有哪里卡住，欢迎在评论区留言，我看到就会回复。
喜欢 
顶
难过
囧
围观
无聊
