一、介绍
1、介绍
递归:递归就是方法自己调用自己,每次调用时传入不同的变量。递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。
迭代和递归区别:迭代使用的是循环结构,递归使用的选择结构。使用递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。其时间复杂度就是递归的次数。
但大量的递归调用会建立函数的副本,会消耗大量的时间和内存,而迭代则不需要此种付出。
递归函数分为调用和回退阶段,递归的回退顺序是它调用顺序的逆序。
分治:当一个问题规模较大且不易求解的时候,就可以考虑将问题分成几个小的模块,逐一解决。
2、案例
- 兔子繁殖的问题。(斐波那契数列)。
- 计算 n! 。
- 任意长度的字符串反向输出。
- 折半查找算法的递归实现。
- 汉诺塔问题
- 八皇后问题
二、迷宫问题
问题:寻找一条从起始点到达终点的有效路径。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5SMlJjY3QmM4EDNzEjN0QGOlZDNjlDO5MmYmdTM3IDZk9CX5AzLclDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLzM3Lc9CX6MHc0RHaiojIsJye.png)
代码示例:迷宫
1 public class MiGong {
2
3 /**
4 * 0:该点没有走过, 1:表示墙, 2:可以走, 3:该点已经走过,但是走不通\
5 * 策略: 下->右->上->左, 如果该点走不通,再回溯
6 */
7 private int[][] map;
8 private int desX;
9 private int desY;
10
11 /**
12 * 构建 row*col的迷宫
13 *
14 * @param row 行
15 * @param col 列
16 */
17 public MiGong(int row, int col) {
18 if (row <= 0 || col <= 0) {
19 return;
20 }
21
22 map = new int[row][col];
23
24 // 默认 上下左右 全部为墙
25 for (int i = 0; i < col; i++) {
26 map[0][i] = 1;
27 map[row - 1][i] = 1;
28 }
29
30 for (int i = 0; i < row; i++) {
31 map[i][0] = 1;
32 map[i][col - 1] = 1;
33 }
34
35 }
36
37 /**
38 * 在迷宫内部添加挡板
39 *
40 * @param i 横坐标
41 * @param j 纵坐标
42 */
43 public void addBaffle(int i, int j) {
44 if (map == null) {
45 return;
46 }
47
48 // 外面一周都是墙
49 if (i > 0 && i < map.length - 1 && j > 0 && j < map[0].length - 1) {
50 map[i][j] = 1;
51 }
52 }
53
54 /**
55 * 设置迷宫的终点位置
56 *
57 * @param desX 横坐标
58 * @param desY 纵坐标
59 */
60 public void setDes(int desX, int desY) {
61 this.desX = desX;
62 this.desY = desY;
63 }
64
65 public boolean setWay(int i, int j) {
66 // 通路已经找到
67 if (map[desX][desY] == 2) {
68 return true;
69 } else {
70 if (map[i][j] != 0) {
71 return false;
72 }
73
74 // map[i][j] == 0 按照策略 下->右->上->左 递归
75 // 假定该点是可以走通.
76 map[i][j] = 2;
77 if (setWay(i + 1, j)) {
78 return true;
79 } else if (setWay(i, j + 1)) {
80 return true;
81 } else if (setWay(i - 1, j)) {
82 return true;
83 } else if (setWay(i, j - 1)) {
84 return true;
85 } else {
86 // 说明该点是走不通,是死路
87 map[i][j] = 3;
88 return false;
89 }
90 }
91 }
92
93 // 显示地图
94 public void show() {
95 for (int i = 0; i < map.length; i++) {
96 for (int j = 0; j < map[0].length; j++) {
97 System.out.print(map[i][j] + " ");
98 }
99 System.out.println();
100 }
101 }
102 }
代码示例:测试类
1 // 测试类
2 public class Main {
3
4 public static void main(String[] args) {
5 MiGong miGong = new MiGong(8, 7);
6 miGong.addBaffle(3, 1);
7 miGong.addBaffle(3, 2);
8 miGong.setDes(6, 5); // 设置目的地
9
10 System.out.println("初始地图的情况");
11 miGong.show();
12 miGong.setWay(1, 1); // 设置起始位置
13
14 System.out.println("小球走过的路径,地图的情况");
15 miGong.show();
16 }
17 }
18
19 // 结果
20 初始地图的情况
21 1 1 1 1 1 1 1
22 1 0 0 0 0 0 1
23 1 0 0 0 0 0 1
24 1 1 1 0 0 0 1
25 1 0 0 0 0 0 1
26 1 0 0 0 0 0 1
27 1 0 0 0 0 0 1
28 1 1 1 1 1 1 1
29 小球走过的路径,地图的情况
30 1 1 1 1 1 1 1
31 1 2 0 0 0 0 1
32 1 2 2 2 0 0 1
33 1 1 1 2 0 0 1
34 1 0 0 2 0 0 1
35 1 0 0 2 0 0 1
36 1 0 0 2 2 2 1
37 1 1 1 1 1 1 1
三、八皇后问题
问题:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
代码示例:八皇后
1 public class Queue8 {
2
3 private static final int MAX = 8;
4 // 保存皇后放置的位置,比如 arr = {0, 4, 7, 5, 2, 6, 1, 3}
5 private final int[] array = new int[MAX];
6
7 public static int count = 0;
8 public static int judgeCount = 0;
9
10 public void check() {
11 this.check(0);
12 }
13
14 // check 是每一次递归时,进入到check中都有 for(int i = 0; i < max; i++),因此会有回溯
15 private void check(int n) {
16 // n = 8, 表示8个皇后就已经放好
17 if (n == MAX) {
18 print();
19 return;
20 }
21
22 for (int i = 0; i < MAX; i++) {
23 array[n] = i;
24
25 // 判断当放置第n个皇后到i列时,是否冲突
26 // 不冲突
27 if (!judge(n)) {
28 // 接着放n+1个皇后,即开始递归
29 check(n + 1);
30 }
31 }
32 }
33
34 private boolean judge(int n) {
35 judgeCount++;
36 for (int i = 0; i < n; i++) {
37 // 同一列 或 同一斜线
38 if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
39 return true;
40 }
41 }
42 return false;
43 }
44
45 private void print() {
46 count++;
47 for (int i = 0; i < array.length; i++) {
48 System.out.print(array[i] + " ");
49 }
50 System.out.println();
51 }
52
53 }
1 // 测试类
2 public class Main {
3
4 public static void main(String[] args) {
5 Queue8 queue8 = new Queue8();
6 queue8.check();
7
8 System.out.printf("一共有%d解法", Queue8.count);
9 System.out.printf("一共判断冲突的次数%d次", Queue8.judgeCount); // 1.5w
10 }
11 }
四、汉诺塔问题
1、问题
2、思想
如果 n = 1,A -> C
如果 n >= 2,总是看做是两个盘,①最下边的盘。②上面所有的盘。则,步骤:
(1)先把上面所有的盘 A->B
(2)把最下边的盘 A->C
(3)把 B 塔的所有盘 从 B->C
3、代码
代码示例:汉诺塔问题
1 // 汉诺塔
2 public class Hanoitower {
3
4 // 使用分治算法
5 public static void move(int num, char a, char b, char c) {
6 // 如果只有一个盘
7 if (num == 1) {
8 System.out.println("第1个盘从 " + a + "->" + c);
9 } else {
10 // n >= 2,总是看做是两个盘,①最下边的盘。②上面所有的盘。则,步骤:
11
12 // 1.先把上面所有的盘 A->B.移动过程会使用到 c
13 move(num - 1, a, c, b);
14 // 2.把最下边的盘 A->C
15 System.out.println("第" + num + "个盘从 " + a + "->" + c);
16 // 3.把 B 塔的所有盘 从 B->C.移动过程会使用到 a
17 move(num - 1, b, a, c);
18 }
19 }
20 }
1 // 测试类
2 public class Main {
3 public static void main(String[] args) {
4 Hanoitower.move(3, 'A', 'B', 'C');
5 }
6 }
7
8 // 结果
9 第1个盘从 A->C
10 第2个盘从 A->B
11 第1个盘从 C->B
12 第3个盘从 A->C
13 第1个盘从 B->A
14 第2个盘从 B->C
15 第1个盘从 A->C