5.递归

5.递归
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

目录

1.递归的概念
2.递归需要遵守的重要规则
3.递归的应用
4.迷宫问题
 4.1 问题简介
 4.2 解决方案
  4.2.1 求解一条可行路径
  4.2.2 求解最短路径
  4.2.3 补充
5.八皇后问题

1.递归的概念

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

例如下面的函数就是递归调用,传参4时的打印结果为2 3 4:

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

2.递归需要遵守的重要规则

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

3.递归的应用

1.各种数学问题如: 8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题等;
2.各种算法中也会使用到递归,比如快排,归并排序,二分查找,分治算法等;
3.需要用栈解决的问题转换为用递归解决,能使代码比较简洁;

4.迷宫问题

4.1 问题简介

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

迷宫可以以二维数组来存储表示。这里距离规定:0表示通路,1表示障碍。规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示,均从0开始,给定起点(1,1)和终点(5,3),迷宫地图表示如下:

int map[5][5]={
   
	{
   1,1,1,1,1,1,1},
    {
   1,0,0,0,0,0,1},
    {
   1,0,1,0,1,0,1},
    {
   1,0,1,1,0,0,1},
    {
   1,0,1,1,0,1,1},
    {
   1,0,0,0,0,0,1},
    {
   1,1,1,1,1,1,1}
};

那么上述的迷宫就有两条可行的路径,分别为:

5.递归
5.递归

可见,迷宫可行路径有可能是多条,且路径长度可能不一。

4.2 解决方案

迷宫问题的求解可以抽象为连通图的遍历,因此可以用深度优先搜索(DFS)加回溯的方法,利用栈的数据结构来实现。在上述递归的应用中提到递归可以用于优化需要用栈来解决的问题,因此下述将先用栈来实现,便于理解,再用递归来优化。

4.2.1 求解一条可行路径

(1)给定起点和终点,判断二者的合法性,如果不合法,返回;
(2)如果起点和终点合法,将起点入栈;
(3)取栈顶元素,求其邻接是否存在有未被访问的无障碍结点。如果有,记其为已访问,并入栈。如果没有则回溯上一结点,具体做法是将当前栈顶元素出栈。其中,求邻接无障碍结点的顺序可任意,示例采用顺时针:上、右、下、左的顺序访问,采用不同的访问顺序得到的结果可能不同。
(4)重复步骤(3),直到栈顶元素等于终点(找到第一条可行路径)或者栈空(没有找到可行路径)。

这里规定:将二维数组迷宫地图中访问了的地方标记为2,已经访问了且为死路的标记为3

package stack;

import java.util.Stack;

class Point{
   
    //行与列
    public int row;
    public int col;

    public Point(int row, int col){
   
        this.row = row;
        this.col = col;
    }

    public boolean equal(Point point){
   
        return point.row == this.row && point.col == this.col;
    }

    @Override
    public String toString() {
   
        return "Point(" + row + ", " + col + ")";
    }
};

public class Maze {
   
    /** * 初始化迷宫地图 */
    private static int[][] map = new int[][]{
   
            {
   1,1,1,1,1,1,1},
            {
   1,0,0,0,0,0,1},
            {
   1,0,1,0,1,0,1},
            {
   1,0,1,1,0,0,1},
            {
   1,0,1,1,0,1,1},
            {
   1,0,0,0,0,0,1},
            {
   1,1,1,1,1,1,1}
    };
    //起点
    private static Point startP = new Point(1,1);
    //终点
    private static Point endP = new Point(5,3);
    //存放路径
    private static Stack<Point> pointStack = new Stack<>();

    public static void main(String[] args) {
   
        System.out.println("初始迷宫地图:");
        showMap();
        //查找可行路径
        mazePath();
        System.out.println("查找一条出迷宫的可行路径后的迷宫地图:");
        showMap();
        System.out.println("路径查找结果:");
        //没有找到可行解
        if(pointStack.empty()==true) {
   
            System.out.println("没有找到出口!");
        }
        else {
   
            //逆向输出栈中节点即为路径
            Stack<Point> tempPointStack = new Stack<>();
            while(pointStack.empty()==false) {
   
                tempPointStack.push(pointStack.pop());
            }
            while (!tempPointStack.empty()) {
   
                Point point = tempPoint1Stack.pop();
            	System.out.printf("(%d,%d) ",point.row,point.col);
            }
        }

    }

