XMD

无语

算法基础09：递归

发表于 更新于 分类于 ，
本文字数： 3.7k 阅读时长 ≈ 3 分钟

递归的应用场景

实际应用场景，迷宫问题（回溯），递归(Recursion)

递归的概念

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

递归的调用机制

我列举两个小案例，来帮助大家理解递归，部分学员己经学习过递归了，这里在给大家回顾一下递归调用机制

  1. 打印问题
  2. 阶乘问题

1
2
3
4
5
6
7
8
9
10
11
12
public class RecursionDemo {
    public static void main(String[] args) {
        test(5);
    }

    public static void test(int n){
        if (n > 2){
            test(n-1);
        }
        System.out.println(n);
    }
}

输出的结果为：2 3 4 5

递归可以解决什么样的问题

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

递归要遵守的规则

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

迷宫问题

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

/**
 * 迷宫问题
 *
 * @author：XMD
 * @date: 25.8.22
 */
public class MoGong {
    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;
        }

        boolean setWay = setWay(map, 1, 1);
        System.out.println(setWay);

        //输出
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }
    }

    /**
     *
     * 从[1][1] 开始找
     * 如果找到[4][3] 说明找到
     * 0表示没有吧走过的
     * 1表示墙，不可走
     * 2走过的路
     * 3该位置已经走过，走不通
     * 定义一个策略：下-右-上-左，走不通再回溯
     *
     * @param mapm 表示数据
     * @param i 从那个位置开始找
     * @param j
     * @return 如果找到出路返回truye，没有返回false
     */
    public static boolean setWay(int[][] mapm,int i,int j) {
        if (mapm[4][3] == 2) {
            return true;
        } else {
            if (mapm[i][j] == 0) {
                //还没有走过，按策略走
                //假定可以走通
                mapm[i][j] = 2;
                if (setWay(mapm, i + 1, j)) {//往下走
                    return true;
                } else if (setWay(mapm, i, j + 1)) {//往右走
                    return true;
                } else if (setWay(mapm, i - 1, j)) {//往上走
                    return true;
                } else if (setWay(mapm, i, j - 1)) {//往左走
                    return true;
                } else {
                    //说明该点走不通
                    mapm[i][j] = 3;
                    return false;
                }
            } else {
                //不为0，就有可能为11，2，3
                //1是墙不能走，2已经走过，不要再走，3是死路，不可走，只能返回false
                return false;
            }
        }

    }

}

八皇后问题

思路分析

  1. 第一个皇后先放第一行第一列
  2. 第二个皇后放在第二行第一列、然后判断是否0K,如果不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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package com.algorithm.recursion;

/**
 * 八皇后问题
 *
 * @author：XMD
 * @date: 28.8.22
 */
public class Queue8 {
    int max = 8;
    /**
     * 理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题,arr[8]=
     * {0,4,7,5,2,6,1,3}/对应arr下标表示第几行，即第几个皇后，ar[)=val,val表示第i+1个皇后，放在第i+1
     * 行的第val+1列
     */
    int[] array = new int[max];
    int count = 0;

    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.println("共有：" + queue8.count);


    }

    //查看当我们放置第个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突

    /**
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            //array[i]==array[n]表示判断第n个皇后是否和前面的n-1个皇后在同一列
            //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++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "  ");
        }
        System.out.println();
    }

    /**
     * 编写一个方法，放置第n个皇后
     *  特别注意：check是每一次递归时，进入到check中都有for(int i=O;i<max;i++),因此会有回崩
     * @param n
     */
    private void check(int n) {
        if (n == max) {
            //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个皇后，放置在本行得后移的一个位置
        }
    }
}

-------------本文结束感谢您的阅读-------------

相关文章