汉诺塔问题的递归与非递归 C++ 解法

汉诺塔是一个经典的递归算法入门问题。规则很简单：有三根柱子 A、B、C，n 个大小不同的圆盘初始都按由小到大的顺序叠在 A 上。要求把所有圆盘移动到 C 上，过程中可以借助 B，但每次只能移动最上面的一个圆盘，而且任何时刻都不能出现大盘压小盘。

最少移动次数是 2^n - 1。当 n=1，一步搞定；n=2，需要 3 步；n=3 就需要 7 步，以此类推。递归解法的核心是把 n 个圆盘的问题拆成三个子问题：先把上面 n-1 个从 A 移到 B（以 C 为辅助），然后把最大的那个从 A 移到 C，最后再把 B 上的 n-1 个移到 C（以 A 为辅助）。当 n 减到 1 时，就可以直接移动了。

递归实现

递归代码很直观，直接照搬分解思路：

#include <iostream>
using namespace std;

int n;

void hanoi(char a, char b, char c, int n) {
    if (n > 0) {
        hanoi(a, c, b, n - 1);
        cout << n << " from: " << a << " to " << c << endl;
        hanoi(b, a, c, n - 1);
    }
}

int main() {
    cin >> n;
    char a = 'A', b = 'B', c = 'C';
    hanoi(a, b, c, n);
    return 0;
}

这个函数在 n>0 时，先递归处理上面 n-1 个圆盘，移动完后把当前最大圆盘从 a 移到 c，然后递归把那 n-1 个从 b 移到 c。参数顺序可能会让人迷糊，但对应起来就是：第一次调用把 A 上的 n-1 个移到 B，所以源是 A，目标是 B，辅助是 C；第二次调用把 B 上的 n-1 个移到 C，源是 B，目标是 C，辅助是 A。

非递归解法：用栈模拟或规律循环

递归的优点是代码简洁，但如果圆盘数很大，递归层数过深可能导致栈溢出。非递归实现可以避免这个问题，同时也能帮助我们更好地理解递归的底层机制。

一种常用的非递归方法是手动维护一个栈，模拟系统调用栈。我们可以把每次待处理的任务（盘数、源、辅助、目标）压栈，然后循环处理直到栈空。不过更简单的非递归思路是利用汉诺塔的一个经典规律：交替完成两种移动。

假设圆盘按顺序编号从 1（最小）到 n（最大）。如果 n 是奇数，移动序列有下面规律：

1. 将圆盘 1 移动到下一个柱子（按 A→C→B→A 循环）；
2. 然后，在剩下的两个柱子之间进行一次合法移动（即只能把较小的盘移到较大的盘上，或移到空柱子上）；
3. 重复以上两步，直到所有圆盘移到 C。

如果 n 是偶数，起点柱子 A 上的第一步移动圆盘 1 要按 A→B→C→A 的顺序。按照这个规律，我们可以在循环中判断何时结束。

下面这段代码用栈来存储每个柱子上的圆盘，并按照上述规律模拟移动：

#include <iostream>
#include <stack>
using namespace std;

int n;
char s[5] = {'0', 'A', 'B', 'C'};
stack<int> a[5];

void move(int now, int next) {
    a[next].push(a[now].top());
    printf("%d from %c to %c\n", a[now].top(), s[now], s[next]);
    a[now].pop();
}

int main() {
    cin >> n;
    for (int i = n; i >= 1; i--)
        a[1].push(i);   // 初始时 A 柱从底到顶是 n, n-1, ..., 1

    if (n % 2 == 1) {   // 奇数时交换 B 和 C 的标签，保证最终移到 C
        s[2] = 'C';
        s[3] = 'B';
    }

    while (true) {
        // 第一步：移动圆盘 1
        int next;
        for (int i = 1; i <= 3; i++) {
            if (!a[i].empty() && a[i].top() == 1) {
                if (i == 3) next = 1;
                else next = i + 1;
                move(i, next);
                break;
            }
        }

        if (a[2].size() == n || a[3].size() == n) break; // 完成

        // 第二步：在剩余两柱间做合法移动
        int other1, other2;
        switch (next) {
            case 1: other1 = 2; other2 = 3; break;
            case 2: other1 = 3; other2 = 1; break;
            case 3: other1 = 1; other2 = 2; break;
        }
        if (a[other1].empty())
            move(other2, other1);
        else if (a[other2].empty())
            move(other1, other2);
        else {
            if (a[other1].top() < a[other2].top())
                move(other1, other2);
            else
                move(other2, other1);
        }
    }
    return 0;
}

代码的核心就是循环执行两步：移动最小盘，然后做剩下两柱之间的合法移动。当某一辅助柱（B 或 C）的圆盘数达到 n 时，任务完成。奇数个圆盘时交换了 B、C 的标签，最终会全部移到 C 上，符合题目要求。

最后

非递归的栈模拟方法不限于汉诺塔，很多递归问题（如二叉树的遍历、DFS、归并排序等）都可以通过手动维护栈来实现非递归版本。理解这种转换思路，对于把握递归的本质很有帮助。