递归(Recursion)

介绍

​ 简单的说, 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

递归小案例

打印问题:

1
2
3
4
5
6
public static void test(int n) {
if (n > 2) {
test(n - 1);
}
System.out.println("n=" + n);
}

阶乘问题:

1
2
3
4
5
6
7
public static int factorial(int n) {
if (n == 1) {
return 1;
} else {
return factorial(n - 1) * n;
}
}

递归应用场景

  1. 各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
  2. 各种算法中也会使用到递归,比如快排,归并排序,二分查找,分治算法等
  3. 将用栈解决的问题使用递归代码比较简洁

递归需要遵守的重要规则

  1. 执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
  2. 方法的局部变量是独立的,不会相互影响
  3. 如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据
  4. 递归必须向退出递归的条件逼近,否则就是无限递归,出现StackOverflowError异常
  5. 当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕。

回溯(Backtrack)

介绍

​ 回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。

回溯和递归的区别

递归是一种算法结构。递归会出现在子程序中,形式上表现为直接或间接的自己调用自己。

回溯是一种算法思想。它是用递归实现的。回溯的过程类似于穷举法,但回溯有“剪枝”功能,即自我判断过程。例如有求和问题,给定有 7 个元素的组合 [1, 2, 3, 4, 5, 6, 7],求加和为 7 的子集。累加计算中,选择 1+2+3+4 时,判断得到结果为 10 大于 7,那么后面的 5, 6, 7 就没有必要计算了。这种方法属于搜索过程中的优化,即“剪枝”功能。

用一个比较通俗的说法来解释递归和回溯:
我们在路上走着,前面是一个多岔路口,因为我们并不知道应该走哪条路,所以我们需要尝试。尝试的过程就是一个函数。
我们选择了一个方向,后来发现又有一个多岔路口,这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上,再做一次尝试,即在函数内部再调用一次函数,这就是递归的过程。
这样重复了若干次之后,发现这次选择的这条路走不通,这时候我们知道我们上一个路口选错了,所以我们要回到上一个路口重新选择其他路,这就是回溯的思想。

迷宫问题

说明

  1. 小球得到的路径,和程序员设置的找路策略有关即:找路的上下左右的顺序相关
  2. 再得到小球路径时,可以先使用(下右上左),再改成(上右下左),看看路径是不是有变化

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package com.nanzx.recursion;

public class MiGong {
public static void main(String[] args) {
// 利用二维数组模拟迷宫
int[][] map = new int[8][7];
// 使用1表示墙,将迷宫四周设置为墙
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;
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("");
}
}

// 使用递归回溯来给小球找路
// 说明
// 1. map 表示地图
// 2. i,j 表示从地图的哪个位置开始出发 (1,1)
// 3. 如果小球能到 map[6][5] 位置,则说明通路找到.
// 4. 约定: 当map[i][j] 为 0 表示该点没有走过;为 1 表示墙 ; 2 表示走过,是通路 ; 3 表示该点已经走过,但是走不通
// 5. 在走迷宫时,需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通,再回溯
public static boolean setWay(int[][] map, int i, int j) {
if (map[6][5] == 2) { // 通路已经找到ok
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;
}
}
}

// 修改找路的策略,改成 上->右->下->左
public static boolean setWay2(int[][] map, int i, int j) {
if (map[6][5] == 2) { // 通路已经找到ok
return true;
} else {
if (map[i][j] == 0) { // 如果当前这个点还没有走过
// 按照策略 上->右->下->左
map[i][j] = 2; // 假定该点是可以走通.
if (setWay2(map, i - 1, j)) {// 向上走
return true;
} else if (setWay2(map, i, j + 1)) { // 向右走
return true;
} else if (setWay2(map, i + 1, j)) { // 向下
return true;
} else if (setWay2(map, i, j - 1)) { // 向左走
return true;
} else {
// 说明该点是走不通,是死路
map[i][j] = 3;
return false;
}
} else { // 如果map[i][j] != 0 , 可能是 1, 2, 3
return false;
}
}
}
}

运行结果

下右上左:

1 1 1 1 1 1 1
1 2 0 0 0 0 1
1 2 2 2 0 0 1
1 1 1 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 2 2 1
1 1 1 1 1 1 1

上右下左:

1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 0 0 0 0 2 1
1 1 1 0 0 2 1
1 0 0 0 0 2 1
1 0 0 0 0 2 1
1 0 0 0 0 2 1
1 1 1 1 1 1 1

八皇后问题

说明

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

思路分析

  1. 第一个皇后先放第一行第一列
  2. 第二个皇后放在第二行第一列、然后判断是否OK, 如果不OK,继续放在第二列、第三列、依次把所有列都放完,找到一个合适
  3. 继续第三个皇后,还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置,就算是找到了一个正确解
  4. 当得到一个正确解时,栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到.
  5. 然后回头继续第一个皇后放第二列,后面继续循环执行 1,2,3,4的步骤

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package com.nanzx.recursion;

public class Queen8 {
// 表示有多少个皇后
int max = 8;
// 保存皇后放置位置的结果,列的位置,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
int[] arr = new int[max];
static int count;
static int judgecount;

public static void main(String[] args) {
Queen8 queen8 = new Queen8();
queen8.check(0);
System.out.println("解法一共有" + count + "种");
System.out.println("判断冲突一共有" + judgecount + "次");
}

public void check(int n) {
if (n == max) {
print();
return;
}
for (int i = 0; i < max; i++) {
arr[n] = i;
if (judge(n)) {
check(1 + n);
}
}
}

// 检测摆放的第n个皇后是否和前面皇后冲突
public boolean judge(int n) {
judgecount++;
for (int i = 0; i < n; i++) {
// 当arr[i] == arr[n]时,表示两个皇后处于同一列;
// 当Math.abs(n-i) == Math.abs(arr[n]-arr[i])时,
// 表示两条直角边相等,斜率为1,等腰直角三角形,两个皇后处于对角线,
if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
return false;//表示冲突
}
}
return true;//不冲突
}

public void print() {
++count;
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

}

运行结果

….

….

解法一共有92种
判断冲突一共有15720次