第五章 递归
一、递归
1.概念
简单的说，递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁
2.代码实现
package com.sisyphus.recursion;
public class RecursionTest {
public static void main(String[] args) {
//通过打印问题，回顾递归调用机制
test(4);
int res = factorial(3);
System.out.println("res= " + res);
}
//打印问题
public static void test(int n){
if (n > 2){
test(n - 1);
}
System.out.println("n=" + n);
}
//阶乘问题
public static int factorial(int n){
if(n == 1){
return 1;
}else{
return factorial(n - 1) * n;
}
}
}
3.递归的规则
- 执行一个方法时，创建一个新的受保护的独立空间（栈空间）
- 方法的局部变量需要是独立的，不会相互影响
但如果方法中使用的时引用类型变量（比如数组），就会共享该引用类型的数据 - 递归必须向退出递归的条件逼近，否则就会无限递归，出现 StackOverflowError
- 当一个方法执行完毕，或者遇到 return，就会返回，谁调用就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕
二、迷宫回溯
1.要求
- 使用递归
- 能从地图任一点出发，到达任一点
2.代码实现
package com.sisyphus.recursion;
public class Maze {
public static void main(String[] args) {
//先创建一个二维数组，模拟迷宫
//地图
int[][] map = new int[8][7];
//使用 1 表示墙
//上下全部置为 1
for(int i = 0; i < 7; i++){
map[0][i] = 1;
map[7][i] = 1;
}
//左右全部置为 1
for (int i = 0; i < 8; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
//设置障碍,第一次测试
map[3][1] = 1;
map[3][2] = 1;
// //设置障碍，第二次测试，将路堵死
// map[3][1] = 1;
// map[3][2] = 1;
// map[1][2] = 1;
// map[2][2] = 1;
//输出地图
System.out.println("地图的情况");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
//使用递归回溯给小球找路
setWay(map,1,1);
//输出新的地图，小球走过，并标记过的地图
System.out.println("地图的情况");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
//使用递归回溯来给小球找路
//说明
//1.map 表示地图
//2.i，j 表示从地图的哪个位置开始触发
//3.如果小球能到达 map[6][5] 位置，则说明通路找到了
//4.约定：当 map[i][j] 为 0 时表示该点没有走过，为 1 表示墙，为 2 表示通路可以走，为 3 表示该点已经走过，但是走不通
//5.在走迷宫时，需要确定一个策略：下 -> 右 -> 上 -> 左，如果该店走不通，再回溯
/**
*
* @param map 表示地图
* @param i 从哪一行开始找
* @param j 从哪一列开始找
* @return 如果找到通路，就返回 true，否则返回 false
*/
public static boolean setWay(int[][] map, int i, int j){
if(map[6][5] == 2){ //通路已经找到
return true;
}else{
if (map[i][j] == 0){//如果当前这个点还没有走过
//按照策略 下 -> 右 -> 上 -> 左 的方式寻路
map[i][j] = 2; //假定该点是可以走通的
if (setWay(map,i+1,j)){//向下走
return true;
}else if (setWay(map,i,j+1)){//向右走
return true;
}else if (setWay(map,i-1,j)){//向上走
return true;
}else if (setWay(map,i,j-1)) {//向左走
return true;
}else{
//说明该点是走不通的
map[i][j] = 3;
return false;
}
}else{ //如果 map[i][j] ！= 0，可能是 1，2，3
return false;
}
}
}
}
第一次测试：
道路通畅，地图只有 0，1，2 没有出现回溯现象
第二次测试：
道路被堵死，地图出现了 3 ，有回溯现象
三、八皇后问题
1.介绍
八皇后问题是由国际西洋棋棋手马克思·贝瑟于 1848 年提出的问题，是回溯算法的典型案例
问题表述为：在 8 × 8 的国际象棋上摆放 8 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。数学家高斯认为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。如果经过 ± 90 度、± 180 度旋转和对角线对称变换的摆法看成一类，共有 42 类。计算机发明后，有多种计算机语言可以编程解决此问题
2.思路
穷举法
如果用穷举法需要尝试 8^8=16,777,216 种情况，每一列放一个皇后，可以放在第 1 行，第 2 行，……，直到第 8 行。穷举的时候从所有皇后都放在第 1 行的方案开始，检验皇后之间是否会相互攻击。如果会，把列 H 的皇后挪一格，验证下一个方案。移到底了就 ”进位“ 到列 G 的皇后挪一格，列 H 的皇后重新试过全部的 8 行。这种方法是非常低效率的，因为它并不是哪里有冲突就调整哪里，而是盲目地按既定顺序枚举所有的可能方案
回溯算法
回溯算法优于穷举法。将列 A 的皇后放在第一行以后，列 B 的皇后放在第一行已经发生冲突。这时候不必继续放列 C 的皇后，而是调整列 B 的皇后到第二行，继续冲突放第三行，不冲突了才开始进入列 C。如此可依次放下列 A 至 E 的皇后，将每个皇后往右边横向、斜向攻击的点位用叉标记，发现列 F 的皇后无处安身。这时回溯到列 E 的皇后，将其位置由第 4 行调整为第 8 行，进入列 F，发现皇后依然无处安身，再次回溯到列 E。此时列 E 已经枚举完所有情况，回溯至列 D，将其由第 2 行移至第 7 行，再进入列 E 继续。按此算法流程最终找到如上图所示的解，成功在棋盘里放下了 8 个 ”和平共处“ 的皇后。继续找完全部的解共 92 个
回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往后退，走到最后是答案。为了加快有无冲突的判断速度，可以给每行和两个方向的每条对角线是否有皇后占据建立标志数组。放下一个新皇后做标志，回溯时挪动一个旧皇后清除标志
- 第一个皇后先放在第一行的第一列
- 第二个皇后放在第二行的第一列，然后判断是否冲突，如果冲突，继续放在第二列、第三列，……，依次把所有列都放完，找到一个不冲突的位置
- 放第三个皇后，还是第一列、第二列，……，直到第 8 个皇后也能放在一个不冲突的位置，找到一个正确解
- 当得到一个正确解时，栈回退到上一个栈，然后开始回溯。得到第一个皇后放在第一行第一列的所有解
- 回到第一步把第一个皇后放在第一行的第二列
理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题
arr[8] = {0, 4, 7, 5, 2, 6, 1, 3}
arr 的下标表示第 n + 1 行的皇后，arr[n+1] 表示第 n + 1 个皇后放在第几列
3.代码实现
package com.sisyphus.recursion;
/**
* @Description: $
* @Param: $
* @return: $
* @Author: Sisyphus
* @Date: $
*/
public class EightQueens {
//定义一个 max 表示共有多少个皇后
int max = 8;
//定义数组 array，保存皇后放置位置的结果
int[] array = new int[max];
static int count = 0;//保存解法数量
static int judgeCount = 0;//保存判断冲突的次数
public static void main(String[] args) {
//测试
EightQueens eightQueens = new EightQueens();
eightQueens.check(0);
System.out.printf("一共有%d种解法",count);
System.out.printf("一共判断了%d次冲突",judgeCount);
}
//编写一个方法，放置第 n 个皇后
//特别注意：每一次递归时，只要没找到解进入到 check 中都会进行一次 for 循环，因此会产生回溯
private void check(int n){
if (n == max){ //n = 8,即 8 个皇后都放好了
print();
return;
}
//依次放入皇后，并判断是否冲突
for (int i = 0; i < max; i++) {
//先把当前这个皇后 n，放到该行的第 1 列
array[n] = i;
//判断当放置第 n 个皇后到 i 列时，是否冲突
if (judge(n)){ //不冲突
//接着放 n + 1 个皇后，即开始递归
check(n + 1);
}
//如果冲突，就继续执行 array[n] = i; 即把第 n 个皇后，放置在本行的下一列
}
}
//查看当我们放置第 n 个皇后时，检测该皇后是否和前面已经摆放的皇后冲突
/**
*
* @param n 表示第 n 个皇后
* @return
*/
private boolean judge(int n){
judgeCount++;//判断的次数
for (int i = 0; i < n; i++) {
//说明
//1.array[i[ == array[n] 表示判断第 n 个皇后是否和前面的 n - 1 个皇后在同一列
//2.Math.abs(n - i) == Math.abs(array[n] - array[i]) 表示判断第 n 个皇后是否和第 i 个皇后在同一斜线
//3.判断是否在同一行，没有必要，n 每次都在递增
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])){
return false;
}
}
return true;
}
//写一个方法，可以将皇后摆放的位置输出
private void print(){
count++;//只有成功才会打印，因此在打印方法里计数
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
