数据结构：递归：汉诺塔问题（Tower of Hanoi）

目录

问题描述

 第一性原理分析

代码实现

第一步：明确函数要干什么

第二步：写好递归的“结束条件”

第三步：写递归步骤 

 🌳 递归调用树

🔍复杂度分析

时间复杂度：T(n) = 2^n - 1

 空间复杂度分析

问题描述

有三个柱子（A, B, C），上面有 n 个大小不等的圆盘，最开始所有圆盘按从大到小顺序堆在柱子 A 上。
目标：将所有圆盘移动到柱子 C，移动时要满足：

1. 一次只能移动一个盘子；

2. 任何时刻小盘子不能压在大盘子上。

❓核心问题：

如何将 n 个盘子 从 A 移动到 C，同时只用 B 做辅助，且不违反约束？

 第一性原理分析

🔹1.基础情况（Base Case）

• n = 1：只有一个盘子，直接从 A → C，一步解决。这是最小子问题。

🔹2. 如果有两个盘子，要怎么动？

设柱子为 A（起始）、B（辅助）、C（目标）：

你会这样操作：

1. 把小盘子从 A → B

2. 把大盘子从 A → C

3. 再把小盘子从 B → C

 🔹3. 如果有三个盘子，要怎么动？

步骤 1：移动盘子 1 从 A ➜ C

步骤 2：移动盘子 2 从 A ➜ B

步骤 3：移动盘子 1 从 C ➜ B

步骤 4：移动盘子 3 从 A ➜ C​​​​​​​

步骤 5：移动盘子 1 从 B ➜ A

步骤 6：移动盘子 2 从 B ➜ C​​​​​​​

步骤 7：移动盘子 1 从 A ➜ C​​​​​​​

这就引出一个关键逻辑：

✅ 要移动第 n 个（最大）盘子，必须先把上面的 n-1 个盘子“暂时”搬开。

🧩 移动 n 个盘子的本质是 —— 找出一个“序列”，让我们可以先清掉上面的 n-1 个盘子，再移动第 n 个，然后再恢复那 n-1 个。

换句话说：

• 把 n-1 个盘子移到辅助柱；

• 把第 n 个（最大）盘子移到目标柱；

• 再把那 n-1 个盘子从辅助柱移回来。

这三步操作可以形成递归：

Hanoi(n, A, B, C):
    1. 移动 n-1 个盘子从 A → B（借助 C）Hanoi(n-1, A, C, B)
    2. 移动第 n 个盘子从 A → C
    3. 移动 n-1 个盘子从 B → C（借助 A）Hanoi(n-1, B, A, C)

📐 所以从第一性来看，汉诺塔的“递归”，不是魔法，而是逻辑：

• 没有任何一步是“看上去神奇的”；

• 每一个盘子的移动，都必须建立在“先让出空间”的原则上；

• 这就导致了问题具有自相似性：每一层和上面那一层的问题结构一样；

代码实现

第一步：明确函数要干什么

我们要写的是一个函数：移动 n 个盘子从柱子 A → 柱子 C，借助柱子 B。

 所以我们需要：

• 盘子的数量：int n

• 三个柱子的名字（我们用字符）：char from, temp, to

#include <iostream>
using namespace std;

// 函数声明：移动 n 个盘子，从 from → to，借助 temp
void hanoi(int n, char from, char temp, char to) {

解释：

• n：要移动的盘子数

• from：起始柱

• temp：中转柱（辅助）

• to：目标柱

第二步：写好递归的“结束条件”

为什么要加“终止条件”？

如果你不加，递归会无限下去，直到程序崩溃！

    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }

解释：

• 如果只剩一个盘子，那就是最简单的情况，直接从 from → to。

• cout 是打印这一步。

第三步：写递归步骤 

    // 1. 把 n-1 个盘子从 from → temp，借助 to
    hanoi(n - 1, from, to, temp);

    // 2. 把第 n 个盘子从 from → to
    cout << "Move disk " << n << " from " << from << " to " << to << endl;

    // 3. 把 n-1 个盘子从 temp → to，借助 from
    hanoi(n - 1, temp, from, to);
}

