1、递归的概念
简单来说，递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得更简洁。代价就是当递归次数过高时会占用过多的计算机资源。
2、递归要遵守的重要规则
1、执行一个方法时，就创建一个新的受保护的独立空间（栈空间）；
2、方法的局部变量是独立的，不会相互影响；
3、如果使用的是引用类型变量，会共享该引用类型的数据；
4、递归必须向推出条件逼近，否则就无限递归，出现内存爆炸；
5、一个方法执行完毕或者遇到return，谁调用就把返回结果给谁。
3、递归的运用
3.1 迷宫问题
3.1.1 问题描述
假设有以下这样子的迷宫，由7×7的格子组成，红色各自表示墙壁，不能走，白色部分是可以走。假设（1，1）是起点，（6，6）是终点，编写程序把起点到终点走过的路线标出来。
3.1.2 代码实现
package cn.klb.datastructures.recursion;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 给定地图、起点和终点，找出路线
* @Date: Create in 2023/4/3 12:18
* @Modified By:
*/
public class Labyrinth {
private int[][] map; // 二维数组表示地图
/**
* 初始化地图
*
* @param map
*/
public Labyrinth(int[][] map) {
this.map = map;
// 左右设置墙
for (int i = 0; i < this.map.length; i++) {
this.map[i][0] = 1; // 左边墙设置为1
this.map[i][this.map.length - 1] = 1; // 右边墙设置为1
}
// 上下设置墙
for (int i = 0; i < this.map[0].length; i++) {
this.map[0][i] = 1;
this.map[this.map[0].length - 1][i] = 1;
}
// 设置障碍
this.map[3][1] = 1;
this.map[3][2] = 1;
}
/**
* 打印地图
*/
public void showMap() {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
/**
* 根据起点找出走到以地图最右下角为终点的路线
* map[i][j] 默认值为 0 表示该点为未走过
* map[i][j] 设置为 2 表示该点为通路
* map[i][j] 设置为 3 表示该点走过，但是不是通路
* 走路逻辑：下 右 上 左
*
* @param i 起点横坐标
* @param j 起点纵坐标
* @return
*/
public boolean go1(int i, int j) {
// 如果终点标记为2，说明路线已经走完并且走成功了
if (map[map.length - 2][map.length - 2] == 2) {
return true;
} else {
// 如果终点标记不为2，说明还没走完
if (map[i][j] == 0) {
// 如果这个点未走过
map[i][j] = 2; // 假定这个点可以走，如果下面走不通再把它设为3
if (go1(i + 1, j)) {
// 如果往下方走一步是可以走的，说明当前位置是通路
return true;
} else if (go1(i, j + 1)) {
// 下方走不通，如果右边走的通，说明当前位置是通路
return true;
} else if (go1(i - 1, j)) {
// 右边也走不了，那就尝试走上边
return true;
} else if (go1(i, j - 1)) {
// 上边也走不了，那就尝试走左边
return true;
} else {
// 上下左右都不能走，说明当前位置是死路
map[i][j] = 3; // 打破了前面的假设，把当前点设置为3
return false;
}
} else {
// 如果这个点已经走过了，就不能再走了
return false;
}
}
}
/**
* 根据起点找出走到以地图最右下角为终点的路线
* map[i][j] 默认值为 0 表示该点为未走过
* map[i][j] 设置为 2 表示该点为通路
* map[i][j] 设置为 3 表示该点走过，但是不是通路
* 走路逻辑：右 上 左 下
*
* @param i 起点横坐标
* @param j 起点纵坐标
* @return
*/
public boolean go2(int i, int j) {
// 如果终点标记为2，说明路线已经走完并且走成功了
if (map[map.length - 2][map.length - 2] == 2) {
return true;
} else {
// 如果终点标记不为2，说明还没走完
if (map[i][j] == 0) {
// 如果这个点未走过
map[i][j] = 2; // 假定这个点可以走，如果下面走不通再把它设为3
if (go2(i, j + 1)) {
return true;
} else if (go2(i - 1, j)) {
return true;
} else if (go2(i, j - 1)) {
return true;
} else if (go2(i+1, j)) {
return true;
} else {
// 上下左右都不能走，说明当前位置是死路
map[i][j] = 3; // 打破了前面的假设，把当前点设置为3
return false;
}
} else {
// 如果这个点已经走过了，就不能再走了
return false;
}
}
}
}
3.3 八皇后问题
3.3.1 问题描述
八皇后问题是一个注明的问题，是递归算法的典型案例。再8×8的国际象棋上摆放八个皇后，任意两个皇后不能处于同一行、同一列或同一斜线上，问有多少种摆法。
3.3.2 算法思路
1、第一个皇后先放在第一行第一列；
2、第二个皇后放在第二行第一列，然后判断和上一个皇后是否冲突，不冲突则放下一个皇后，冲突则第二个皇后放到第二行第二列，再次判断，直到不冲突；
3、放置第三个皇后，还是放在第三行的第一列，然后判断和前面的皇后是否冲突，以此类推；
4、当得到一个正确的解时，在栈回退到上一个栈时，就会开始回溯，即第一个皇后放到第一列的所有正确解；
5、然后回头继续第一个皇后放到第一行第二列，依此循环上面步骤。
说明：理论上可以创建要给二维数组来表示棋盘，但是通过算法实际上可以用一个一维数组来解决问题，arr[8]={0,1,2,3,4,5,6,7}，arr[i] = val表示第 i+1 个皇后放在第 i+1 行第 val+1 列。
3.3.3 代码实现
package cn.klb.datastructures.recursion;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description:
* @Date: Create in 2023/4/3 14:06
* @Modified By:
*/
public class Queen8 {
private int max;
private int[] array; // 默认，第i个皇后放在第i行，数组保存的是该行的第几列
public int count = 0;
// 皇后的数量
public Queen8(int max) {
this.max = max;
array = new int[this.max];
this.check(0);
}
/**
* 放置第 n 个皇后
*/
private void check(int n) {
if (n == max) {
// n==max说明所有皇后都已经放好了
showQueen8();
return;
}
// 依此放入皇后并检查是否冲突
for (int i = 0; i < max; i++) {
array[n] = i; // 把第n个皇后放到该行第i列上
if (judge(n)) {
// 如果放在该位置没问题，就继续放置下一个皇后
check(n + 1);
}
// 如果冲突了，就把当前皇后往下一列移动一格
}
}
/**
* 放置了第n个皇后，判断是否和前面放的有冲突
*
* @param n
* @return
*/
private boolean judge(int n) {
for (int i = 0; i < n; i++) {
// 说明
// array[i] == array[n] 表示判断第n个皇后是否和前面的n-1个皇后在同一列
// Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
/**
* 显示摆放好的八皇后
*/
public void showQueen8() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}