递归（包含迷宫问题）

文章目录

• • 一、递归的概述
  • • 1.1 什么是递归
    • 1.2 递归要遵守的准则
    • 1.3 递归的运行机制
    • 1.4 递归的应用场景
  • 二、迷宫问题

一、递归的概述

1.1 什么是递归

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

简单来说：递归，就是在方法运行的过程中调用自己。

构成递归需具备的条件：

1. 子问题须与原始问题为同样的事，且更为简单；

2. 不能无限制地调用本身，必须有个出口，化简为非递归状况处理。

1.2 递归要遵守的准则

在使用递归的过程中，需要遵守下面几个重要准则：

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

1.3 递归的运行机制

我们可以用两个小案例来理解一下递归的运行机制。

1.3.1 案例一

需求：

使用递归来打印 n 次 “Hello World”。

分析：

要使用递归打印 n 次字符串。首先根据递归的准则，要明确以下两点：

1. 递归退出的条件；
2. 递归要逼近退出条件。

对于上面两点，递归函数的初始参数一定是 n，如果要想打印 n 次，也就是要执行 n 次递归函数。假设每次递归时传递的参数是 n-1，那么递归的退出条件则是 n <= 1，反之，函数递归调用的条件则是 n > 1。

代码实现：

public class No1_Recursion_BasicDemo {

    public static void main(String[] args) {
        // 递归打印
        printHello(3);
    }

    /**
     * @Description 递归打印 Hello world
     * @Param [n] 打印次数
     */
    public static void printHello(int n){
        if (n > 1){
            printHello(n-1);
        }
        System.out.println("Hello World!");
    }
}

运行结果：

分析：

从上面的运行结果可以看出来，递归函数的初始参数为 n 时，将递归打印 n 次指定的字符串，符合题目需求。

那么这个递归函数是如何运行的呢？

下面将使用一个动图来描述当主函数调用 printHello(3) 时这个递归函数的运行过程：

1.3.2 案例二

需求：

使用递归来求解 n 的阶乘。

代码实现：

public class No1_Recursion_BasicDemo {

    public static void main(String[] args) {
        // 计算 4 的阶乘
        int factorial = getFactorial(4);
        System.out.println(factorial);
    }

    /**
     * @Description 计算 n 的阶乘
     */
    public static int getFactorial(int n){
        if (n == 1){
            return 1;
        }else{
            return n * getFactorial(n-1);
        }
    }
}

运行结果：

分析：

当主函数调用了 getFactorial(4) 时，这个递归的运行过程可以这么理解：

getFactorial(4)
=> 4 * getFactorial(3)
=> 4 * (3 * getFactorial(2))
=> 4 * (3 * (2 * getFactorial(1)))
=> 4 * (3 * (2 * 1))
=> 4 * (3 * 2)
=> 4 * 6
=> 24

1.4 递归的应用场景

递归可以解决许多实际性问题，主要可以概括为以下几个方面：

1. 各种数学问题，如 8 皇后问题、汉诺塔、阶乘问题、迷宫问题、球和篮子问题等；
2. 各种算法中也会使用到递归，如快排、 归并排序、二分查找、分治算法等；
3. 欲使用栈解决的问题，使用递归来解决代码更加简洁。

二、迷宫问题

2.1 问题描述

如上图所示是一个简单的迷宫，小球每次只能移动一个格子，且只能往上、下、左、右这四个方向移动。要求使用递归找出小球可以从起点走到终点的一条有效路径。

2.2 思路分析

从上面的迷宫图可以看出来，小球从起点走到终点可以有很多条路径。那么如何用代码实现呢？

1. 创建一个二维数组 arr[8][7]来代替迷宫；
2. 约定数组的值代表迷宫格子的状态，如：
   • 值为 0 代表这个格子没有走过；
   • 值为 1 代表这个格子是墙；
   • 值为 2 代表这个格子可以走通；
   • 值为 3 代表这个格子已经走过，但是走不通。
3. 小球采取探测移动策略，即每次移动之前，先探测周围的格子是否可以走通，再决定移动；
4. 确定小球的探测移动顺序，如按照 “上、左、下、右” 顺序探测移动，还是 “上、下、左、右” 顺序，亦或是 “左、上、右、下” 顺序等等。每种探测顺序的到的路径一般是不相同的。
5. 如果 arr[6][5] == 2 ，说明小球走到了终点。那么在此时的数组中，值为 2 的索引组成的路径即为有效路径。

