从N阶汉诺塔理解循环和递归的区别

N阶汉诺塔的通常解法为递归解决，通过递归将任意层级的汉诺塔逐层降级，使其成为一阶汉诺塔时再依次求解，最终得出答案。

理论上来说递归和循环可相互转换，那通过循环的方式来实现N阶汉诺塔理论上也是可行的。

那既然如此，通过循环实现的N阶汉诺塔的解法相比于递归又有何区别呢？能否以此探究下循环和递归到底有什么不同？

什么是汉诺塔问题？

先前情提要一下，汉诺塔问题的目标是将 N 个圆盘从起始柱（A）移动到目标柱（C），借助辅助柱（B），并遵循以下规则：

• 一次只能移动一个圆盘。
• 任何时候，大圆盘都不能放在小圆盘之上。

当 N 阶汉诺塔求解完成时，所需的总步数为 2^N - 1。

汉诺塔问题的递归解法

作为参考答案，这里也给出N阶汉诺塔的经典递归写法，来感受下递归自顶向下的简约之美。

public class HanoiTower {
    /**
     * @brief 汉诺塔递归方法
     * * @param n 圆盘数量
     * @param source 起始柱 (e.g., "A")
     * @param auxiliary 辅助柱 (e.g., "B")
     * @param destination 目标柱 (e.g., "C")
     */
    public static void hanoi(int n, String source, String auxiliary, String destination) {
        // 基本情况
        if (n == 1) {
            System.out.println("将圆盘 1 从" + source + " 移动到 " + destination);
            return;
        }
        // 1. 将 n-1 个圆盘从 source 移到 auxiliary
        hanoi(n - 1, source, destination, auxiliary);
        // 2. 将第 n 个圆盘从 source 移到 destination
        System.out.println("将圆盘 " + n + " 从 " + source + " 移动到 " + destination);
        // 3. 将 n-1 个圆盘从 auxiliary 移到 destination
        hanoi(n - 1, auxiliary, source, destination);
    }

    public static void main(String[] args) {
        int N = 3; // 假设 N=3 阶汉诺塔
        System.out.println("--- " + N + "阶汉诺塔 ---");
        hanoi(N, "A", "B", "C");
    }
}

对于N阶汉诺塔这类具有自相似结构的问题，通过递归求解，其核心部分就三四行代码，简洁到让人不仔细看都不知道它做了什么（虽然仔细看也不一定看得明白就是了~）。

在递归解法中将原本的N阶圆盘移动的问题拆分为了将 N-1 个圆盘移动的问题，可将整个移动步骤视为以下几步：

1. (N-1 降级)： 将最上面的 N-1 个圆盘作为一个整体，从 起始柱 S 移动到 辅助柱 A。此时目标柱 D 作为辅助柱。
2. (N 移动)： 将底部的第 N 个圆盘（最大的圆盘）从 起始柱 S 移动到 目标柱 D。
3. (N-1 归位)： 将先前移动到 辅助柱 A 上的 N-1 个圆盘，移动到 目标柱 D。此时起始柱 A 作为辅助柱。

以二层汉诺塔为例，做个简单说明。

1. (1 降级)： 将最上面的 1 个圆盘作为一个整体，从 起始柱 S 移动到 辅助柱 A。
2. (2 移动)： 将底部的第 2 个圆盘（最大的圆盘）从 起始柱 S 移动到 目标柱 D。
3. (1 归位)： 将先前移动到 辅助柱 A 上的 1 个圆盘，移动到 目标柱 D。

在此过程中，柱子的身份并非一成不变的，而是随着移动过程而变化。每一次函数调用和随后的函数返回（即层级恢复）时，起始柱、目标柱和辅助柱的角色都在不断地根据当前的子任务而动态变换，柱子的身份也会跟随发生相应的变化。

递归的代码用起来确实简洁又简单，但理解其背后的执行逻辑却很曲折，即使你知道它的核心思路是从最高层逐层降级到最底层再逆序求解，但由于所有的状态变化和上下文都被隐式的封装在系统调用栈中，并没有显示说明，这导致看代码还是让人头疼欲裂，总感觉哪里想不明白，以至于我总是觉得递归这种玩意有点反人类。

鉴于以上种种，让我突发奇想，如果用循环解决汉诺塔问题会怎么样呢？递归那么反人类，循环总得好点吧~

