暴力递归
- 将问题转化为规模缩小了的同类问题的子问题。
- 有明确的不需要继续递归的条件（base case）
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
暴力递归的要点大致可以分为以上四条，但是总结起来就是一句话：不断的尝试，所尝即所得。
下面用著名的汉诺塔问题来进行带入讲解。
汉诺塔
简单的阐述一下汉诺塔问题：有3根柱子，依次从左到右排列分别是left、mid、right，假设此时左柱上有1、2、3，3个有小到大的圆盘，每次只能挪动一个圆盘，并且小圆盘要永远在大圆盘之上。几步可以将圆盘从left移到right。
结论：3个圆盘共需要7步
- 1圆盘left -> right
- 2圆盘left -> mid
- 1圆盘right ->mid
- 3圆盘left -> right
- 1圆盘mid -> left
- 2圆盘mid->right
- 1圆盘left -> right
如何用暴力递归解决
上面的7小步可以统一总结为3大步，分别是：
- 上面的2个挪到中间
- 最下层最大的挪到右边
- 中间的两个挪到右边。
再来确定base case（当什么时候我可以随意挪动）：是当圆盘数为1时，如果此时left柱上只剩1个圆盘，那一步就可以直接到right柱。
OK，我们来完善下这部分的代码：
hanoi
public static void hanoi1(int N) {
//主过程从最左挪到最右
leftToRight(N);
}
public static void leftToRight(int N) {
//base case
//当我只剩1层圆盘时，就可以直接从left -> right
if (N == 1) {
System.out.println("Move 1 from left to right");
return;
}
//不止1个圆盘
//想从 left —> right
//第一大步: 先将N - 1位置的圆盘，left -> mid
leftToMid(N - 1);
//第二大步: 上面挪完，将自己 left -> right
System.out.println("Move " + N + " from left to right");
//第三大步 将其他圆盘 mid -> right
midToRight(N - 1);
}
上面已经将整体分为了三大步，并且将主流程和每一步对应的操作流程给了出来，下一步，我们再来深入到每一步的流程。
leftToMid
如果我想将圆盘从left -> mid。是不是依然可以分为3大步：
- 将圆盘从left -> right
- base case 剩我自己时，可以随意挪动
- 将其余圆盘从right -> mid。
我们再来完善这部分的细节代码：
public static void leftToMid(int N) {
if (N == 1) {
System.out.println("Move 1 from left to mid");
return;
}
leftToRight(N - 1);
System.out.println("Move " + N + " from left to mid");
rightToMid(N - 1);
}
其余主流程剩余的midToRight，是不是也同理。所以完整代码如下：
public static void hanoi1(int N) {
leftToRight(N);
}
public static void leftToRight(int N) {
if (N == 1) {
System.out.println("Move 1 from left to right");
return;
}
leftToMid(N - 1);
System.out.println("Move " + N + " from left to right");
midToRight(N - 1);
}
public static void leftToMid(int N) {
if (N == 1) {
System.out.println("Move 1 from left to mid");
return;
}
leftToRight(N - 1);
System.out.println("Move " + N + " from left to mid");
rightToMid(N - 1);
}
private static void midToRight(int N) {
if (N == 1) {
System.out.println("Move 1 from mid To right");
return;
}
midToLeft(N - 1);
System.out.println("Move " + N + " from mid to right");
leftToRight(N - 1);
}
private static void midToLeft(int N) {
if (N == 1) {
System.out.println("Move 1 from mid to left");
return;
}
midToRight(N - 1);
System.out.println("Move " + N + " from mid to left");
rightToLeft(N - 1);
}
private static void rightToLeft(int N) {
if (N == 1) {
System.out.println("Move 1 from right to left");
return;
}
rightToMid(N - 1);
System.out.println("Move " + N + " from right to left");
midToLeft(N - 1);
}
private static void rightToMid(int N) {
if (N == 1) {
System.out.println("Move 1 from right to mid");
return;
}
rightToLeft(N - 1);
System.out.println("Move " + N + " from right to mid");
leftToMid(N - 1);
}
OK，汉诺塔的问题已经解决了，整体的思路就是先规划好整体的几大步并确定base case，在根据大的步骤完善细节。
但是不知道你们有没有发现，虽然解决了汉诺塔问题，但是代码太过冗余，left -> mid , left -> right , mid -> right , mid -> left，每一个都对应着两个方法。
那我们不妨将问题稍微抽象化一点，加一些参数，来简化这个方法。
抛去left，mid和right的概念，我们此时只有from to 和other，圆盘的目的是从from到to，我们依然分为3步来看：
- base case依然是当圆盘数为 1 时， 可以随意挪动。 这点无可厚非。
- 第一步： 想要圆盘数为 1 的话，还是要将N - 1的圆盘全部挪到其他圆盘上，但是此时，圆盘都在from，应该是从from -> to， to是谁？ to应该是上面提到的other吧，只有将N - 1圆盘从 from 挪到了other上，最后一个圆盘才可以从from -> to。
- 第二步：此时，from上只剩一个圆盘，可以直接挪动从from -> to
- 第三步：是不是这一步再将N - 1挪到to上，整个汉诺塔问题就完成了。 怎么挪 ？ 第一步将 N - 1从from挪到other，此时other是不是就是那个 from，to不变，from变成了other的概念。
将问题稍微抽象一些，并且增加了几个参数，此时再来看一看优化后的代码：
hanoi2
public static void hanoi2(int N) {
func(N, "left", "right", "mid");
}
public static void func(int N, String from, String to, String other) {
if (N == 1) {
System.out.println("Move 1 from " + from + " to " + to);
} else {
func(N - 1, from, other, to);
System.out.println("Move " + N + " from " + from + " to " + to);
func(N - 1, other, to, from);
}
}
