[数据结构与算法]详解Java递归(Recursion)通过递归解决迷宫回溯及八皇后问题

什么是递归

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

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

递归调用机制

下面给大家举两个小案例来帮助大家快速的理解递归！

一.打印问题

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

递归调用规则

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

控制台运行结果

二.阶乘问题

public static int factorial(int n){
	if(n == 1){
		return 1;
	} else {
		return factorial(n-1)*n;
	}
}

了解完上面的调用规则后，我们先往方法中传一个为2的参数大家想想会是什么结果？

如果他传入的不为1会进入else分支此时这个地方就会变为下面这种结果。

return factorial(n-1)*n; //factorial(2-1) * 2

减1后进入递归方法 n == 1 直接返回所以最终结果为2

我们如果吧参数改为3呢？

return factorial(n-1)*n; //factorial(3-1) * 3

再次递归后

return factorial(n-1)*n; //factorial(2-1) * 2

以此类推最终的结果为 1 * 2 * 3 = 6 我们运行一下看看

递归能解决什么问题？

• 各种数学问题如：8皇后问题，汉罗塔，阶乘问题，迷宫问题，球和篮子的问题(google编程大赛)

• 各种算法中也会使用到递归如：快排，归并排序，二分查找，分治算法等。

• 将用栈解决的问题改为递归代码会比较整洁。

递归需要遵守什么规则？

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

迷宫问题

需求说明

1. 小球得到的路径，和程序员设置的找路策略有关。即：找路的上下左右的顺序相关。
2. 再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化。
3. 测试回溯现象
4. 思考如何求出最短的路径？

为了简化需求我们用控制台的数字来模拟迷宫地图并完成相关操作！

1. 新建一个初始化地图方法

  //初始化地图方法
    public static int[][] initMap(){
        //先创建一个二维数组，模拟一个八行七列的迷宫地图
        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;

        return map;
    }

2. 输出查看地图情况

    public static void main(String[] args) {
        int[][] map = initMap();

        //输出地图
        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();
        }
    }

3. 编写下右上左找路方法

	/**
     * 使用递归回溯来给小球找路
     * @param map 表示地图
     * @param i j 从那个位置开始找
     * @return 如果找到通路，就返回true，否则返回false
     * 如果小球能到 map[6][5]位置，则说明通路找到了
     * 约定：当map[i][j] 为0表示该点没有走过当为1表示墙。如果为2表示通路可以走，3表示该路走过了但是没有走通
     * 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 如果该点走不通再回溯
     */
	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;
            }
        }
    }

4. 测试

    public static void main(String[] args) {
        int[][] map = initMap();

        //输出地图
        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);
				//setWay2(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();
        }
    }

5. 编写上右下左方法观察路线变化

  	//修改找路策略，改成 上->右->下->左
    public static boolean setWay2(int[][] map,int i,int j){
        if (map[6][5] == 2){ //通路已经找到
            return true;
        }else {
            if (map[i][j] == 0){ //如果当前这个点还没有走过
                //按照策略 上->右->上->左
                map[i][j] = 2; //假设该点可以走通
                if (setWay2(map,i-1,j)){ //向上走
                    return true;
                } else if (setWay2(map,i,j+1)){ //向右走
                    return true;
                } else if (setWay2(map,i+1,j)){ //向下走
                    return true;
                } else if (setWay2(map,i,j-1)){ //向左走
                    return true;
                } else {
                    //说明该点是走不通的，是死路
                    map[i][j] = 3;
                    return false;
                }
            }else { //如果map[i][j] !=0，可能是1 2 3
                return false;
            }
        }
    }

6. 重新测试

    public static void main(String[] args) {
        int[][] map = initMap();

        //输出地图
        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);
        setWay2(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();
        }
    }

7. 修改地图测试回溯功能

    public static int[][] initMap(){
        //先创建一个二维数组，模拟一个八行七列的迷宫地图
        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;

        return map;
    }

8. 运行并测试

八皇后问题

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

八皇后问题算法思路分析

1. 第一个皇后先放第一行第一列
2. 第二个皇后放在第二行第一列，然后判断是否OK(判断是否冲突)，如果不OK，继续放在第二列，第三列，依次吧所以列都放完，找到一个合适
3. 继续第三个皇后，还是第一列，第二列…直到第八个皇后也能放在一个不冲突的位置，算是找到了一个正确解
4. 当得到一个正确解时，在栈退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正缺解，全部得到。
5. 然后回头继续第一个皇后放第二列，后面继续循环执行1,2,3的步骤。

说明：理论上应该创建一个二维数组表示棋盘，但是实际上可以通过算法用一个一维数组即可解决问题。arr[8] = {0,4,7,5,2,6,1,3} //对应arr下标，表示第几行，即第几个皇后，arr[i] = val，val表示第i+1个皇后，放在第i+1行的第val+1列。

代码实现

package recursion;

/**
 * @author mengzhichao
 * @create 2022-05-19-11:14
 */
public class Queue8 {

    //定义一个max表示共有多少个皇后
    int max=8;
    //定义数组arry，保存皇后放置位置的结果，比如arr = {0,4,7,5,2,6,1,3}
    int[] array = new int[max];

    static int count = 0;

    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);

        System.out.println("一共有："+count+"种解法");
    }



    //编写一个方法，放置第n个皇后
    //特别注意：check是每一次递归时，进入到check中都有 for (int i =0; i < max;i++),因此会有回溯
    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; 即将第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-i个皇后在同一列
            //2.Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
            //n = 1 放置第2列1n = 1 array[1] = 1
            //Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
            //3.这里没有必要判断是否在同一行，因为n每次都在递增
            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();
    }
}

运行并测试

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系