汉诺塔问题的循环解法

循环实现相比较于递归感觉差别最大的地方在于显示的状态处理，很多情况下，递归解法中状态处理是隐式的，而循环解法中状态处理是显式的，需要手动维护。

对于通过循环来实现N阶汉诺塔的过程，不得不说，让我体会到了递归其实是有其优点和美好的，在特别的问题上，还是要用特别的解法，死磕的话，就得求自己的心理阴影面积了。

首先需要思考的就是如何通过循环去模拟N阶汉诺塔的移动轨迹，总结规律，找出最优走法，是的这个逻辑很顺畅，很符合日常的思维习惯，但实际操作起来会发现程序并不具备整体观念，它没办法根据其他柱子的情况来判断当前该做什么不该做什么，如果不设置好足够优秀的规则，很容易把自己跑进死循环里，就看着它 A->B，B->A，无限转圈圈。

只能是人工不断的优化和总结相应的规律，哪里错了改哪里，不断的校正各种状态处理和控制条件，最终使循环能够正常运行。

总之，再经过漫长的尝试的后，自己都不知道自己推算过多少次汉诺塔后，再失败了 N 次后，最终得出了完美的结论！（PS：才怪，我只总结出了部分规则，在特定层数会有bug，最后的实在是没办法，请 AI 出山总结，我又调整的后续逻辑，真是一言难尽）

总结如下：

N阶汉诺塔的运行轨迹和层数以及步数强相关，层数和步数成正比，步数为2的N次方减1，解法关键在于跟踪最小圆盘的移动方向，是的，最小圆盘不光是递归的出口，在循环里它也是关键，最小圆盘提供了一个可预测、周期性且与总步数紧密关联的规律，使N阶汉诺塔的整个的执行流程解耦成两个简单的规则，奇数操作和偶数操作。

当N阶汉诺塔为奇数层时，最小圆盘的最优走法始终是：S -> D -> A -> S 的循环，偶数层时，最小圆盘的最优走法始终是：S -> A -> D -> S 的循环。其中 S 代表起始柱、D 代表目标柱、 A代表辅助柱。

确定了汉诺塔的层数后，后续操作就以步数的奇偶再进行区分，当步数为奇数时，严格按照预定的 S -> D -> A 或 S -> A -> D 的顺序循环移动最小圆盘，很神奇吧，在为奇数的时候居然都是在移动最小圆盘。当步数为偶数的时候，在非最小圆盘存在的另外两个柱子之间，执行唯一合法的移动（将较小的圆盘移到较大的圆盘上）。

下面就是个复杂到抽象的代码实现

public class HanoiIterative {

    // 使用常量表示无穷大，用于判断空柱子的顶部圆盘
    private static final int INF = Integer.MAX_VALUE;

