我知道的算法的递归

大家好，我是郝. 本文与您分享算法的递归. 我很高兴与segmentfault共享它，以便与大家学习和交流. 第一次，请小心并一起学习.

简单来说，递归就是自称，每次您调用不同的变量时，递归都可以帮助程序员解决复杂的问题，同时使您的代码更简单

列出两个小案例以了解递归调用机制

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

//1.打印问题
public class RecursionTest {
    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);
    }
}

在我们的程序中如何调用递归？程序从主方法入口进入

当我们进入调用test的主要方法（4）时，打开一个独立的空间

执行test（4）方法时，将有一个变量n = 4，如果判断（4> 2），则将执行test（4-1）方法

此时执行test（3）方法时递归 2次调用，如果n = 3，则也执行if判断（3> 2），并执行test（3-1）方法

此时执行test（2）方法时，如果n = 2，则也执行if判断（2> 2），但是2> 2未成立，并且执行输出命令

这时，执行测试（2）之后控制台的输出为n =2. 执行测试（2）时，它将返回到测试（3）.. n = 3，测试（4）. .. n = 4

public class RecursionTest {
    public static void main(String[] args) {
        int res=factorial(3);
        System.out.println("结果="+res);
    }
    //阶乘问题
    public static int factorial(int n) {
        if(n==1){
            return 1;
        } else {
            return factorial(n - 1) * n;
        }
    }
}

根据的理解，首先是阶乘（3-1）* 3，阶乘（2-1）* 2，阶乘（1）直接返回1，所以输出结果为1 * 2 * 3 = 6 <

1. 程序执行某个方法时，将打开一个独立的空间（堆栈）

2. 每个空间中的数据（局部变量）都是独立的

1. 各种数学问题:

例如: 8个皇后问题，河内塔，阶乘问题，迷宫问题，球篮问题等.

2. 递归还用于各种算法

例如，快速排序，合并排序，二进制搜索，分治算法等.

3. 堆栈要解决的问题->第一个返回代码更加简洁

1）执行方法时，将创建一个新的受保护的独立空间（堆栈空间）

2）该方法的局部变量是独立的，不会互相影响，例如上面的n变量示例

3）如果在方法中使用了引用变量，则将共享引用类型的数据，即，当迷宫问题通过时该方法是一个数组，而该数组是引用类型，则相同的数据将被称为: 数组

4）递归必须接近退出递归的条件，否则它是无限递归，并且死乌龟会引发异常: StackOverflowError

5）当一个方法完成执行或遇到返回时，它将返回，并且遵循它的任何人都将把结果返回给谁，并且当该方法完成执行或返回时，该方法也将完成执行.

1. 创建一个二维数组来模拟迷宫

2. 用1表示墙，顶部和底部均为1，即列在变化，行在变化，因此范围是0-6在变化

3. 用1代表墙，左边和右边都是1，即行在变化，列在变化，所以范围0-7在变化

4. 根据图中所示的第一行和第四行的第二列，使用1表示挡板，即球无法到达挡板的位置.

5. 约定: 0表示不行走，1表示围墙，2表示可以通过道路，3表示已经行走但失败.

6. 如图所示，起点从（1,1）（第二行和第二列）开始，球位于（6,5）的位置

7. 如果球是（i，j），向左走是（i，j-1），向右走是（i，j + 1），向上走是（i-1，j），向下是（i + 1，j）

//先创建一个二维数组，模拟迷宫地图
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;
}
//设置挡板, 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();
}
运行结果：
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. map表示地图
//2. i,j 表示从地图的哪个位置开始出发(1,1)
//3. 如果小球能到map[6][5]位置，则说明通路找到. .
//4. 约定:当map[i][j] 为0表示该点没有走过当为1表示墙; 2表示通路可以走; 3表示该点已经走过，但是走不通
//5. 在走迷宫时，需要确定-个策略(方法)：下->右->上->左 ，如果该点走不通，再回溯
/**
 * @param map 表示地图
 * @param i 从哪个位置开始找
 * @param j 从哪个位置开始找
 * @return 如果找到通路,就返回true, 否则返回false
 */
public static boolean setWay(int[][] map, int i, int j) {
    //小球的位置是(6,5) 对应数组则是map[6][5]
    if(map[6][5] == 2) {
        //到map[6][5]位置,说明球已找到
        return true;
    } else {
        //判断到地图map[i][j]是0，则代表这个点还没有走过
        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, 1 - 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
            //当为1表示墙; 2表示通路可以走; 3表示该点已经走过
            return false;
        }
    }
}

步骤分析图:

.....

