递归概念和调用机制

递归的概念

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

递归的调用机制

image-20221007113351948

  1. 当程序执行到一个方法时，就会开辟一个独立的空间(栈)；
  2. 每个空间的数据(局部变量)是独立的；

代码演示

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    // 通过代码简单理解递归调用
    test(4);
}
public static void test(int n){
    if(n>2){
        test(n-1);
    }
    System.out.println("n="+n);
}

运行结果

1
2
3
4
5
n=2
n=3
n=4

Process finished with exit code 0

递归能解决的问题和规则

递归解决什么样的问题

  1. 数学问题：八皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题；
  2. 各种算法中也会使用递归，例如：快排，归并排序，二分查找，分治算法等；
  3. 将用栈解决的问题->用递归代码比较简洁；

递归需要遵守的重要规则

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

迷宫回溯问题思路分析

迷宫问题思路分析

image-20221008104450819

  1. 小球得到的路径，和程序员设置的找路策略有关，和找路的上下左右的顺序相关；
  2. 再得到小球路径时，可以先使用(下右上左)策略，再改为(上右下左)策略，看看路径是不是有变化；
  3. 测试回溯现象

迷宫回溯问题代码实现

下右上左测试

代码

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.jokerdig.recursion;

/**
 * @author Joker大雄
 * @data 2022/10/8 - 10:05
 **/
public class Maze {
    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;
        }
        // 设置挡板
        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);
        // 输出新的地图，小球走过并标识的地图
        // 输出地图
        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表示地图，i,j表示从地图那个位置出发;
        2. 如果小球能到map[6][5],则说明通路找到
        3. 当map[i][j]为0时，表示该点还没有走左，
           为1表示墙，
           为2表示路可以走，
           为3表示该点已经走过，但走不通；
        4. 在走迷宫时，策略：下->右->上->左 的顺序走，如果该点走不通再回溯；

     */
    /***
     * @param map 迷宫地图
     * @param i 从哪个位置开始
     * @param j 从哪个位置开始
     * @return 返回找路结果
     */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5] == 2){
            // 通过已经找到
            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;
            }
        }
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
=======地图的情况=======
1 1 1 1 1 1 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 1 1 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 1 1 1 1 1 1 
=======小球走过并标识的地图的情况=======
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 

Process finished with exit code 0

测试回溯

代码

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
package com.jokerdig.recursion;

/**
 * @author Joker大雄
 * @data 2022/10/8 - 10:05
 **/
public class Maze {
    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;
        }
        // 设置挡板
        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);
        // 输出新的地图，小球走过并标识的地图
        // 输出地图
        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();
        }
    }
    // 使用递归回溯来给小球找路
    /***
     * @param map 迷宫地图
     * @param i 从哪个位置开始
     * @param j 从哪个位置开始
     * @return 返回找路结果
     */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5] == 2){
            // 通过已经找到
            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;
            }
        }
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
=======地图的情况=======
1 1 1 1 1 1 1 
1 0 1 0 0 0 1 
1 0 1 0 0 0 1 
1 1 1 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 1 1 1 1 1 1 
=======小球走过并标识的地图的情况=======
1 1 1 1 1 1 1 
1 3 1 0 0 0 1 
1 3 1 0 0 0 1 
1 1 1 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 1 1 1 1 1 1 

Process finished with exit code 0

上右下左测试

代码

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package com.jokerdig.recursion;

/**
 * @author Joker大雄
 * @data 2022/10/8 - 10:05
 **/
