Question

汉诺塔递归算法是什么？

Answer 1

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

注意：

我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求。

这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。

现这个算法可以简单分为三个步骤：

（1）  把n-1个盘子由A 移到 B。

（2）把第n个盘子由 A移到 C。

　（3） 把n-1个盘子由B 移到 C。

从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：

（1）中间的一步是把最大的一个盘子由A移到C上去。

（2）中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上。

（3）中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上。