java - 河内代码塔中的错误

在为河内的塔编写递归解决方案时，我的代码适用于1、2和3盘，但之后就不适用了。
不知道我做错了什么。

package recursion;

import java.util.List;

import org.springframework.util.Assert;

import com.google.common.collect.Lists;
import com.google.common.collect.Ordering;

public class Hanoi {

    private static List<Integer> reference = Lists.newArrayList(4, 3, 2, 1);

    private static List<Integer> aList = Lists.newArrayList(reference);
    private static List<Integer> bList = Lists.newArrayListWithCapacity(aList.size() - 1);
    private static List<Integer> cList = Lists.newArrayListWithCapacity(aList.size());

    public static void main(String[] args) {

        hanoi(aList, bList, cList);
        System.out.println(cList);
        Assert.isTrue(cList.equals(reference));
        Assert.isTrue(aList.size() == 0);
        Assert.isTrue(bList.size() == 0);
        System.out.println("done");

    }

    private static void hanoi(List<Integer> aList, List<Integer> bList, List<Integer> cList) {
        if (aList.size() == 1) {
            cList.add(aList.remove(0));
            return;
        }
        hanoi(aList.subList(1, aList.size()), cList, bList);
        print();
        hanoi(aList.subList(0, 1), null, cList);
        print();
        hanoi(bList, aList, cList);
        print();
        System.out.println("=======================================");
    }

    private static void print() {
        System.out.println(aList);
        System.out.println(bList);
        System.out.println(cList);
        Assert.isTrue(Ordering.natural().reverse().isOrdered(aList));
        Assert.isTrue(Ordering.natural().reverse().isOrdered(bList));
        Assert.isTrue(Ordering.natural().reverse().isOrdered(cList));
        System.out.println("******************************************");
    }
}

最佳答案

你的算法基于这样的假设：河内的塔楼总是在第一步（和最后一步）中移动所有的切片，除了一个。
这是一个错误的假设。子问题转移较小的塔。
在hanoi方法中添加参数大小必须调整所有三个步骤：
步骤1和3只应改变大小-1
步骤2不应移动第一个切片，而应移动最后一个（最上面的）