C++ 汉诺塔问题：递归与非递归实战解析

非递归实现汉诺塔

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

非递归思路

经典的迭代策略指出：所有的汉诺塔移动可以总结为重复的两步。假设现在最小的圆盘在 A 杆上，杆为 A、B、C：

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

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

1. 非递归思路详解

1. 定义栈结构，初始化 A 盘，从大到小排序好；
2. 判断 n 的奇偶性，做出对应的转化（调整 B 盘与 C 盘的功能标签）；
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;
    for (int i = 0; i < n; i++) a[1].push(n - i); // 从大到小初始化 A 杆
    
    if (n % 2 == 1) { // 如果是奇数个圆盘交换 B 盘与 C 盘的功能
        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;
                }
            }
        }
        
        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++ 非递归实现基于栈模拟的核心思想，结合 C++ 标准库的优势，实现了内存安全、无栈溢出、高效率的汉诺塔解法，相比纯递归版更适合实际工程应用。

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