递归回溯 迷宫 汉诺塔 八皇后
递归
递归，简单地说就是方法自己调用自己，每次调用时传入不同的变量。
使用递归，可以有助于我们解决复杂问题，同时可以使代码保持简洁。
递归解决问题：
- 复杂的数学问题。如：迷宫问题、八皇后问题、阶乘问题、汉诺塔等。
- 很多算法也会用到递归。如：快速排序、归并排序、二分查找、分治算法等。
使用递归注意事项：
- 每次递归调用执行一个方法，就创建一个新的受保护的独立的栈空间；
- 方法局部变量都是独立的，不会互相影响；
- 如果方法中传参使用的是引用类型变量(如数组、链表、队列、栈、List)，就会共享该引用类型的数据；
- 递归调用必须逐步逼近退出递归的条件，否则会无限递归，虚拟机会抛出
StackOverflowError异常，退出程序； - 当一个方法调用完成后或遇到
return，就会返回发起调用它的方法，谁调用，就将返回结果返回给谁。
递归的应用
迷宫问题
该问题是一个小球从迷宫的起点出发，怎么走才能到达终点。
实现代码：
/**
* 小球走迷宫
* <br />
* 一个小球充下面的地图"S"点开始出发，走到"E"到达终点
* S：起点
* E：终点
* <pre>
* 1 1 1 1 1 1 1
* 1 S 0 0 0 0 1
* 1 0 0 0 0 0 1
* 1 1 1 0 0 0 1
* 1 0 0 0 0 0 1
* 1 0 0 0 0 0 1
* 1 0 0 0 0 E 1
* 1 1 1 1 1 1 1
* </pre>
* @author jyoryo
*/
public class Maze {
public static void main(String[] args) {
// 迷宫地图
int [][] map = new int[8][7];
// 上下墙
for(int i = 0; i < 7; i++) {
map[0][i] = 1;
map[7][i] = 1;
}
// 左右墙
for(int i = 0; i < 8; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
// 障碍物
map[3][1] = 1;
map[3][2] = 1;
print(map);
run(map, 1, 1);
System.out.println("~~~完成迷宫~~~");
print(map);
}
/**
* 走法
* 地图上每个点值说明：0:表示该点没有走过； 1:表示墙； 2:表示通路可以走； 3:表示该点走过，但是走不通
* @param map 地图
* @param i 出发点行索引
* @param j 出发点列索引
* @return
*/
public static boolean run(int[][] map, int i, int j) {
// 到终点
if(map[6][5] == 2) {
print(map);
return true;
}
// 该点没有走过，开始走
if(map[i][j] == 0) {
/*
* 走的策略：下→右→上→左
*/
map[i][j] = 2;
// 下走
if(run(map, i + 1, j)) {
return true;
}
// 右走
else if(run(map, i, j + 1)) {
return true;
}
// 上走
else if(run(map, i - 1, j)) {
return true;
}
// 左走
else if(run(map, i, j - 1)){
return true;
}
// 走不通,回溯更改
else {
map[i][j] = 3;
return false;
}
}
return false;
}
// 打印地图
private static void print(int [][] array) {
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array[i].length; j++) {
System.out.printf("%d\t", array[i][j]);
}
System.out.println();
}
}
}汉诺塔问题
汉诺塔算法的思路：
- 把第
n-1个盘子由A移到B； - 把第
n个盘子由A移到C； - 把第
n-1个盘子由B移到C。
实现代码如下：
public class TowerOfHanoi {
private static int counter = 0; // 计数器
public static void main(String[] args) {
char a = 'A', b = 'B', c = 'C';
System.out.println("请输入圆盘数：");
Scanner scanner = new Scanner(System.in);
int number = scanner.nextInt();
hanoi(number, a, b, c);
scanner.close();
}
public static void hanoi(int n, char a, char b, char c) {
if(1 == n) {
move(1, a, c);
return ;
}
// 递归，将A上的编号{n - 1}盘移动到B， C为辅助塔
hanoi(n - 1, a, c, b);
// 将编号为{n}盘移动到C
move(n, a, c);
// 递归，将B上的编号{n - 1}盘移动到C， A为辅助塔
hanoi(n - 1, b, a, c);
}
public static void move(int diskNo, char from, char to) {
System.out.printf("第%d次移动，将%d号盘从%s→%s。\n", ++counter, diskNo, from, to);
}
}八皇后问题
public class EightQueensPuzzle {
// 使用一维数组表示，数组索引表示所在行；对应值为该行皇后排放的列
int max = 8;
int [] array = new int[max];
int counter = 0;
public static void main(String[] args) {
EightQueensPuzzle queensPuzzle = new EightQueensPuzzle();
queensPuzzle.queue(0);
System.out.printf("一共由%d种摆法！", queensPuzzle.counter);
}
// 排放第n个皇后
private void queue(int n) {
// 8皇后都已摆放好
if(n == max) {
print();
return ;
}
for(int i = 0; i < max; i++) {
array[n] = i;
// 不冲突
if(valid(n)) {
queue(n + 1);
}
}
}
// 当放置第n个皇后，检测是否与前已排的有冲突(同一行、同一列、同一斜线)
private boolean valid(int n) {
for(int i = 0; i < n; i++) {
// array[i] == array[n] 表示在同一列
// Math.abs(n - 1) == Math.abs(array[n] - array[i]) 表示在同一斜线上
if(array[i] == array[n] || (Math.abs(n - i) == Math.abs(array[n] - array[i]))) {
return false;
}
}
return true;
}
// 打印
private void print() {
counter ++;
for(int i = 0; i < array.length; i++) {
System.out.printf("%d\t", array[i]);
}
System.out.println();
}
}