算法入门教程-递归回溯

前面一节我们通过一个案例来熟悉了数据结构栈的使用和以及栈的使用场景,我们在本节来了解下经典的算法递归回溯的学习,相信大家对递归并不是很陌生,可具体的原理和使用过程并不是很理解,可能在学java时file知识点时我们利用递归遍历我们的文件夹的内容,当然在使用递归时也要注意跳出递归的限制条件,这样也是为了避免出现栈溢出情况等,说了这么多我们直接入正题.

递归的概念

简单的来说:递归就是方法自己调用自己的过程,不同的是在每一次的调用时所传入的变量不同,可以帮助我们解决复杂的问题,接下来我们通过一个经典的递归案例来分析递归的调用过程

经典案例(打印问题)

• 代码实现:

 /**
 * 数据结构-递归(问题打印)
 */
public class RecursionCase {
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);
}

简单的代码,我们通过示意图来分析结果,假设我给定的n为4

递归调用机制1.png

结合图和代码我们来解释下:

• 首先我们的代码执行的main方法时,会创建一个main函数对应的栈就如图所示
• 接着会执行我们的test(4)方法,此刻也会创建一个n=4时的栈,结合代码来看,将4带入我们的if语句是成立的.
• 此时会创建一个test(3)的栈,将3代入if语句是成立的,此刻会创建一个test(2)的栈,将2代入if语句条件不成立,该方法最早打印出来的是2,当执行完毕时,该栈销毁,会回溯到上一个栈也就是n=3时的栈,相继打印出3,同样的道理相继打印出4

分析完之后我们来看看实际的打印结果如图:

微信截图_20200203174841.png

如我们分析的一样,看完了上述简单的案例后我们总结下递归调用的规则

递归调用规则

• 当调用一个方法时,就会创建一个独立的空间栈
• 方法之间的局部变量是独立的,相互之间不会受到影响
• 在递归时,必须向递归推出的条件逼近,避免死循环(栈溢出)
• 当方法执行完毕时,或者遇到return时,就会返回,递归遵守谁调用就将结果返回给谁.

上述是我们在使用递归时需要遵守的几个规则,接着我们通过一个案例来实际感受下递归回溯的过程

递归场景

• 需求:
• 迷宫问题

• 1.如图所示:

  
  迷宫图.png

简单的说明下此图:

• 红色的区域表示我们迷宫的挡板,我们的目的是选择路径将球送到图中箭头的位置处就算完成任务,来看代码实现:

代码实现

• 迷宫的创建

  /**
 * 数据结构-递归实现迷宫
 */
public class MiGong {

public static void main(String[] args) {

    //1.创建二维数组来模拟迷宫
    int map [][] = new int[8][7];
    //2.将map的第一行和最后一行置为1,以及第一列和最后一列置为1,表示墙
    for (int i = 0; i < 7 ; i++) {

        map[0][i] = 1;
        map[7][i] = 1;
    }
    //3.将第一列和最后一列置为1
    for (int i = 0; i < 7  ; i++) {
        map[i][0] = 1;
        map[i][6] = 1;
    }
    //4.将3行1列和3行第2列设置为挡板
    map[3][1] = 1;
    map[3][2] = 1;

• 打印迷宫代码

//输出map
    for (int i = 0; i < 8 ; i++) {
        for (int j = 0; j < 7 ; j++) {
            System.out.print(map[i][j]+"");
        }
        System.out.println();
    }

• 测试结果如下图:

迷宫代码实现图.png

• 完成小球找路的代码代码实现:

 //5.使用递归回溯来给小球找路
//说明
// map表示地图
// i和j表示从地图的那个位置出发,这里规定从(1,1)出发
// 如果小球能到(6,5)位置,则说明找到了通路
// 约定:当map[i][j]为0时,表示没有该点没有走过,如果遇到的是1时,表示墙,2表示通路可以走,3表示改点已经走过,但是走不通
// 在走迷宫时,我们规定的策略为:下-->右->上->左,如果该点走不通在回溯


/**
 *
 * @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;
        }
    }

}

• 上述就是我们找路的代码,来测试一把,测试代码如下:

    //使用递归回溯给小球找路
    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();
    }

• 测试结果如图

  
  小球走过的路.png

总结

• 上述的小球找路的代码中我们已经明确规定了策略为下-->右->上->左,接下来我们改变策略为上->右->下->左再来看下代码实现过程

//修改找路的策略:上->右->下->左
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 (setWay(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;
        }
    }

}

• 测试代码

   //使用递归回溯给小球找路
    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();
    }

• 测试结果如下图所示

  
  修改策略后小球的路.png

关于递归回溯的简单学习就到这了...