public class Maze {
    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;
        }
        // 设置挡板
        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();
        }
        // 使用递归回溯，给小球找路
        setWayUpdate(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();
        }
    }
    // 使用递归回溯来给小球找路
    /***
     * @param map 迷宫地图
     * @param i 从哪个位置开始
     * @param j 从哪个位置开始
     * @return 返回找路结果
     */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5] == 2){
            // 通过已经找到
            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 setWayUpdate(int[][] map,int i,int j){
        if(map[6][5] == 2){
            // 通过已经找到
            return true;
        }else{
            if(map[i][j]==0){
                // 如果当前点还没有走过,按照策略走 上->右->下->左
                map[i][j] = 2;// 假定该点可以走通
                if(setWayUpdate(map,i-1,j)){
                    // 向上走
                    return true;
                }else if(setWayUpdate(map,i,j+1)){
                    // 向右走
                    return true;
                }else if(setWayUpdate(map,i+1,j)){
                    // 向下走
                    return true;
                }else if(setWayUpdate(map,i,j-1)){
                    // 向左走
                    return true;
                }else{
                    // 到这说明该点下右上左都走不通，说明该点为死路
                    map[i][j] = 3;
                    return false;
                }
            }else{
                // 如果map[i][j] != 0，可能是1，2，3
                return false;
            }
        }
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
=======地图的情况=======
1 1 1 1 1 1 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 1 1 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 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 

Process finished with exit code 0

八皇后问题思路分析

八皇后问题介绍

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

八皇后问题思路

image-20221009110659512

  1. 第一个皇后先放第一行第一列；
  2. 第二个皇后放在第二行第一列，然后判断是否满足要求，如果不满足，继续放在第二列、第三列，依次把所有列都放完，找到一个合适的；
  3. 继续第三个皇后，是第三行第一列、第二列…直到第八个皇后也放在一个不冲突的位置，算是找到一个正确的摆法；
  4. 当得到一个正确摆法，在栈回退到上一个栈时，就会开始回溯，将第一个皇后放到第一行第一列的所有正确摆法全部得到；
  5. 然后回头继续第一个皇后放第一行的第二列，之后继续循环执行1，2，3，4的步骤；

说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组解决问题；

arr[8] - {0,4,7,5,2,6,1,3}，arr下标代表第几行，即第几个皇后；arr[i] = val，val表示第i+1个皇后，放在第i+1行的第val+1列；

八皇后问题代码实现

代码

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
package com.jokerdig.recursion;

/**
 * @author Joker大雄
 * @data 2022/10/10 - 10:30
 **/
// 八皇后问题
public class EightEmpresses {
    // 定义max，存放皇后总数
    int max = 8;
    // 定义数组array，保存皇后放置结果
    int[] array = new int[max];
    // 统计摆放总数
    static int count = 0;
    public static void main(String[] args) {
        // 测试8皇后代码
        EightEmpresses empresses = new EightEmpresses();
        empresses.check(0);
        System.out.println("八皇后问题一共有"+count+"种正确摆法");
    }
    // 编写一个方法，放置第n个皇后
    // 特别注意：check的每一次递归，都有一个for循环，因此会有回溯
    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执行，因为有i++，所以放到本行的后一列
        }
    }
    // 当我们放置第n个皇后，就去检测该皇后是否和之前摆放的皇后冲突
    /**
     *
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n){
        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个皇后在同一斜线
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }
    // 编写一个方法，将皇后摆放位置输出
    private void print(){
        // 每打印一次，说明是一种摆放方法，count++统计
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+ " ");
        }
        System.out.println();
    }
}

运行结果

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
0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4 
0 6 3 5 7 1 4 2 
0 6 4 7 1 3 5 2 
1 3 5 7 2 0 6 4 
1 4 6 0 2 7 5 3 
1 4 6 3 0 7 5 2 
1 5 0 6 3 7 2 4 
1 5 7 2 0 3 6 4 
1 6 2 5 7 4 0 3 
1 6 4 7 0 3 5 2 
1 7 5 0 2 4 6 3 
2 0 6 4 7 1 3 5 
2 4 1 7 0 6 3 5 
2 4 1 7 5 3 6 0 
2 4 6 0 3 1 7 5 
2 4 7 3 0 6 1 5 
2 5 1 4 7 0 6 3 
2 5 1 6 0 3 7 4 
2 5 1 6 4 0 7 3 
2 5 3 0 7 4 6 1 
2 5 3 1 7 4 6 0 
2 5 7 0 3 6 4 1 
2 5 7 0 4 6 1 3 
2 5 7 1 3 0 6 4 
2 6 1 7 4 0 3 5 
2 6 1 7 5 3 0 4 
2 7 3 6 0 5 1 4 
3 0 4 7 1 6 2 5 
3 0 4 7 5 2 6 1 
3 1 4 7 5 0 2 6 
3 1 6 2 5 7 0 4 
3 1 6 2 5 7 4 0 
3 1 6 4 0 7 5 2 
3 1 7 4 6 0 2 5 
3 1 7 5 0 2 4 6 
3 5 0 4 1 7 2 6 
3 5 7 1 6 0 2 4 
3 5 7 2 0 6 4 1 
3 6 0 7 4 1 5 2 
3 6 2 7 1 4 0 5 
3 6 4 1 5 0 2 7 
3 6 4 2 0 5 7 1 
3 7 0 2 5 1 6 4 
3 7 0 4 6 1 5 2 
3 7 4 2 0 6 1 5 
4 0 3 5 7 1 6 2 
4 0 7 3 1 6 2 5 
4 0 7 5 2 6 1 3 
4 1 3 5 7 2 0 6 
4 1 3 6 2 7 5 0 
4 1 5 0 6 3 7 2 
4 1 7 0 3 6 2 5 
4 2 0 5 7 1 3 6 
4 2 0 6 1 7 5 3 
4 2 7 3 6 0 5 1 
4 6 0 2 7 5 3 1 
4 6 0 3 1 7 5 2 
4 6 1 3 7 0 2 5 
4 6 1 5 2 0 3 7 
4 6 1 5 2 0 7 3 
4 6 3 0 2 7 5 1 
4 7 3 0 2 5 1 6 
4 7 3 0 6 1 5 2 
5 0 4 1 7 2 6 3 
5 1 6 0 2 4 7 3 
5 1 6 0 3 7 4 2 
5 2 0 6 4 7 1 3 
5 2 0 7 3 1 6 4 
5 2 0 7 4 1 3 6 
5 2 4 6 0 3 1 7 
5 2 4 7 0 3 1 6 
5 2 6 1 3 7 0 4 
5 2 6 1 7 4 0 3 
5 2 6 3 0 7 1 4 
5 3 0 4 7 1 6 2 
5 3 1 7 4 6 0 2 
5 3 6 0 2 4 1 7 
5 3 6 0 7 1 4 2 
5 7 1 3 0 6 4 2 
6 0 2 7 5 3 1 4 
6 1 3 0 7 4 2 5 
6 1 5 2 0 3 7 4 
6 2 0 5 7 4 1 3 
6 2 7 1 4 0 5 3 
6 3 1 4 7 0 2 5 
6 3 1 7 5 0 2 4 
6 4 2 0 5 7 1 3 
7 1 3 0 6 4 2 5 
7 1 4 2 0 6 3 5 
7 2 0 5 1 4 6 3 
7 3 0 2 5 1 6 4 
八皇后问题一共有92种正确摆法

Process finished with exit code 0