汉诺塔问题详解：C++ 递归与非递归实现

2. 完整递归代码（带步骤打印）

#include<iostream>
using namespace std;

int n;

void hanoi(char a, char b, char c, int n) {
    if (n > 0) {
        // 将 A 盘分为两部分，n-1 与 1，把 n-1 放到 B 盘（修改为目标盘），C 盘作为中介盘
        hanoi(a, c, b, n - 1);
        
        // 输出移动步骤
        cout << n << " from: " << a << " to " << c << endl;
        
        // 将 B 盘中的 n-1 作为起始盘移动到目标盘 C
        hanoi(b, a, c, n - 1);
    }
}

int main() {
    cin >> n;
    char a = 'A'; // A 盘
    char b = 'B'; // B 盘
    char c = 'C'; // C 盘
    
    // 将 A 作为起始盘，B 作为中介盘，C 作为目标盘，n 为移动目标数量
    hanoi(a, b, c, n);
    return 0;
}

三、非递归实现汉诺塔

递归的本质是'系统栈自动处理调用过程'，因此非递归实现的核心是用栈模拟递归栈，手动维护汉诺塔的移动状态（待移动的圆盘数、源柱、辅助柱、目标柱）。

非递归思路

一位美国学者发现：所有的汉诺塔移动可以总结为重复的两步。我们假设现在最小的圆盘在 A 杆上，杆为 A、B、C：

1. 第一步：将最小圆盘移动到下一个杆上；
2. 第二步：对剩下两个杆的顶上元素进行判断，把较小的那个圆盘移动到较大的那个圆盘上（如果有空杆则移在空杆上）。

重复上述两步就可以得到答案。

注意：这样得到的最后的答案不一定是摞在 C 杆上，如果 N 是奇数则将摞在 B 上。所以如果 N 是奇数我们把杆的摆放顺序设置为 A、C、B，这样就能保证盘子是从 A 杆全部移动到 C 杆。

1. 非递归思路

1. 定义栈结构，初始化 A 盘，从大到小排序好；
2. 判断 n 的奇偶性，做出对应的转化；
3. 按照第一步：将最小圆盘移动到下一个杆上；第二步：对剩下两个杆的顶上元素进行判断，把较小的那个圆盘移动到较大的那个圆盘上（如果有空杆则移在空杆上）进行循环操作；
4. 循环直至栈 B 或栈 C 全满，所有圆盘移动完成。

2. 代码实现

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

int n;
char s[5] = {'0', 'A', 'B', 'C'}; // 杆 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;
    int count = 0;
    
    // 从大到小初始化 A 杆
    for (int i = 0; i < n; i++) a[1].push(n - i);
    
    // 如果是奇数个圆盘交换 B 盘与 C 盘的功能
    if (n % 2 == 1) {
        s[2] = 'C';
        s[3] = 'B';
    }
    
    while (1) {
        int next;
        // 循环移动判断三个杆
        for (int i = 1; i <= 3; i++) {
            if (!a[i].empty()) { // 如果不为空
                if (a[i].top() == 1) { // 且最上面是最小的盘
                    if (i == 3) next = 1; // 若是最后一个杆，它的下一个杆是 A 杆
                    else next = i + 1; // 否则正常 i+1 是下一个
                    move(i, next); // 当前杆的盘移动到下一个杆
                    break;
                }
            }
        }
        
        // 如果都在一个杆上了就完成了，判断 a[2] 与 a[3]
        // 因为奇数的目标杆是 2 号杆，偶数的目标杆是 3 号杆
        if (a[2].size() == n || a[3].size() == n) break;
        
        int other1, other2;
        switch (next) {
            case 1: { // 如果此次对 1 号杆进行了操作
                other1 = 2; // 剩下两个杆就是 2 号 3 号杆
                other2 = 3;
                break;
            }
            case 2: { // 依次类推
                other1 = 3;
                other2 = 1;
                break;
            }
            case 3: {
                other1 = 1;
                other2 = 2;
                break;
            }
        }
        
        if (a[other1].empty()) move(other2, other1); // 如果 other1 为空，那它是最小的一个杆，将 other2 移动到 other1
        else if (a[other2].empty()) move(other1, other2); // 如果 other2 为空，那它是最小的一个杆，将 other1 移动到 other2
        else {
            if (a[other1].top() < a[other2].top()) move(other1, other2); // 否则判断大小，将小的移动到大的杆上
            else move(other2, other1);
        }
    }
    return 0;
}

四、总结

通过对比两种实现方式，我们可以更清晰地看到递归与非递归的内在联系。非递归实现基于栈模拟的核心思想，结合 C++ 标准库的优势，实现了内存安全、无栈溢出、高效率的解法。相比纯递归版，它在处理大规模数据时更具工程实用性。

掌握这一思路，不仅能解决汉诺塔问题，更能理解递归的本质（系统栈的自动调用）和递归转非递归的通用方法（自定义栈模拟状态）。这一思路可推广到所有递归问题（如二叉树遍历、深度优先搜索 DFS、归并排序等）的 C++ 非递归实现中。