分析这三步逻辑：

1. 把顶部的 n-1 个盘子先“挪走”（递归调用自己）；

2. 把第 n 个盘子（最大的）真正地移动到底部（打印出来）；

3. 把刚才挪走的 n-1 个盘子搬回来（递归调用自己）。

完整代码

#include <iostream>
using namespace std;

// 递归函数：将 n 个盘子从 from 移动到 to，借助 temp
void hanoi(int n, char from, char temp, char to) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }

    // 第一步：把 n-1 个盘子从 from → temp
    hanoi(n - 1, from, to, temp);

    // 第二步：移动第 n 个盘子到目标柱
    cout << "Move disk " << n << " from " << from << " to " << to << endl;

    // 第三步：把 n-1 个盘子从 temp → to
    hanoi(n - 1, temp, from, to);
}

int main() {
    int n;
    cout << "Enter number of disks: ";
    cin >> n;

    hanoi(n, 'A', 'B', 'C');
    return 0;
}

 🌳 递归调用树

我们现在来画出 hanoi(3, A, B, C) 的调用树结构，说明递归是怎么层层展开的。

                            hanoi(3, A, B, C)
                          /         |         \
            hanoi(2, A, C, B)     Move 3     hanoi(2, B, A, C)
             /     |     \                       /     |     \
 hanoi(1,A,B,C)  M2  hanoi(1,C,A,B)   hanoi(1,B,C,A)  M2  hanoi(1,A,B,C)

 标上实际操作编号：

                            hanoi(3, A, B, C)
                          /         |         \
            hanoi(2, A, C, B)     Move 3     hanoi(2, B, A, C)
             /     |     \                       /     |     \
 hanoi(1,A,B,C)  M2  hanoi(1,C,A,B)   hanoi(1,B,C,A)  M2  hanoi(1,A,B,C)
    /          |         \          |         /          |         \
step1         step2    step3      step4    step5     step6       step7

🔍复杂度分析

时间复杂度：T(n) = 2^n - 1

汉诺塔的递归形式是这样的：

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

意思是：

• 为了移动 n 个盘子：

  • 我们要先移动 n - 1 个盘子（第一次调用）；

  • 移动第 n 个盘子（+1 次）；

  • 再移动 n - 1 个盘子（第二次调用）。

利用迭代展开式来看：

T(n) = 2*T(n-1) + 1
     = 2*(2*T(n-2) + 1) + 1 = 4*T(n-2) + 2 + 1
     = 8*T(n-3) + 4 + 2 + 1
     = ...
     = 2^k * T(n - k) + (2^(k-1) + ... + 2 + 1)

 当 k = n-1 时，T(1) = 1，代入得到：

T(n) = 2^(n - 1) * T(1) + (2^(n - 2) + ... + 1)
     = 2^(n - 1) * 1 + (2^(n - 1) - 1)
     = 2^n - 1

所以时间复杂度是：⏱️ T(n) = O(2^n)

也就是说：

• 每增加一个盘子，所需的移动次数翻倍 + 1。

• 极其不可扩展。

 空间复杂度分析

我们来看递归函数会“开多少层栈”：

void hanoi(int n, char from, char temp, char to)
{
    if (n == 1) return;

    hanoi(n - 1, from, to, temp); // 一次递归调用
    // move...
    hanoi(n - 1, temp, from, to); // 第二次递归调用
}

递归深度分析：

• 最大的递归深度就是从 n → n-1 → n-2 → ... → 1

• 所以最多开 n 层函数栈

所以空间复杂度是：🧠 Space: O(n)

• 因为递归是深度优先遍历

• 不会存储所有子问题，只保存当前路径

🕊️ 如果你是“神庙僧侣”，每天只移动 1 次？

汉诺塔在传说中是：64 个金盘子，僧侣每天移动一块。

T(64) = 2^64 - 1 ≈ 1.84 × 10^19 次

即使 1 秒动一次，你也需要：

≈ 5.8 × 10^11 年

而宇宙年龄都才 138 亿年。所以说移动 64 个盘子“永远也完成不了”。