递归解汉诺塔

什么是汉诺塔

汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

图解汉诺塔

我们可以使用如下图表示汉诺塔的初始状态：

我们可以看到，此时 A 柱上有 64 个大小不同的圆盘，现在，我们需要将这 64 个大小不同的圆盘按照原来的顺序移到 C 柱上，并且每次只能移到一个，并且大圆盘不能放在小圆盘上面，最终要达到的效果如下图所示：

64 个盘子有点多，讲解起来又比较困难，我们先从简单的入手，比如只有两个盘子，如下图所示：

现在，我们需要将 A 柱上的两个盘子移动到 C 柱上，那么第一步，我们首先，需要将最上面的盘子移动到 B 柱上，如下图所示：

接着，我们将 A 柱上黄色盘子移动到 C 柱上，此时如下图所示：

最后，我们只需要将 B 柱上的盘子移到 C 柱上即可，此时如下图所示：

我们看到，此时，我们就完成了将 A 柱上的两个盘子借助 B 柱移动到了 C 柱上。现在，我们再看看三个盘子的情况，如下图所示：

我们需要将 A 柱上的三个盘子借助 B 柱移动到 C 柱上，那么我们使用倒推的思想，我们第一步需要的就是要将 A 柱上的 1 号盘移到 C 柱上，那么我们就需要将 2 号盘和 3 号盘想办法移到 B 柱上，那么我们就需要首先将 3 号盘移到 C 柱上，此时如下图所示：

接着，我们将 2 号盘移到 B 柱上，如下图所示：

接着，我们需要将 C 柱腾出来，那么我们可以将 C 柱上的 3 号盘移到 B 柱上，如下图：

现在，我们就可以将 A 柱上的 1 号盘移到 C 柱上了，如下图：

目前我们已经实现了将 1 号盘移到了 C 柱上了，我们需要继续将 2 号盘移到 C 柱上，那么我们首先就需要将 3 号盘移到 A 柱，如下图所示：

现在，我们就可以将 2 号盘移到 C 柱了，如下图：

最后，我们只需要将 A 柱上的 3 号盘移到 C 柱即可，如下图所示：

我们看到，此时我们就完成了三个盘子的移动。

思路说明

两个盘子

如果我们需要将两个盘子比如 1 号盘和 2 号盘（1 号盘大 2 号盘小），从 A 柱移动到 C 柱，那么第一步就一定是要想办法将 1 号盘移到 C 柱上。

此时，因为 2 号盘在 1 号盘上面，因此，我们首先，就需要将 2 号盘移到 B 柱上，接着，就可以将 A 柱上的 1 号盘移到 C 柱了。

最后，我们只需要将 B 柱的 2 号盘移到 C 柱即可完成。

三个盘子

如果我们需要将三个盘子比如 1 号盘，2 号盘和 3 号盘（1 号盘大 2 号盘次之 3 号盘最小），从 A 柱移动到 C 柱，那么第一步就一定是要想办法将 1 号盘移到 C 柱上。

要将 1 号盘移到 C 柱上，那么一定需要将 2 号盘和 3 号盘移到 B 柱上，同理，要将 2 号盘和 3 号盘移到 B 柱，那么首先要做的就是将 3 好盘移到 C 柱，接着，才可以将 2 号盘移到 B 柱，最后，直接将 3 号盘移到 B 柱即可。

此时，C 柱已经空出来了，我们直接将 A 柱的 1 号盘移到 C 柱即可。同理，现在，我们需要将 B 柱上的 2 号盘移到 C 柱，那么此时我们可以借助 A 柱，将 3 号盘先移到 A 柱，此时可以将 B 柱的 2 号盘移到 C 柱了。

最后，直接将 A 柱上的 3 号盘移到 C 柱即可。

N个盘子

从以上的规律，我们总结，如果我们需要将 N 个盘子从 A 柱移到 C 柱，那么我们首先要做的就是将编号为 N 的盘子移到 C 柱上，那么我们一定需要将编号从1 ~ N-1 的盘子移到 B 柱上。

我们需要将 1 ~ N-1 的盘子移到 B 柱上，那么我们一定需要将第 N-2 个盘子移到 C 柱上，接着，才可以将第 N-1 个盘子移到 B 柱。

同理，要将 N-2 个盘子，移到 C 柱上，那么一定需要将 N-3 个盘子移到 B 柱上。由此类推，一直推到 1 个盘子的情况即可。

实现

#include <stdio.h>
void hannuota(int n, char x, char y, char z);
void move(char x, char y);
int main()
{
	printf("嗨客网（www.haicoder.net）\n\n");
	hannuota(3, 'A', 'B', 'C');
}
/**
* n 表示要移动的盘子的个数
* x 表示A柱 
* y 表示B柱
* z 表示C柱
*/
void hannuota(int n, char x, char y, char z)
{
	//递归截止条件，如果就一个盘子，直接从A柱移到C柱即可
	if (n == 1)
	{ 
		move(x, z);
	}
	else
	{
		//先将n-1个盘子从A柱借助C柱移到B柱 
		hannuota(n-1, x, z, y);
		//将A柱上地剩下的一个盘移动到C柱上
		move(x, z);
		//将n-1个盘从B柱借助A柱移动到C柱上
		hannuota(n-1, y, x, z);
	}
}
void move(char x, char y)
{
	printf("将盘子从 %c -> %c\n", x, y);
}

运行结果如下：

我们使用了递归的方式实现了汉诺塔移动的过程，递归的出口就是一个盘子的时候，直接从 A 柱移动 C 柱上，否则，我们就首先将 n -1 个盘子移到 B 柱，接着，将第 n 个盘子从 A 柱移到 C 柱，最后，只需要将 n - 1 个柱子从 B 柱移到 C 柱即可。