暴力递归就是尝试
1）把问题转化为规模缩小了的同类问题的子问题
2）有明确的不需要继续进行递归的条件(base case)
3）有当得到了子问题的结果之后的决策过程
4）不记录每一个子问题的解
补充一点，如果记录每一个子问题的解就是动态规划，后续文章会讲到。
递归方法
假设有3跟柱子，左、中、右，我们细分为如下三个步骤：
1）将1~N-1层圆盘从左 -> 中（大问题，需要继续划分为小问题）
2）将第N层圆盘从左 -> 右（base case）
3）将1~N-1层圆盘从中 -> 右（大问题，需要继续划分为小问题）
递归方法改进版
如果我们忘记柱子的左中右，将三根柱子标记为from、to、other。我们实现的是，将所有的圆盘（一共N层）从from -> to，同样细分为3个步骤：
1）将1~N-1层圆盘从from -> other（大问题，需要继续划分为小问题）
2）将第N层圆盘从from -> to（base case，可以直接打印）
3）将1~N-1层圆盘从other -> to（大问题，需要继续划分为小问题）
貌似没什么改进，因为还是细分这三步，同样要递归，但关键在于忘掉柱子的左中右顺序，只需要三个变量，代码可以少很多。
总结
汉诺塔问题还有非递归的解法，因为任何递归都可以改成非递归，只需要自己设计压栈。但是博主个人认为汉诺塔的递归方法比非递归更好容易理解和实现，非递归自己去设计压栈还比较麻烦，博主目前也还没弄懂，所以就只附上代码了。后面如果搞懂了在补充吧，😄
附上完整代码
package com.harrison.class12; import java.util.Stack; public class Code01_Hanoi { 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); } public 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); } public 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); } public 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); } public 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); } public static void hanoi1(int n) { leftToRight(n); } public static void f(int n,String from,String to,String other) { if(n==1) { System.out.println("move 1 from "+ from + " to " + to); }else { f(n-1, from, other, to); System.out.println("move " + n + " from " +from +" to "+to); f(n-1, other,to,from); } } public static void hanoi2(int n) { if(n>0) { f(n, "left", "right", "mid"); } } public static class Record { public boolean finish1; public int base; public String from; public String to; public String other; public Record(boolean f1, int b, String f, String t, String o) { finish1 = false; base = b; from = f; to = t; other = o; } } public static void hanoi3(int N) { if (N < 1) { return; } Stack<Record> stack = new Stack<>(); stack.add(new Record(false, N, "left", "right", "mid")); while (!stack.isEmpty()) { Record cur = stack.pop(); if (cur.base == 1) { System.out.println("Move 1 from " + cur.from + " to " + cur.to); if (!stack.isEmpty()) { stack.peek().finish1 = true; } } else { if (!cur.finish1) { stack.push(cur); stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to)); } else { System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to); stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from)); } } } } public static void main(String[] args) { int n=3; hanoi1(n); System.out.println("======================="); hanoi2(n); System.out.println("======================="); hanoi3(n); System.out.println("======================="); } }
