打印n层汉诺塔从最左边移动到最右边的全部过程

暴力递归就是尝试

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("=======================");
	}
}