    /** * 深度优先搜索(DFS)加回溯查找一条可行路径,顺序:上、右、下、左 */
    public static void mazePath(){
   
        //起点和终点必须为无障碍结点,否则错误
        if(map[startP.row][startP.col] == 1 || map[endP.row][endP.col] == 1) {
   
            throw new RuntimeException("起点或终点不能为障碍点!") ;
        }
        //将起点入栈
        pointStack.push(startP);
        map[startP.row][startP.col] = 2;
        //栈不空并且栈顶元素不为结束节点则查找路径
        while(!pointStack.empty() && !endP.equal(pointStack.peek())){
   
            Point point = pointStack.peek();
            if (map[point.row-1][point.col]==0) {
   //上节点满足条件
                //入栈并设置访问标志为2
                pointStack.add(new Point(point.row-1,point.col));
                map[point.row-1][point.col] = 2;
            }else if (map[point.row][point.col+1]==0) {
   //右节点满足条件
                //入栈并设置访问标志为2
                pointStack.add(new Point(point.row,point.col+1));
                map[point.row][point.col+1] = 2;
            }else if (map[point.row+1][point.col]==0) {
   //下节点满足条件
                //入栈并设置访问标志为2
                pointStack.add(new Point(point.row+1,point.col));
                map[point.row+1][point.col] = 2;
            }else if (map[point.row][point.col-1]==0) {
   //左节点满足条件
                //入栈并设置访问标志为2
                pointStack.add(new Point(point.row,point.col-1));
                map[point.row][point.col-1] = 2;
            }else {
   
                //回溯到上一个节点并访问标志为3
                pointStack.pop();
                map[point.row][point.col] = 3;
            }
        }
    }

