汉诺塔问题：递归思想的完美入门

汉诺塔，可以说是递归世界里最经典的入门题了。我第一次接触它是在大学的数据结构课上，当时觉得这玩意儿挺玄乎的——三个柱子，几个盘子，怎么就扯上递归了？后来工作后，在写文件系统遍历、目录树操作时，才真正体会到汉诺塔背后那个分治思想的威力。

说白了，汉诺塔问题就是：有三根柱子，A、B、C，A柱上有n个大小不等的盘子，按大小顺序叠放（大的在下，小的在上）。目标是把所有盘子从A移到C，过程中可以借助B，但每次只能移动一个盘子，且任何时候大盘子不能压在小盘子上。

嗯，规则很简单。但如果你试图用手动方式去推导每一步，n=3时还能应付，n=4就开始头晕，n=5以上基本就乱了。这时候，递归就派上用场了。

分治思想：把大问题拆成小问题

递归的核心，说白了就是四个字：分而治之。你不需要一次性解决整个问题，而是把它拆成更小的、结构相同的子问题。

对于汉诺塔，我们这样想：

• 如果只有一个盘子，直接把它从A移到C，完事。
• 如果有n个盘子，我们能不能先把上面n-1个盘子从A移到B？
• 然后把最底下那个最大的盘子从A移到C？
• 最后再把B上的n-1个盘子从B移到C？

你看，这样一拆，问题就变成了：移动n-1个盘子，而移动n-1个盘子又可以拆成移动n-2个盘子……直到拆成移动1个盘子。这就是递归的典型结构。

递归三步法：写代码的套路

我个人习惯把递归函数的编写总结成三步，汉诺塔正好拿来练手：

1. 定义递归函数：明确函数要做什么，参数是什么。比如 hanoi(n, from, to, aux) 表示把n个盘子从from柱移到to柱，借助aux柱。
2. 找终止条件：什么时候递归结束？n=1时，直接移动。
3. 写递归体：把问题拆成子问题，调用自身。

来，直接看代码：

#include <stdio.h>

// 递归函数：将n个盘子从from移到to，借助aux
void hanoi(int n, char from, char to, char aux) {
    // 终止条件：只有一个盘子，直接移动
    if (n == 1) {
        printf("移动盘子 1 从 %c 到 %c\n", from, to);
        return;
    }
    
    // 第一步：将上面 n-1 个盘子从 from 移到 aux，借助 to
    hanoi(n - 1, from, aux, to);
    
    // 第二步：将最大的盘子从 from 移到 to
    printf("移动盘子 %d 从 %c 到 %c\n", n, from, to);
    
    // 第三步：将 n-1 个盘子从 aux 移到 to，借助 from
    hanoi(n - 1, aux, to, from);
}

int main() {
    int n = 3;
    printf("汉诺塔 %d 个盘子的移动步骤：\n", n);
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

运行结果：

汉诺塔 3 个盘子的移动步骤：
移动盘子 1 从 A 到 C
移动盘子 2 从 A 到 B
移动盘子 1 从 C 到 B
移动盘子 3 从 A 到 C
移动盘子 1 从 B 到 A
移动盘子 2 从 B 到 C
移动盘子 1 从 A 到 C

你看，代码只有十几行，但背后蕴含的逻辑却非常强大。这就是递归的魅力——用简单的代码解决复杂的问题。

递归的执行过程：别试图跟踪每一层

很多初学者会犯一个错误：试图在脑子里模拟递归的每一步调用。我当年也干过这事，结果把自己绕晕了。

其实你不需要这样。你只需要相信：递归函数在逻辑上是正确的。只要你的终止条件写对了，递归体写对了，计算机就会帮你把每一步执行好。

打个比方：你让一个团队去完成一项任务，你只需要告诉组长「你负责把这件事拆成三件小事，每件小事再找三个人去干」，你不需要亲自盯着每个人怎么干活。递归函数就是那个组长，它负责拆任务，子任务由它自己（递归调用）去处理。

汉诺塔的数学本质：2ⁿ - 1

汉诺塔的移动次数有一个很漂亮的公式：移动n个盘子需要 2ⁿ - 1 步。

为什么会这样？我们来推导一下：

• n=1：1步 = 2¹ - 1
• n=2：3步 = 2² - 1
• n=3：7步 = 2³ - 1
• n=4：15步 = 2⁴ - 1

从递归的角度看，这个公式也很自然：移动n个盘子 = 移动n-1个盘子（两次）+ 移动1个盘子（一次）。设f(n)为移动次数，则：

f(n) = 2 * f(n-1) + 1

这个递推关系，解出来就是 f(n) = 2ⁿ - 1。

盘子数 n	最少步数	时间复杂度
1	1	O(1)
3	7	O(2³)
5	31	O(2⁵)
10	1023	O(2¹⁰)
20	1,048,575	O(2²⁰)
64	约 1.84 × 10¹⁹	O(2⁶⁴)

看到没？n=64时，步数已经是一个天文数字了。传说中僧侣们要移动64个金盘，按每秒移动一次算，需要约5849亿年才能完成。嗯，这个传说告诉我们两件事：一是递归的指数增长很可怕，二是递归的代码量不会因为问题规模变大而变复杂——64个盘子的代码和3个盘子的代码，几乎一模一样。

知识体系总览

下面这张图，帮你把汉诺塔问题的知识结构梳理清楚：

避坑指南：我踩过的那些坑

写递归，有几个地方特别容易出错。我把自己踩过的坑分享给你：

• 忘记终止条件：这是最常见的错误。没有终止条件，递归就会无限调用下去，最终栈溢出。我曾经有一次写递归时忘了写if判断，结果程序直接崩溃，排查了半天才发现。
• 参数传错顺序：汉诺塔的三个参数（from, to, aux）很容易搞混。我的习惯是：每次递归调用时，在纸上画一下三个柱子，标清楚哪个是源、哪个是目标、哪个是辅助，再写代码。
• 试图优化递归：有些同学觉得递归太慢，想用循环代替。对于汉诺塔，递归是最自然的解法，强行用循环反而会让代码变得极其复杂。记住：递归优先考虑可读性，性能优化是后面的事。

汉诺塔问题，说白了就是递归思想的一个完美缩影。它简单到只有几行代码，却又深刻到能让你理解分治、递归、栈这些核心概念。我个人觉得，把汉诺塔吃透了，后面再学快速排序、二叉树遍历、回溯算法，都会轻松很多。

嗯，递归的世界才刚刚开始。你准备好了吗？

---