递归入门

递归的应用场景

迷宫问题（回溯），上图说明：

• 红色的方块是围墙，是小球不能够走的
• 白色的方块是小球可以活动的范围
• 左上角是小球的起点，移动到右下角，就算走出了迷宫

那么在这个场景中，就用到了递归（Recursion）

递归的概念

简单说：递归就是方法自己调用自己，每次调用时 传入不同的变量

递归有助于编程者解决复杂的问题，同时可以让代码变简单。

递归的调用机制

使用两个小案例，来帮助理解递归的调用机制：

• 打印问题
• 阶乘问题

打印信息

public static void main(String[] args) {
    m1(4);
}
public static void m1(int n){
    if(n > 2){
        m1(n-1);//递归调用
    }
    System.out.println("n = " + n);
}

如上图所示：

• 当程序执行到一个方法时，就会开辟一个独立的空间（可以看成是栈）
• man 方法先执行，执行到 test(4)，就开辟可一个空间
• 由于有判定 n > 2 时，再次调用 test 方法，所以会不断开辟空间，直到不再调用 test 方法
• 到了最顶端的空间区域，不满足条件，就会开始打印信息
• 一个区域执行完代码后，会回到上一个空间，继续执行剩下的代码

那么直到所有代码运行完成，就如下图所示了

从最顶端开始返回执行剩余代码，也就是打印信息，直到退出程序。那么结果就是上图所示的控制台中的信息。

运行上面的程序，也会输出一样的结果

阶乘问题

public class RecursionTest1 {
    public static void main(String[] args) {
        System.out.println(m1(4));
    }
    public static int m1(int n){
        if(n == 1){
            return 1;
        }else{
            return m1(n-1) * n;
        }

    }
}

递归能解决什么样的问题

• 各种数学问题，如：汉诺塔、阶乘问题、迷宫问题、球和篮子的问题（google 编程大赛里面的题目）
• 各种算法中也会使用到递归，比如：快排、归并、二分查找、分治算法等
• 将用栈解决的问题，可以用递归代码实现，比较简洁

递归需要遵守的规则

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

2. 方法的局部变量是独立的，不会相互影响，比如 n 变量

   但是如果是引用类型变量（比如数组），就会共享该引用类型的数据

3. 递归 必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError

4. 当一个方法执行完毕，或则遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

递归-迷宫问题

迷宫问题（回溯），上图说明：

• 红色的方块是围墙，是小球不能够走的
• 白色的方块是小球可以活动的范围
• 左上角是小球的起点，移动到右下角，就算走出了迷宫

那么在这个场景中，就用到了递归（Recursion），下面使用代码来实现小球走出迷宫的路径，学习数据结构，没有必要写界面。

/**
 * 迷宫问题，使用递归和回溯解决
 */
public class Maze {
    public static void main(String[] args) {
        //创建地图
        int[][] map = new int[8][7];
        //约定，使用1表示墙，2表示通路,3表示死路，4表示没有走过的路
        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 < map.length; i++){
            for(int j = 0; j < map[i].length; j++){
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        //开始找路
        boolean flag = setWay(map,1,1);
        if(flag){
            System.out.println("找到路：");
            for(int i = 0; i < map.length; i++){
                for(int j = 0; j < map[i].length; j++){
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        }else{
            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] = 1 || 2 || 3
                //等于1表示墙，不用走，等于2表示走过了，不用走，等于3表示死路，不用走
                return false;
            }
        }
    }
}

思考:最短路径问题

上面实现的算法有一个问题，最短路径问题，经过上面的代码实现和测试之后，就会发现，怎么走，是根据我们的策略来走的，目前没有学习其他寻找最短路径的算法时，我们能做的也只有修改策略，比如出口在左下，那么我们就先往左下走。所以我们这里的最短路径求解也只是最简单粗暴的方式，把所有可能的策略都整理出来，每一个策略都走一遍，看哪一个策略路径最短，就是最短路径。

递归回溯-八皇后问题

八皇后问题，是一个古老而著名的问题，是 回溯算法 的典型案例。

该问题是国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

高斯认为有 76 种方案。1854年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，使用回溯算法，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以解决此问题

八皇后思路分析

找出八皇后有多少种摆法，其实就是暴力穷举，思路如下：

1. 第一个皇后先放第一行第一列
2. 第二个皇后放在第二行第一列，然后判断是否符合规则，如果不符合规则，则继续放在第 二 列，依次把所有列都放完，找到一个合适的列
3. 继续第 3 个皇后，直到 8 个皇后都放到了棋盘上，并且没有违反规则，就算一个解答
4. 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后放在第一列的所有正确解全部拿到
5. 然后回头继续第一个皇后放第二列，后面继续循环执行前面 4 步

理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}，这个是存储结果，数组下标表示第几行，对应的值则为在那一列上摆放着

代码实现

public class Queue8 {
    private int max = 8;//最多有几个皇后
    private int[] array = new int[max];//存放皇后的解法
    private static int count = 0;//记录有多少种解法
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.println(count);
    }
    //判断当前位置是否合法
    private boolean judge(int n){
        //依次和它前面的已经确定位置的皇后进行判断，当前要放置皇后的位置是否合法
        for(int i = 0; i < n; i++){
            //判断当前皇后所在的位置，是否与其前面的皇后在同一列，同一行，同一斜线
            if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])){
                return false;
            }
        }
        return true;
    }

    //
    private void check(int n){
        if(n == max){//当n=8时，第八个皇后已经放置OK
            print();
            count++;
            return;
        }else {//挨个位置找，是否是正确的位置，当这个位置不满足的时候，会出现回溯，或者找到一种解法之后，也会进行回溯，找出下一种解法
            for(int i = 0; i < max; i++){
                array[n] = i;//找寻每个皇后都是从0开始
                if(judge(n)){//满足条件即开始递归找下一个满足条件的皇后位置
                    check(n+1);//递归调用
                }
            }
        }
    }
    //打印解法
    private void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

来源：

https://www.cnblogs.com/wyzstudy/p/15397780.html