哈诺塔问题相信只要学习计算机的人都知道。这是一个古老而又伟大的问题。在这篇文章中，主要是给出递归解决汉诺塔问题的代码方法。毕竟面试的时候，HR比我们要变态很多，怎么蹂躏我们怎么玩。
一、什么是汉诺塔问题
这个问题来源于印度。有三个金刚石塔，第一个从小到大摞着64片黄金圆盘。现在把圆盘按大小顺序重新摆放在最后一个塔上。并且规定，在小圆盘上不能放大圆盘，在三个塔之间一次只能移动一个圆盘。
image
也就是说将 from 上的圆盘全部移动到 to 上，并且要保证小圆盘始终在大圆盘上。
如何来求解呢？很明显这道题大家都知道使用递归的方式来做。不过如何去考虑递归呢？
在这里我想说一下我个人目前关于递归的理解。递归其实就是一个方程式：f(n) = f(n-1) + a;也就是说在设计递归的时候应该考虑下面三个方面：
（1）求解f(n)的时候，假设f(n-1)已经求解出来了。我们不要去考虑f(n-1)是如何求解出来的。
（2）关键点在于递归的结束条件。
（3）递归往往和分治法是分不开的。对于复杂的递归，往往将递归拆分。然后再合并
整体的递归方法流程是这样的。首先我们要写一个递归方法。
（1）首先判断递归结束时候的操作
（2）递归分解
而本题的汉诺塔就是使用典型的递归思想。首先我们求解f(n)
① 将 n-1 个圆盘从 from -> buffer
image
② 将 1 个圆盘从 from -> to
image
③ 将 n-1 个圆盘从 buffer -> to
image
④以上三步都是为了求解f(n)，最后我们给出递归结束的条件。只有一个圆盘的时候，只需一次移动操作即可。
二、代码实现
public class Hanoi {
public static void move(int n, String from, String buffer, String to) {
//第一步：递归结束的条件
if (n == 1) {
System.out.println("from " + from + " to " + to);
return;
}
// n-1 个圆盘从 from -> buffer
move(n - 1, from, to, buffer);
//将 1 个圆盘从 from -> to
move(1, from, buffer, to);
//将 n-1 个圆盘从 buffer -> to
move(n - 1, buffer, from, to);
}
public static void main(String[] args) {
Hanoi.move(3, "石柱1", "石柱2", "石柱3");
}
}
image