    /** * 打印迷宫地图 */
    public static void showMap(){
   
        for (int i = 0; i < 7; i++) {
   
            for (int j = 0; j < 7; j++) {
   
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
}

运行结果:
在这里插入图片描述
将上述用栈实现的算法改为用递归实现:

package stack;

import java.util.Stack;

class Point{
   
    //行与列
    public int row;
    public int col;

    public Point(int row, int col){
   
        this.row = row;
        this.col = col;
    }

    public boolean equal(Point point){
   
        return point.row == this.row && point.col == this.col;
    }

    @Override
    public String toString() {
   
        return "(" + row + ", " + col + ")";
    }
}

public class RecursionMaze {
   
    /** * 初始化迷宫地图 */
    private static int[][] map = new int[][]{
   
            {
   1,1,1,1,1,1,1},
            {
   1,0,0,0,0,0,1},
            {
   1,0,1,0,1,0,1},
            {
   1,0,1,1,0,0,1},
            {
   1,0,1,1,0,1,1},
            {
   1,0,0,0,0,0,1},
            {
   1,1,1,1,1,1,1}
    };
    //起点
    private static Point startP = new Point(1,1);
    //终点
    private static Point endP = new Point(5,3);

    public static void main(String[] args) {
   
        System.out.println("初始迷宫地图:");
        showMap();
        //查找可行路径
        //起点和终点必须为无障碍结点,否则错误
        if(map[startP.row][startP.col] == 1 || map[endP.row][endP.col] == 1) {
   
            throw new RuntimeException("起点或终点不能为障碍点!") ;
        }
        mazePath(startP);
        System.out.println("查找一条出迷宫的可行路径后的迷宫地图:");
        showMap();
        System.out.println("路径查找结果:");
        for (int i = 0; i < 7; i++) {
   
            for (int j = 0; j < 7; j++) {
   
                if (map[i][j]==2){
   
                    System.out.printf("(%d,%d) ",i,j);
                }
            }
        }
    }

    /** * 深度优先搜索(DFS)加回溯查找一条可行路径,顺序:上、右、下、左 */
    public static boolean mazePath(Point point){
   
        if (endP.equal(point)){
   //找到终点
            map[point.row][point.col] = 2;
            return true;
        }else {
   
            if(map[point.row][point.col] == 0) {
    //如果当前这个点还没有走过
                map[point.row][point.col] = 2;
                if (mazePath(new Point(point.row-1,point.col))) {
    // 向上走
                    return true;
                } else if (mazePath(new Point(point.row,point.col+1))) {
    // 向右
                    return true;
                } else if (mazePath(new Point(point.row+1,point.col))){
    // 向下走
                    return true;
                } else if (mazePath(new Point(point.row,point.col-1))){
    // 向左走
                    return true;
                }else {
   //说明没有地方可以走了,该处是死路,标记为 3;
                    map[point.row][point.col] = 3;
                    return false;
                }
            }else {
   // 如果不为0 ,则可能是 1 2 3,墙体、走过的、死路都应该回溯
                return false;
            }
        }
    }

    /** * 打印迷宫地图 */
    public static void showMap(){
   
        for (int i = 0; i < 7; i++) {
   
            for (int j = 0; j < 7; j++) {
   
                System.out.print(" "+map[i][j]);
            }
            System.out.println();
        }
    }
}

通过比较上述用栈实现和用递归的实现容易看出,递归的代码结构明显更简洁,但更难理解。

另外,一般的,当搜索深度较小、问题递归方式比较明显时,用递归方法设计好,它可以使得程序结构更简捷易懂。当数据量较大时,由于系统堆栈容量的限制,递归容易产生溢出,用非递归方法设计比较好。

4.2.2 求解最短路径

上面的方法只在乎找到一条可行路径,而并不关心这条路径是不是最短的,有时在实际情况下我们需要查找的是最短路径。因此,根据上面的方法我们可以进行改进,求出迷宫的最短路径。具体做法如下:

(1)让已经访问过的结点可以再次被访问,具体做法是将map中标记改为当前结点到起点的距离,作为当前结点的权值。即从起点开始出发,向四个方向查找,每走一步,把走过的点的值+1(为了避免和权值冲突,将墙改为-1,起点的距离权值为1);
(2)寻找栈顶元素的下一个可访问的相邻结点,条件就是栈顶元素的权值加1必须小于下一个节点的权值或下一个节点未被访问(墙不能走,未被访问的结点权值为0);
(3)如果访问到终点,记录当前最短的路径。如果不是,则继续寻找下一个结点;
(4)重复步骤(2)和(3)直到栈空(迷宫中所有符合条件的结点均被访问)。

package stack;
import java.util.Stack;
import java.util.function.UnaryOperator;

class Point{
   
    //行与列
    public int row;
    public int col;

    public Point(int row, int col){
   
        this.row = row;
        this.col = col;
    }

    public boolean equal(Point point){
   
        return point.row == this.row && point.col == this.col;
    }

    @Override
    public String toString() {
   
        return "(" + row + ", " + col + ")";
    }
};

public class ShortestPathMaze {
   
    /** * 初始化迷宫地图 */
    private static int[][] map = new int[][]{
   
            {
   -1,-1,-1,-1,-1,-1,-1},
            {
   -1, 0, 0, 0, 0, 0,-1},
            {
   -1, 0,-1, 0,-1, 0,-1},
            {
   -1, 0,-1,-1, 0, 0,-1},
            {
   -1, 0,-1,-1, 0,-1,-1},
            {
   -1, 0, 0, 0, 0, 0,-1},
            {
   -1,-1,-1,-1,-1,-1,-1}
    };
    //起点
    private static Point startP = new Point(1,1);
    //终点
    private static Point endP = new Point(5,3);
    //存放访问路径
    private static Stack<Point> pointStack = new Stack<>();
    //存放最短路径
    private static Stack<Point> shortestPath = new Stack<>();

    public static void main(String[] args) {
   
        System.out.println("初始迷宫地图:");
        showMap();
        //查找可行路径
        mazePath();
        System.out.println("查找一条出迷宫的可行路径后的迷宫地图:");
        showMap();
        System.out.println("路径查找结果:");
        //逆序输出
        //逆向输出栈中节点即为路径
        Stack<Point> tempPoint1Stack = new Stack<>();
        while(shortestPath.empty()==false) {
   
            tempPoint1Stack.push(shortestPath.pop());
        }
        while (!tempPoint1Stack.empty()) {
   
            Point point = tempPoint1Stack.pop();
            System.out.printf("(%d,%d) ",point.row,point.col);
        }
    }

    /** * 深度优先搜索(DFS)加回溯查找一条可行路径,顺序:上、右、下、左 */
    public static void mazePath(){
   
        //起点和终点必须为无障碍结点,否则错误
        if(map[startP.row][startP.col] == -1 || map[endP.row][endP.col] == -1) {
   
            throw new RuntimeException("起点或终点不能为障碍点!") ;
        }
        //将起点入栈
        pointStack.push(startP);
        map[startP.row][startP.col] = 1;
        //记录当前找到终点路径的长度
        int pathLength = 0;
        //栈不空则查找路径
        while(!pointStack.empty()){
   
            Point point = pointStack.peek();
            Point nextPoint = null;
            if ((map[point.row-1][point.col]==0 || map[point.row-1][point.col]>map[point.row][point.col]+1) && map[point.row-1][point.col]!=-1) {
   
                //上节点满足条件
                nextPoint = new Point(point.row-1,point.col);
            }else if ((map[point.row][point.col+1]==0 || map[point.row][point.col+1]>map[point.row][point.col]+1) && map[point.row][point.col+1]!=-1) {
   
                //右节点满足条件
                nextPoint = new Point(point.row,point.col+1);
            }else if ((map[point.row+1][point.col]==0 || map[point.row+1][point.col]>map[point.row][point.col]+1) && map[point.row+1][point.col]!=-1) {
   
                //下节点满足条件
                nextPoint = new Point(point.row+1,point.col);
            }else if ((map[point.row][point.col-1]==0 || map[point.row][point.col-1]>map[point.row][point.col]+1) && map[point.row][point.col-1]!=-1) {
   
                //左节点满足条件
                nextPoint = new Point(point.row,point.col-1);
            }else {
   //没有找到符合条件的节点,回溯到上一节点
                pointStack.pop();
                continue;
            }
            pointStack.push(nextPoint);
            map[nextPoint.row][nextPoint.col] = map[point.row][point.col]+1;
            //找到了终点即找到了一条路径,记录该路径,回溯继续查找其他可行路径,
            //若当前为最短路径,则后续由于权值,都无法到达终点,都会回溯直到栈空;若不为最短路径,则会被找到的更短路径替换
            if (endP.equal(nextPoint)){
   
                shortestPath.clear();
                shortestPath.addAll(pointStack);
                //终点出栈,由于之前记录了终点到起点的距离,所以后续将回溯直到找到另一条路
                pointStack.pop();
            }
        }
    }

    /** * 打印迷宫地图 */
    public static void showMap(){
   
        for (int i = 0; i < 7; i++) {
   
            for (int j = 0; j < 7; j++) {
   
                System.out.print(map[i][j]+"\t");
            }
            System.out.println();
        }
    }
}

4.2.3 补充

另外还有一种方法,广度优先搜索(BFS),该方法利用队列,从起点开始向每一个可行方向同时前进,将节点入队,这样最先找到终点的那条路一定是最短路径。为了准确找到路径,可以用一个和迷宫地图一样大的节点二位数组,存储该节点的前驱节点,这样找到终点后便可以通过终点沿着最短路径回到起点,找到路径。

5.八皇后问题

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出:在 8×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法(92)。
在这里插入图片描述

八皇后问题算法思路分析:

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

说明:

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

代码实现:

package stack;

public class Queen {
   
    //表示皇后数量
    private int max = 0;
    //定义数组 array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
    private int[] array;
    //一共有多少种解法
    private int count = 0;

    public Queen(int max){
   
        this.max = max;
        array = new int[max];
    }

    public static void main(String[] args) {
   
        Queen queen8 = new Queen(8);
        //放置第一个皇后,后续递归放置
        queen8.putQueen(0);
        System.out.printf("一共有%d 解法", queen8.count);
    }

    /** * 放置第n个皇后,即放第几行,递归实现 * @param n */
    public void putQueen(int n){
   
        if (n == max){
    //放置完最后一个皇后即结束,回溯
            printArray();
            count++;//找到一种放置方法,记录
            return;
        }
        //查找该皇后可以放置的列
        for(int i = 0; i < max; i++) {
   
            //先把当前这个皇后 n , 放到该行的第 i 列
            array[n] = i;
            //判断当放置第 n 个皇后到 i 列时,是否冲突
            if(check(n)) {
    // 不冲突
                //接着放 n+1 个皇后,即开始递归
                putQueen(n+1);
            }
            //如果冲突,就继续执行 array[n] = i; 即将第 n 个皇后,后移一列
        }
    }

    /** * 判断当前第n个皇后的放置的列是否符合要求 * @param n * @return */
    public boolean check(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 printArray() {
   
        for (int i = 0; i < array.length; i++) {
   
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

}

运行结果:
在这里插入图片描述
为了测试查找到的92种解法是否是正确的,可以去八皇后的在线小游戏 随便选运行结果中的一种进行测试。
在这里插入图片描述

本文来源MrKorbin,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/25281

发表评论