    /**
     * @brief N阶汉诺塔问题的循环（迭代）解法。
     * * @param n 圆盘数量
     * @param sourceName 起始柱名称 (e.g., "A")
     * @param auxiliaryName 辅助柱名称 (e.g., "B")
     * @param destinationName 目标柱名称 (e.g., "C")
     */
    public static void hanoiIterative(int n, String sourceName, String auxiliaryName, String destinationName) {
        if (n <= 0) return;

        long totalMoves = (1L << n) - 1; // 总移动次数: 2^n - 1

        // 1. 初始化柱子
        Stack<Integer> source = new Stack<>();
        Stack<Integer> auxiliary = new Stack<>();
        Stack<Integer> destination = new Stack<>();

        // 初始化起始柱：圆盘从大到小（N到底 1到顶）
        for (int i = n; i >= 1; i--) {
            source.push(i);
        }

        // 使用数组存储柱子和它们的名称，方便通过索引访问
        Stack<Integer>[] towers = new Stack[]{source, auxiliary, destination};
        String[] names = new String[]{sourceName, auxiliaryName, destinationName};

        // 2. 根据 N 的奇偶性确定柱子的顺序
        String[] order = new String[3];
        if (n % 2 == 1) {
            // N为奇数: S -> D -> A -> S (顺时针)
            order[0] = sourceName;
            order[1] = destinationName;
            order[2] = auxiliaryName;
        } else {
            // N为偶数: S -> A -> D -> S (逆时针)
            order[0] = sourceName;
            order[1] = auxiliaryName;
            order[2] = destinationName;
        }

        System.out.println("--- " + n + " 阶汉诺塔（循环解法）---");

        // 主循环：执行 totalMoves 次移动
        for (long moveCount = 1; moveCount <= totalMoves; moveCount++) {

            if (moveCount % 2 != 0) {
                // **奇数步：移动圆盘 1**

                // 1. 找到圆盘 1 当前所在的柱子
                Stack<Integer> currentPeg = null;
                String currentPegName = "";

                for (int i = 0; i < 3; i++) {
                    if (!towers[i].isEmpty() && towers[i].peek() == 1) {
                        currentPeg = towers[i];
                        currentPegName = names[i];
                        break;
                    }
                }

                // 2. 找到下一个目标柱子
                // 定位当前柱子在 order 数组中的索引
                int currentIndex = Arrays.asList(order).indexOf(currentPegName);
                String nextPegName = order[(currentIndex + 1) % 3];

                // 3. 找到目标柱子 Stack 对象
                Stack<Integer> nextPeg = null;
                for (int i = 0; i < 3; i++) {
                    if (names[i].equals(nextPegName)) {
                        nextPeg = towers[i];
                        break;
                    }
                }

                // 4. 执行移动
                if (currentPeg != null && nextPeg != null) {
                    int disk = currentPeg.pop();
                    nextPeg.push(disk);
                    System.out.println("Move " + moveCount + ": Disk " + disk + " from " + currentPegName + " to " + nextPegName);
                }

            } else {
                // **偶数步：移动非圆盘 1 的唯一合法移动**

                // 找出不是圆盘 1 所在的那两个柱子
                Stack<Integer> peg1 = null, peg2 = null;
                String name1 = "", name2 = "";

                for (int i = 0; i < 3; i++) {
                    if (towers[i].isEmpty() || towers[i].peek() != 1) {
                        if (peg1 == null) {
                            peg1 = towers[i];
                            name1 = names[i];
                        } else {
                            peg2 = towers[i];
                            name2 = names[i];
                            break; // 找到了两根，可以退出
                        }
                    }
                }

                // 获取两个柱子的顶部圆盘大小
                int top1 = peg1.isEmpty() ? INF : peg1.peek();
                int top2 = peg2.isEmpty() ? INF : peg2.peek();

                Stack<Integer> sourcePeg, destPeg;
                String sourceNameP, destNameP;

                if (top1 < top2) {
                    // 移动 top1 到 peg2 (小移到大)
                    sourcePeg = peg1; destPeg = peg2;
                    sourceNameP = name1; destNameP = name2;
                } else {
                    // 移动 top2 到 peg1 (小移到大)
                    sourcePeg = peg2; destPeg = peg1;
                    sourceNameP = name2; destNameP = name1;
                }

                // 执行移动
                int diskMoved = sourcePeg.pop();
                destPeg.push(diskMoved);
                System.out.println("步数 " + moveCount + ": 圆盘 " + diskMoved + " 从 " + sourceNameP + " 到 " + destNameP);
            }
        }

        // 验证最终状态
        System.out.println("\n最终结果:");
        System.out.println(sourceName + ": " + source);
        System.out.println(auxiliaryName + ": " + auxiliary);
        System.out.println(destinationName + ": " + destination);
    }

    public static void main(String[] args) {
        int N = 3; // N=3 阶汉诺塔
        hanoiIterative(N, "A", "B", "C");
    }
}

1. 整体代码流程就是先构建三个栈当做柱子，然后给起始柱填入对应的圆盘做好基础的准备。
2. 确定N阶汉诺塔的层级，决定最小圆盘的移动顺序
3. 开始在循环中移动圆盘，奇数步的时候按照定好的顺序移动最小圆盘，偶数的时候，将最小圆盘不在的两个柱子中，将较小的圆盘移到较大的圆盘上
4. 循环往复，直至最后得出结论

总结

对于自相似结构的问题（如树、分治算法），递归是首选，因为它更自然、更易于编写和理解（是的，这要看怎么比了，它相比较于用循环去实现同样的问题确实要简单和快捷……） 递归通过调用栈时的隐式状态管理可以省却很多的麻烦，在其他的情况下，循环总会是个不错的选择，它更符合人类的思维习惯，也更容易编写和理解。