汉诺塔问题中递归思想分析

假设有A、B、C三个柱子,刚开始A柱上有N片面积从上到下依次递减的金片，要求把这N片金片移动到C柱上，移动期间大片不能放到小片上。

先说结论吧，要把N片金片从A柱移动到C柱上，要：

1、先把前N-1片移动到B柱(非目标柱)；

2、再把第N片移动到C柱上；

3、最后把B柱的N-1片移动到C柱上。

你说，怎么把前N-1片金片移动到B柱呢？最简单的方法就是重复上述123 ！

到这里，我们就能很容易就看出递归了吧！

-------------------接下来我们用N分别=1、2、3、4来验证下------------------------------------

• N=1

我们直接把这1片金片从A移动到C就好。

• N=2

我们给每个金片从上到下编号：1、2；

接下来套用上面的步骤，把金片分成两组移动：[1]，[2]；此时ABC柱金片分布为：（[1,2]，[ ]，[ ]）

1、[1]-->B 表示把组[1]移动到B柱，此时A、B、C柱的金片分布为 ([2]，[1]，[ ])。

2、[2]-->C，（[ ]，[1]，[2]）;

3、[1]-->C，([ ]，[ ]，[1,2])移动完成！

• N=3

金片编号：1、2、3

分组移动：[1,2]，[3]

1、[1,2]-->B：

1.0 分组移动：[1]，[2]；因为目标为B柱，而此时C柱为非b目标柱，所以要先把[1]移动到C柱；

1.1 [1]-->C，（[2,3]，[ ]，[1]）

1.2 [2]-->B，（[3]，[2]，[1]）

1.3 [1]-->B，（[3]，[1,2]，[ ]）

2、[3]-->C，（[ ]，[1,2]，[3]）

3、[1,2]-->C:

3.0 分组移动：[1]、[2]；目标为C柱，此时A柱为非目标柱，所以要先把[1]移动到A柱；

3.1 [1]-->A，（[1]，[2]，[3]）

3.2 [2]-->C，（[1]，[ ]，[2,3]）

3.3 [1]-->C，（[ ]，[ ]，[1,2,3]）

移动完成！

• N=4自己递推试试吧。

----------------------------------算了,直接递推N=4-------------------------------

分组：[1,2,3]，[4]

1、[1,2,3]-->B:

1.0 分组：[1,2]，[3]，此时是不是和N=3基本一致，只是目标柱是B柱？

1.1 [1,2]-->C：

1.1.0 分组：[1]，[2]；目标为C柱，而B柱为非目标柱，所以把[1]移动到B

1.1.1：[1]-->B，（[2,3,4]，[1]，[ ]）

1.1.2：[2]-->C，（[3,4]，[1]，[2]）

1.1.3：[1]-->C，（[3,4]，[ ]，[1,2]）

1.1移动完成

1.2 [3]-->B，（[4 ]，[3]，[1,2]）

1.3 [1,2]-->B：

1.3.0 分组：[1]，[2]；目标为B柱，而此时A柱为非目标柱，所以把[1]移动到A柱

1.3.1 [1]-->A，（[1,4]，[3]，[2]）

1.3.2 [2]-->B，（[1,4]，[2,3]，[ ]）

1.3.3 [1]-->B，（[ 4]，[1,2,3]，[ ]）

步骤1 移动完成

2、[4]-->C，（[ ]，[1,2,3]，[4]）

3、[1,2,3]-->C：

3.0 分组：[1,2]，[3]；目标柱为C柱，而A为非目标柱，所以把[1,2]移动到A柱

3.1 [1,2]-->A

3.1.0分组[1]，[2]；目标为A柱，此时C为非b目标柱

3.1.1 [1]-->C，（[ ]，[2,3]，[1,4]）

3.1.2 [2]-->A，（[2]，[3]，[1,4]）

3.1.3 [1]-->A，（[1,2]，[3]，[4]）

步骤3.1完成

3.2 [3]-->C，（[1,2]，[ ] ，[3,4]）

3.3 [1,2]-->C:

3.3.0分组：[1]，[2]；此时B柱为非目标柱

3.3.1 [1]-->B，（[2]，[1]，[3,4]）

3.3.2 [2]-->C，（[ ]，[1]，[2,3,4]）

3.3.3 [1]-->C，（[ ]，[ ]，[1,2,3,4]）

移动完成！

有兴趣可以尝试递推N=5啊，N每增加1，就增加2^(N-1)步。