我来帮你理清楚四柱汉诺塔（Reve's Puzzle）的递归实现思路——你已经搞定了三柱的代码，其实四柱的核心就是基于Frame-Stewart猜想的分治策略，咱们一步步拆解明白：

先搞懂核心的Frame-Stewart策略 #

首先，你提到的k值是整个递归的关键分界点：对于n个圆盘，我们要先把最上面的k个小圆盘从起始柱移到第一根辅助柱（不是目标柱），这一步用4柱模式；然后把剩下的n-k个大圆盘用3柱模式移动到目标柱（这时候第一根辅助柱被小圆盘占了，相当于只能用剩下3根柱子）；最后再把那k个小圆盘从第一根辅助柱移到目标柱，还是用4柱模式。

这里的k值计算公式你记的有点小偏差，正确的应该是：k = n + 1 - sqrt(2*n + 1)，计算后取整数部分就行。比如n=4时，k=2，这是经过验证的最优分界点。

对比三柱和四柱的递归差异 #

你写的三柱递归是固定的“移n-1到辅助→移最大到目标→移n-1到目标”的流程，而四柱递归是分两种场景：当圆盘数量少到可以用4柱优化时用4柱逻辑，当需要移动较大的圆盘堆时，因为小圆盘占了一根辅助柱，只能退化成你熟悉的3柱逻辑。

拆解你疑惑的步骤1和3 #

你说的步骤1和3逻辑相似，其实它们本质都是4柱模式下的圆盘移动，区别只是起始柱、辅助柱组合和目标柱的角色换了：

• 步骤1：把k个小圆盘从from柱移到temp1柱，这时候4根柱子都能用，所以调用4柱递归；
• 步骤3：把k个小圆盘从temp1柱移到to柱，同样4根柱子都能用，只是参数里的起始柱、目标柱和辅助柱顺序调整了，递归逻辑完全一致。

中间的步骤2就是你已经掌握的三柱递归：把n-k个大圆盘从from移到to，这时候temp1被小圆盘占了，大圆盘不能放在上面，所以只能用from、temp2、to三根柱子，直接复用三柱逻辑就行。

完整代码实现 #

我们把代码拆成两个方法，复用你已有的三柱递归，再实现四柱的核心逻辑：

import java.lang.Math;

public class RevesPuzzle {

    // 复用你已有的三柱汉诺塔递归方法
    private static void hanoiThree(int n, String from, String temp, String to) {
        if (n == 0) return;
        hanoiThree(n - 1, from, to, temp);
        System.out.println("Move disc " + n + " from " + from + " to " + to);
        hanoiThree(n - 1, temp, from, to);
    }

    // 四柱汉诺塔的递归实现（Reve's Puzzle）
    private static void revesPuzzleFour(int n, String from, String temp1, String temp2, String to) {
        if (n == 0) return;
        // 计算最优k值，取整数部分
        int k = (int) (n + 1 - Math.sqrt(2 * n + 1));
        
        // 步骤1：4柱模式移k个圆盘到第一辅助柱
        revesPuzzleFour(k, from, temp2, to, temp1);
        // 步骤2：3柱模式移剩下的n-k个圆盘到目标柱
        hanoiThree(n - k, from, temp2, to);
        // 步骤3：4柱模式移k个圆盘到目标柱
        revesPuzzleFour(k, temp1, from, temp2, to);
    }

    // 测试入口，比如测试4个圆盘，最优步数是9步
    public static void main(String[] args) {
        int n = 4;
        revesPuzzleFour(n, "A", "B", "C", "D");
    }
}

关键细节再强调 #

1. k值的意义：这个k值是Frame-Stewart猜想给出的最优分界点，能让总移动步数最少，目前对于所有正整数n，这个策略都能得到最优解，已经被数学证明。
2. 步骤1和3的一致性：这两步都是4柱递归，只是柱子参数的顺序调整了——因为起始和目标柱换了，辅助柱的角色也跟着变，但递归的核心逻辑都是用4根柱子来移动k个圆盘。
3. 退化为三柱的时机：当移动n-k个大圆盘时，k个小圆盘已经占了一根辅助柱，大圆盘不能放在小圆盘上，所以只能用剩下的3根柱子，这时候就直接用你熟悉的三柱汉诺塔逻辑。

内容的提问来源于stack exchange，提问作者Eric Goto