1、递归要素
- 明确递归的终止条件
- 提取重复的逻辑，缩小问题的规模不断递去
- 给出递归终止时的处理办法
2、递归应用场景
- 问题的定义是按递归定义的（Fibonacci 函数，阶乘，…）；
- 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；
- 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）。
3、递归与栈的关系
常常听到 “递归的过程就是出入栈的过程”，这句话怎么理解？
从上面的分析的递归问题来看，递归对问题的处理顺序，是遵循了先入后出（先开始的问题最后结束）的规律，这天然地符合栈这种数据结构的特性
递归和栈之间有一种紧密的联系。事实上，大部分的编译器是使用栈来实现递归的。当调用一个方法的时候，编译器会把这个方法的所有参数及其返回地址（这个方法返回时控制达到的地方）都压入栈中，然后把控制转移给这个方法。
当这个方法返回时，这些值退栈。参数消失，并且控制权重新回到返回地址处。
事实上，我们可以把任意一个递归程序转换成一个使用栈的程序。本质上做的转换是本来由编译器来维护的栈，变为由开发人员来维护。
所以两者的关系是："递归算法可以使用数据栈来进行非递归化，同时借助数据栈而实现的非递归算法，也可以被递归化。两者是可逆的
4、如何思考递归
在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的验证之中，比如上面提及的阶乘，求解 Factorial(n) 时，我们总会情不自禁的发问，Factorial(n-1) 可以求出正确的答案么？接着我们就会再用 Factorial(n-2) 去验证……不停地往下验证直到 Factorial(0)。
对递归这样的不适应，和平时习惯的思维方式有关。习惯的思维是：已知 Factorial(0)，乘上 1 就等于 Factorial(1)，再乘以 2 就等于 Factorial(2)……直到乘到 n。
而递归和我们的思维方式正好相反。
那我们怎么判断这个递归计算是否是正确的呢？Paul Graham 提到一种方法：
如果下面这两点是成立的，我们就知道这个递归对于所有的 n 都是正确的。
- 当 n=0,1 时，结果正确；
- 假设递归对于 n 是正确的，同时对于 n+1 也正确。
5、递归解决问题案例
1.1迷宫问题
使用二维数组模拟出一个迷宫，“1”代表城墙，右下角的“0”是终点位置，给一个起点位置，如果在不穿过城墙的情况下可以到达终点。
小球得到的路径，与程序员设置的找路策略有关，即找路的上下左右的顺序。因此我们假定一个找路策略：
- 判断下面是否可以走？
- 下面不行，判断右边是否可以走？
- 右边不行，判断上面是否可以走？
- 上面不行，判断左面是否可以走？
- 如果都不能走，那么这个点就不能走到终点。
每次走的时候都要经历这五个步骤，似乎一直在重复，但是重复的似乎又有点不太一样，这时候就可以用递归的思想来解决
而想要求出最短路径的方法也很简单，只需要要把找路的规则穷举一遍，保存每一种找路规则走的路径长度，然后进行比较即可
public class Maze {
public static void main(String[] args) {
// 先创建一个二维数组，模拟迷宫
int[][] map = new int[8][7];
// 使用1 表示墙
// 上下全部置为1
for (int x = 0; x < 7; x++) {
map[0][x] = 1;
map[7][x] = 1;
}
// 左右全部置为1
for (int x = 0; x < 8; x++) {
map[x][0] = 1;
map[x][6] = 1;
}
//设置挡板, 1 表示
map[3][1] = 1;
map[3][2] = 1;
// 输出地图
System.out.println("地图的情况");
for (int x = 0; x < 8; x++) {
for (int y = 0; y < 7; y++) {
System.out.print(map[x][y] + " ");
}
System.out.println();
}
//使用递归回溯给小球找路
setWay(map, 1, 1);
//输出新的地图, 小球走过，并标识过的递归
System.out.println("\n小球走过，并标识过的地图的情况");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
/**
* 使用递归回溯来给小球找路
* 当 map[x][y] 为 0 表示该点没有走过；当为 1 表示墙；2 表示通路可以走；3 表示该点已经走过，但是走不通
* 在走迷宫时，需要确定一个策略（方法） 下->右->上->左 , 如果该点走不通，再回溯
* @param map 表示地图
* @param x 从哪个位置开始出发的横坐标
* @param y 从哪个位置开始出发的纵坐标
* @return 找到通路 map[6][5]，返回true，否则返回false
*/
public static boolean setWay(int[][]map, int x, int y) {
if (map[6][5] == 2) { // 通路已经找到
return true;
} else {
if (map[x][y] == 0) { // 如果当前这个点还没有走过
map[x][y] = 2; // 假定该点是可以走通.
if(setWay(map, x+1, y)) {//向下走
return true;
} else if (setWay(map, x, y+1)) { //向右走
return true;
} else if (setWay(map, x-1, y)) { //向上
return true;
} else if (setWay(map, x, y-1)){ // 向左走
return true;
} else {
//说明该点是走不通，是死路
map[x][y] = 3;
return false;
}
} else {
// 如果map[i][j] != 0 , 可能是 1， 2， 3
return false;
}
}
}
}1.2 八皇后问题
八皇后问题是一个古老而著名的问题，是回溯算法和递归调用的典型案例。八皇后难题是要将八个皇后（Queen）放在棋盘上，任何两个皇后都不能互相攻击（即没有任意两个皇后是在同一行、同一列或者同一条对角线上），问一共有多少种摆法。
- 第一个皇后先放在第一行第一列
- 第二个皇后放在第二行第一列，然后判断能否在该位置放皇后，如果不可以，则继续放下一列，直至找到一个合适的位置
- 继续放置第三个皇后，还是第一列、第二列…直到第8个皇后也能放在一个不能相互攻击的位置，就找到了一个正确解
- 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯。即将第一个皇后放在第一列的所有解逐个得到
- 完成以上步骤之后，将第一个皇后放在第二列，后面循环执行1, 2, 3, 4 步骤
public class Queue8 {
static int[] array = new int[8]; // 定义数组，保存皇后放置的位置，数组的下标表示的是行，元素的值表示的是该行的皇后摆放在哪一列
static int count = 0;
static int judgeCount = 0;
public static void main(String[] args) {
putQueen(0);
System.out.printf("总共累积判断冲突 %d 次", judgeCount);
}
/**
* 往第 row 行中放入皇后，row 最开始从 0 开始，即从上往下摆
* @param row 第几行
*/
public static void putQueen(int row) {
// 如果 row = 8 了，说明皇后位置已经全部摆放完毕，直接返回
if (row == 8) {
printQueen();
return;
}
for (int column = 0; column < 8; column++) {
// 将皇后放入该位置前判断这个位置放置皇后后是否与其他位置冲突
if (isAccessible(row, column)) {
// 如果不冲突
array[row] = column; // 放入皇后
putQueen(row + 1); // 继续下一行
}
}
}
/**
* 判断该位置能否摆放皇后
* @param row 行数
* @param column 列数
* @return true 为可以摆放；false 为不可以摆放
*/
public static boolean isAccessible(int row, int column) {
judgeCount++; // 判断是否有冲突的
int left = column - 1; // 对角线左上 \
int right = column + 1; // 对角线右上 /
// 从当前行的上一行开始，向上遍历 （没有必要判断当前行的下面几行了，因为下面几行肯定没有放皇后）
for (int i = row - 1; i >= 0; i--) {
// 先判断上面行数的列是否有和该行列冲突的，false 为有冲突
if (array[i] == column) {
return false;
}
// 再判断上面行数的左对角线是否与该点有冲突，false 为有冲突
if (array[i] == left) {
return false;
}
// 最后判断上面行数的右对角线是否与该点有冲突，false 为有冲突
if (array[i] == right) {
return false;
}
// 如果都没有，则继续遍历该行上一行的上一行，以此类推，同时斜对角线的值会变动
left--;
right++;
}
// 如果全部都遍历完了，执行到此处，说明不冲突
return true;
}
/**
* 打印解法
*/
public static void printQueen() {
for (int row = 0; row < 8; row++) {
for (int column = 0; column < 8; column++) {
if (array[row] == column) {
System.out.print("Q ");
}
else {
System.out.print("* ");
}
}
System.out.println();
}
System.out.println("第" + (++count) + "种解法：" + Arrays.toString(array));
}
}
1 条评论