递归全解析：概念、应用场景、调用机制与遵循规则
一、递归应用场景
来看一个实际的应用场景，即迷宫问题（回溯），还有递归（Recursion）。
二、递归的概念
简单来说：递归就是一种方法会自己去调用自己，并且在每次调用的时候会传入不一样的变量。递归能够帮助编程者去处理复杂的问题，同时也能够让代码变得更加简洁。
三、递归调用机制
通过两个小案例，了解递归调用机制
3.1、打印问题
public class RecursionTest {
公共静态 void 主函数（字符串数组 args）{ }
//通过打印问题，回顾递归调用机制
test(4);
}
//打印问题
它会根据传入的参数 n 来进行相应的处理。
if (n > 2) {
test(n - 1);
} //else {
System.out.println("n=" + n);
// }
}
}3.2、阶乘问题
public class RecursionTest {
public static void main(String[] args) {
int res = factorial(3);
System.out.println("res 等于 " + res);
}
//阶乘问题
如果 n 小于 0，返回 -1；如果 n 等于 0 或 1，返回 1；否则，通过循环计算阶乘，初始结果为 1，每次循环将当前结果乘以当前的 n 值，然后 n 减 1，直到 n 等于 0，最后返回计算得到的阶乘结果。
if (n == 1) {
return 1;
} else {
使用 n - 1 调用阶乘函数得到结果，再将该结果与 n 相乘；即先计算 n - 1 的阶乘，然后乘以 n；就像计算 1 * 2 * 3 那样，先计算 2 的阶乘，再乘以 3 。
}
}
}
四、递归能解决什么样的问题
各种数学问题，例如 8 皇后问题、汉诺塔、阶乘问题、迷宫问题以及球和篮子的问题（谷歌编程大赛）。
各种算法中会用到递归。例如快排会使用递归。归并排序也会使用递归。二分查找会使用递归。分治算法同样会使用递归。
3、将用栈解决的问题-->第归代码比较简洁
五、递归需要遵守的重要规则
执行一个方法时，会创建一个新的空间。这个空间是受保护的、独立的，属于栈空间。
2、方法的局部变量是独立的，不会相互影响, 比如n变量
如果方法中使用的是引用类型变量，比如数组，那么就会共享该引用类型的数据。
递归需要朝着退出递归的条件靠近。如果做不到这一点，就会出现无限递归的情况，进而引发 StackOverflowError，就像乌龟死了一样。
当一个方法执行完毕后，或者遇到 return 时，就会进行返回操作。它遵守谁调用就将结果返回给谁的原则。并且，当方法执行完毕或者返回时，该方法也就完成了执行。
六、递归-迷宫问题
6.1、先创建一个二维数组，模拟迷宫
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;
}
//设置挡板, 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);
//setWay2(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();
}
}6.2、说明:
小球所得到的路径，与程序员设置的找路策略有关，具体来说就是与找路时上下左右的顺序相关。
得到小球路径后，可先采用（下右上左）的方式，接着改为（上右下左），然后观察路径是否发生变化。
3、测试回溯现象
思考: 如何求出最短路径?
6.3、使用递归回溯来给小球找路
1、map 表示地图
2、i,j 表示从地图的哪个位置开始出发 (1,1)
如果小球能够到达 map[6][5]这个位置，那就意味着通路已经被找到了。
map[i][j] 为 3 时，表示该点已经走过但走不通。
在走迷宫的过程中，需要明确一个策略，也就是下->右->上->左。如果走到某个点走不通了，就需要进行回溯。
/**
*
* @param map 表示地图
* @param i 从哪个位置开始找
* @param j
如果找到了通路，就会返回 true；如果没有找到通路，就会返回 false。
*/
确定一个策略（方法），先向下走，接着向右走，然后向上走，最后向左走。如果在这个点走不通，就进行回溯。
静态的布尔值是否可以设置路径（int[][] 类型的地图，int 类型的 i，int 类型的 j）？
如果地图中第 6 行第 5 列的元素等于 2，那么通路已经找到 ok。
return true;
} else {
如果 map[i][j] 的值为 0，那就意味着当前这个点还没有走过。
//按照策略 下->右->上->左 走
map[i][j] = 2; // 假定该点是可以走通.
如果将值设置到 map 中，位置为 i + 1 和 j ，那么就向下走。
return true;
如果将路径设置在地图上，并且当前位置的下一个位置是向右移动一格的位置（即 i 不变，j 加 1），那么就可以向右走。
return true;
否则如果在地图上向上移动是可行的（通过调用 setWay 函数并传入地图、当前位置的行索引减 1 和列索引），则执行相应操作
return true;
如果通过 setWay(map, i, j - 1) 这个条件判断成立，那么就向左走。
return true;
} else {
//说明该点是走不通，是死路
map[i][j] = 3;
return false;
}
如果 map[i][j] 不等于 0 ，那么它可能是 1 ，也可能是 2 ，还可能是 3 。
return false;
}
}
}
//修改找路的策略，改成 上->右->下->左
如果地图 map 中坐标 (i, j) 的值为 0 ，则将其值设置为 2 并返回 true ；否则返回 false 。
if(map[6][5] == 2) { // 通路已经找到ok
return true;
} else {
if(map[i][j] == 0) { //如果当前这个点还没有走过
//按照策略 上->右->下->左
map[i][j] = 2; // 假定该点是可以走通.
如果 setWay2(map, i - 1, j) 成立，那么就意味着向上走。
return true;
如果在地图 map 上，从当前位置 (i, j) 向右走一步是可行的，即 setWay2(map, i, j + 1) 返回 true ，那么就可以向右走。
return true;
如果在地图 map 中，从当前位置 (i, j) 向下移动是可行的，即调用 setWay2(map, i + 1, j) 返回 true ，那么就执行相应的操作。
return true;
要是在地图 map 上，在坐标 (i, j-1) 处能够进行路径设置，那就向左走。
return true;
} else {
//说明该点是走不通，是死路
map[i][j] = 3;
return false;
}
} else { // 如果map[i][j] != 0 , 可能是 1， 2， 3
return false;
}
}
}七、递归-八皇后问题 7.1、八皇后问题介绍
八皇后问题是一个古老且著名的问题，它是回溯算法的典型案例。这个问题是由国际西洋棋棋手马克斯·贝瑟尔在 1848 年提出的。在 8×8 格的国际象棋棋盘上摆放八个皇后，要使它们不能互相攻击，也就是任意两个皇后都不能处于同一行、同一列或同一斜线上，需要探究有多少种摆法。
7.2、解题思路
1) 第一个皇后先放第一行第一列
第二个皇后放置在第二行第一列，接着对其进行是否 OK 的判断（也就是判断是否有冲突）。倘若不 OK，就继续放置在第二列，然后放置在第三列，依次将其放置在所有列，直至找到一个合适的位置。
继续放置第三个皇后，从第一列开始尝试，接着是第二列……一直到第八个皇后也能被放置在一个不会产生冲突的位置，这样就找到了一个正确的解。
当获得一个正确解时，栈回退到上一个栈的位置，就会开始回溯过程。这个回溯过程意味着要将第一个皇后放置在第一列的所有可能的正确解都要全部获取到。
接着回头接着放置第一个皇后在第二列，之后持续按照 1、2、3、4 的步骤进行循环操作
7.3、说明
理论上应当创建一个二维数组去表示棋盘，然而实际上凭借算法，仅用一个一维数组就能解决问题。比如 ar[8]=(0,4,7,5,2,6,1,3)，这里的下标对应着 an，它表示的是第几行，也就是第几个皇后，而 ami]=val，其中 val 表示第 i+1 个皇后，是放在第 i+1 行的第 val+1 列。
7.4、代码实现
public class Queue8 {
//定义一个max表示共有多少个皇后
int max = 8;
定义一个数组叫做 array，其作用是保存皇后放置位置的结果，例如 arr 可以是 {0, 4, 7, 5, 2, 6, 1, 3} 。
int[] array = new int[max];
static int count = 0;
static int judgeCount = 0;
public static void main(String[] args) {
//测试，8皇后是否正确
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out 会打印出“一共有”加上 count 的值再加上“解法”这样的内容，其中 count 表示解法的数量，最终输出的是一共有多少种解法的信息。
System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w 可翻译为“一万五千”，但因禁止翻译英文单词，所以保留原文数字形式
}
//编写一个方法，放置第n个皇后
特别注意：在每一次递归时，进入到 check 中都要进行 for 循环，循环的条件是 int i = 0；并且 i 要小于某个值；然后在循环内部进行相关操作。< max; i++)，因此会有回溯
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皇后是否在同一斜线（同一斜线上斜率为+-1）
// n = 1 放置第 2列 1 n = 1 array[1] = 1
// Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
//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();
}
}
phper