2.3 代码实现

迷宫问题的代码实现如下，采用了两种策略，分别是： “下、右、上、左” 探测移动策略、“上、右、下、左” 探测移动策略：

public class No2_Recursion_Maze {

    private static final int row = 8;
    private static final int col = 7;

    public static void main(String[] args) {
        // 创建一个 8 行 7 列的迷宫
        int[][] maze = new int[row][col];
        // 初始化迷宫
        setMaze(maze);
        showMaze(maze);
        System.out.println("=========【下右上左】递归走迷宫==========");
        setWay(maze, 1, 1);
        showMaze(maze);
        
        // 初始化迷宫
        maze = new int[row][col];
        setMaze(maze);
        System.out.println("=========【上右下左】递归走迷宫==========");
        setWay2(maze, 1, 1);
        showMaze(maze);
    }

    /**
     * @Description 小球从坐标 maze[1][1] 开始，采用 下、右、上、左 策略来走迷宫
     * @Param [maze, i, j] maze:迷宫      i：当前所处行     j：当前所处列
     * @return boolean
     */
    public static boolean setWay(int[][] maze, int i, int j){
        // 1. 递归结束条件：当迷宫出口被置为 2 时，也即说明小球走到了这个格子
        if (maze[6][5] == 2){
            return true;
        }else{
            // 2. 如果不满足递归结束条件，继续递归
            if (maze[i][j] == 0){   // 如果没走过这个格子
                maze[i][j] = 2;     // 假设这个格子之后能走通
                if (setWay(maze, i+1, j)){  // 先向下走
                    return true;
                }else if (setWay(maze, i, j+1)){    // 如果向下走不通，就向右走
                    return true;
                }else if (setWay(maze, i-1, j)){    // 如果向右走不通，就向上走
                    return true;
                }else if (setWay(maze, i, j-1)){    // 如果向上走不通，就向左走
                    return true;
                }else{  // 如果上下左右都走不通，就说明这个格子是死路
                    maze[i][j] = 3;
                    return false;
                }
            }else{  // 如果这个格子是 1/2/3，由于这里没有回溯算法，就说明走不出去了
                return false;
            }
        }
    }

    /**
     * @Description 小球从 maze[1][1] 开始，采用上、右、下、左策略走迷宫
     * @Param [maze, i, j]
     * @return boolean
     */
    public static boolean setWay2(int[][] maze, int i, int j){
        // 1. 递归结束条件：当迷宫出口被置为 2 时，也即说明小球走到了这个格子
        if (maze[6][5] == 2){
            return true;
        }else {
            // 2. 如果不满足递归结束条件，继续递归
            if (maze[i][j] == 0) {   // 如果没走过这个格子
                maze[i][j] = 2;     // 假设这个格子之后能走通
                if (setWay2(maze, i-1, j)) {  // 先向上走
                    return true;
                } else if (setWay2(maze, i, j+1)) {    // 如果向上走不通，就向右走
                    return true;
                } else if (setWay2(maze, i+1, j)) {    // 如果向右不通，就向下走
                    return true;
                } else if (setWay2(maze, i, j-1)) {    // 如果向下走不通，就向左走
                    return true;
                } else {  // 如果上下左右都走不通，就说明这个格子是死路
                    maze[i][j] = 3;
                    return false;
                }
            } else {  // 如果这个格子是 1/2/3，由于这里没有回溯算法，就说明走不出去了
                return false;
            }
        }
    }
    
    /**
     * @Description 初始化迷宫
     * @Param [maze]
     */
    public static void setMaze(int[][] maze){
        // 第一行和第八行都是 1
        for (int i=0; i<col; i++){
            maze[0][i] = 1;
            maze[7][i] = 1;
        }
        // 第一列和第七列也都是 1
        for (int i=0; i<row; i++){
            maze[i][0] = 1;
            maze[i][6] = 1;
        }
        // 第四行第二列和第四行第三列都是 1
        maze[3][1] = 1;
        maze[3][2] = 1;
    }

    /**
     * @Description 显示迷宫状态
     * @Param [maze]
     */
    public static void showMaze(int[][] maze){
        // 打印初始迷宫
        for (int i=0; i<row; i++){
            for (int j=0; j<col; j++){
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
    }
}

最终的运行结果如下：

图1 下右上左策略

图2 上右下左策略

可以看到，使用两种不同的策略，最终可以得到不同的路径图。

本文地址：https://blog.csdn.net/zhuxian1277/article/details/112236923