八皇后问题是一个古老且众所周知的问题，这是回溯算法的典型案例. 这个问题是由国际象棋棋手马克斯·伯特尔（Max Bethel）在1848年提出的: 在8X8的国际象棋棋盘上放置八个皇后，以防止他们互相攻击，也就是说，任何两个皇后不能在同一行，同一列或同一斜杠上，问一下有多少种摆法（92）.

1. 第一女王将第一行和第一列放在第一位

2. 将第二个皇后放在第二行的第一列中，然后判断它是否为0K. 如果还不行，请继续将其放在第二列，第三列...中，按顺序排列所有列并找到合适的列. 的位置

3. 继续到第三个皇后仍然是第一列，第二列...“直到第八个皇后被放置在没有冲突的位置之前，它才被认为找到了正确的解决方案. ”

4）当获得正确的解决方案时，堆栈将返回到先前的堆栈并开始回溯，即，第一个皇后将所有正确的解决方案放在第一列中，全部得到.

5）然后返回并继续将第一个皇后放在第二列中，然后继续循环执行第1、2和3步

根据此想法，将第一位皇后放在第一行第一列（小圆圈代表皇后）

第二个皇后放在第二行的第一列中，然后判断它是否为0K，显然条件是: 两个皇后都不能在同一行，同一列或同一斜杠中

然后第二任皇后向右移动一个位置，满足条件不是相互攻击

所以继续进行第三个皇后或第一列，显然情况是: 两个皇后都不能在同一行，同一列或相同的斜杠中……第一...皇后

这时，如果获得正确的解决方案，则将第一个皇后放在第二列，然后继续执行1,2,3的步骤，但是效率不高，因为将执行8x8超过10,000次. ，将会有优化的算法

理论上，应该创建一个二维数组来表示棋盘，但是实际上，可以使用一维数组通过以下算法解决问题: arr [8] = {0,4，7 ，5,2，6，1，3}

arr下标表示行数，即皇后数，arr [i] = val，val表示第i + 1个皇后，位于i + 1第1行的i + 1列

也就是说递归 2次调用，我们使用下标来指示哪些行是皇后区，如图所示，如果相应的值一致，它们将在同一列中表示: array [n] == array [i]

也就是说，我们使用下标指示行数是皇后数，然后第n个皇后与n-1个皇后之间的列差==第n个皇后与n-1行之间的差，然后是相同的斜线: Math.abs（ni）== Math.abs（数组[n]-数组[i]），例如，第二个皇后和第一个皇后的行差= 1，列差= 1 ，相等证明如图所示为斜杠

实际操作代码如下:

public class Queue8 {
    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义数组array,保存皇后放置位置的结果,比如arr = {0 , 4, 7, 5, 2, 6, 1, 3}
    int[] array = new int[max];
    
    //放置第n个皇后
    public void check(int n){
        //从0开始放置 若n=8 则代表最后一列的皇后了
        if( n == max ){
            printQueue();
            return;
        }
        //依次放入皇后
        for(int i=0; i<max; i++){
            //把当前皇后n，放入第一列位置
            array[n]=i;
            //放入第n个皇后检查是否冲突
            if(judge(n)){
                //若不冲突，则执行n+1个皇后
                check(n+1);
            }
            //若冲突 则继续执行arr[n] = i;即将第n个皇后 放置在本行的后移一个位置
        }
    }
    //查看当我们放置第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 printQueue(){
        for (int i = 0; i < array.length; i++) {
            System. out. print(array[i] +"");
        }
        System.out.println();
    }
}

根据想法，添加数据以对其进行测试

public static void main(String[] args) {
    //测试八皇后
    Queue8 queue8 = new Queue8();
    queue8.check(0);
}
运行结果如下：
04752613
05726314
06357142
06471352
13572064
14602753
14630752
15063724
15720364
16257403
16470352
17502463
20647135
24170635
24175360
24603175
24730615
25147063
25160374
25164073
25307461
25317460
25703641
25704613
25713064
26174035
26175304
27360514
30471625
30475261
31475026
31625704
31625740
31640752
31746025
31750246
35041726
35716024
35720641
36074152
36271405
36415027
36420571
37025164
37046152
37420615
40357162
40731625
40752613
41357206
41362750
41506372
41703625
42057136
42061753
42736051
46027531
46031752
46137025
46152037
46152073
46302751
47302516
47306152
50417263
51602473
51603742
52064713
52073164
52074136
52460317
52470316
52613704
52617403
52630714
53047162
53174602
53602417
53607142
57130642
60275314
61307425
61520374
62057413
62714053
63147025
63175024
64205713
71306425
71420635
72051463
73025164

共有92种思维解决方案. 发现递归判断是基于思维导图的思维. 您可以进入小型游戏网站进行练习:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-172598-1.html