😍从人脑思维出发：解决递归与汉诺塔

以汉诺塔问题为例，带你真正弄懂递归的本质

⚠️ 本文是Java语言：但递归的思想是相通的 其他语言的也可以来学习一下思路

---

🧐 先搞懂递归的灵魂

递归并不是什么"高大上"的概念，它的核心思想只有一条：

“大问题拆成完全一样的子问题，直到不能再拆为止”

拆完之后怎么解决？靠两条：

1. 子问题和原问题解法相同 — 用同一个方法，只是参数变小了
2. 有递归出口 — 没法再拆的时候，直接给出答案（不再调用自己）

听起来有点抽象？我们用汉诺塔来实操一遍 👇

---

🏗️ 汉诺塔问题描述

假设有 A、B、C 三根柱子。

初始状态：A 柱上从上到下叠着 n 个从小到大的盘子（A 最上是最小盘，A 最下是最大盘）
目标状态：把所有盘子移动到 C 柱上，B 可作为中转

规则：
  • 每次只能移动一个盘子
  • 大盘子不能压在小盘子上

---

🧠 人脑怎么想？

一开始别急着展开整个过程，那会"脑子爆炸"。

换个思路：先把最大的盘子甩一边，把上面的 n-1 个盘子当成一个整体

想象 A 柱是一整栋楼，最大盘在最底层。

我们的目标是：把这 n-1 层楼搬到 B 上，然后把最底层的大盘移到 C，最后再把 B 上的 n-1 层也移到 C 上。

递归的精髓就在这里：
👉 你不需要知道"怎么把 n-1 个盘子搬到 B 上"的具体步骤
👉 你只需要相信：这个函数 hanoi(n-1, ...) 就是干这个的！

这种"信任自己的函数"的豪气，是理解递归最关键的一步 😎

---

🔧 代码实现

全局保留了笔者的注释 虽然略显口语 但符合一般人的思考过程

public class Test {
    // 以3柱3盘为例 胎教级 解决 汉诺塔 问题
    // A B C 三个柱子 A上面从下到上是从大到小的盘子
    // 完成换柱 需要这么一步步的执行
    // a->c a->b c->b a->c b->a b->c a->c 最终移动到了C柱上
    // 需要7步
    // 多验证几个之后 发现 n 个盘子 需要 (2^n) - 1 次操作
    // 脑海里面不要去展开 数值大一点展开就崩溃了
    // 每一个塔都可以看作是最下面那个加上上面的所有 而每一次的移动你都需要借助一个中间位置
    // A柱上的塔放到C柱上
    public static int count = 0; // 定义这个变量看看 n == 1 被执行了几次

    public static void move(char posSrc, char posDest) {
        System.out.print(posSrc + "->" + posDest + " ");
    }

    //                              起始位置    中间位置    目标位置
    public static void hanoi(int n, char pos1, char pos2, char pos3) {
        if (n == 1) { // 2. 递归出口
            move(pos1, pos3); // 注意了: 这里是孤零零一个盘子从出发柱移动到目的柱子 而不是第一个位置移动到第三个柱子
            count++;
            return;
        } else {
            // 第一步:上面的 n-1 个 盘子放到 B 上  至于这一步怎么放的我先不管(就是要有这种豪气和胆气 这种感觉只可深究不好言传)
            hanoi(n - 1, pos1, pos3, pos2);
            //               src         dest
            // 反正我就是得先把上面的 n-1 个盘子堆到第二个柱子上面去
            // 你这个方法就是得去实现这个功能

            // 你实现好了之后我就可以做下面的第二步了
            // 第二步:最下面的盘子放到 C 上面
            move(pos1, pos3);

            // 第三步:刚刚从 A->B 的 n-1 个盘子 要放到 已经有最大盘子的 C 上 他怎么实现的我不管
            hanoi(n - 1, pos2, pos1, pos3);
            //              src          dest
            // 那这n个盘子不也是汉诺塔问题吗 按我想把你从 pos2 弄到 pos3去 直接这么写就好了
            // 那这里就满足了递归的条件一: 1. 将原问题划分成其子问题，注意：子问题必须要与原问题的解法相同
            // 那这个时候还缺递归的条件二: 2. 递归出口
            // 想一下什么时候可以停止递归 没法再化成子问题的时候对不对 那就是只剩最后一个盘子的时候了
            // 那肯定要写在反复调用之前喽 所以写在 hanoi 这个方法的最前面
        }
    }
static void main() {
	Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    hanoi(n, 'A', 'B', 'C'); // 这里打断点再调试调试看看
    System.out.println(count);
}

运行结果

输入3 得到下面结果

A->C A->B C->B A->C B->A B->C A->C 4

---

📊 执行过程拆解（n=3 的完整展开）

用图示来理解每一步发生了什么：

Step 1: hanoi(3, A, B, C)
   ├── 第一步：hanoi(2, A, C, B)   ← 把 2 个盘子从 A 借助 C 搬到 B
   │       ├── hanoi(1, A, B, C)  → move(A, B)  A→B
   │       ├── move(A, C)          A→C
   │       └── hanoi(1, B, A, C)  → move(B, C)  B→C
   │       结果：A柱空，B有[2][1]，C有[3]
   ├── 第二步：move(A, C)            A→C（最大盘终于动了！）
   │       结果：A柱空，B有[2][1]，C有[3(最大)]
   └── 第三步：hanoi(2, B, A, C)   ← 把 B 上的 2 个盘子搬到 C
           ├── hanoi(1, B, C, A)  → move(B, A)  B→A
           ├── move(B, C)          B→C
           └── hanoi(1, A, B, C)  → move(A, C)  A→C

最终：A空 B空 C有[1][2][3] ✅

// ├ ─ ─ └ 这几个符号好难搞 有更好的办法欢迎评论或私信告知 笔者是使用cv大法的

---

🔑 递归的两条铁律（一定要记住）

规则	内容	对应代码
子问题与原问题相同	每次调用 hanoi(n-1, ...)，只是规模变小，解法不变	hanoi(n - 1, pos1, pos3, pos2)
有递归出口	不能继续拆时，直接给答案，不再调用自己	if (n == 1) { move...; return; }

---

📈 复杂度分析

多代入几个值就可以发现这个规律 相信上面的理解了之后 下面这个表格是没有问题的

n（盘子数）	移动次数	公式
1	1	2¹ - 1
2	3	2² - 1
3	7	2³ - 1
4	15	2⁴ - 1
5	31	2⁵ - 1

时间复杂度：O(2ⁿ - 1) — 指数级，每多一个盘子，计算量翻倍
空间复杂度：O(n) — 递归调用栈的深度

---

🧩 递归的通用思维模板

遇到递归问题，按这个顺序想：

1. 我要解决什么问题？（定义函数的功能）
2. 这个大问题能拆成完全一样的子问题吗？（写出递归调用）
3. 什么时候不能再拆了？（找出递归出口）
4. 检验：最小问题能否正确返回？

---

💡 核心一句话总结

递归不是"自己调用自己"，而是"相信已有的自己能把问题解决"
你只需要做好两件事：拆分问题 + 守住出口

---

📝 笔者学会了用Emoji 同时对警告框进行了优化 若有建议或者问题 欢迎随时交流沟通