数据结构之递归的应用场景迷宫问题

递归是什么

简单的说：递归就是方法自己调用自己，每次调用的时传入不同的变量。递归有助于开发解决复杂的问题，同时可以使代码变的简洁。

递归调用机制

直接上代码，用案例说明，我觉得在学校老师好像讲过很多遍了，但是过一端时间自己又写不出来。

打印问题

看一下输出结果吧

/**
 * 输出结果
 */
public class test1 {

    public static void main(String[] args) {
        fun(5);
    }

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

阶乘

/**
 * 阶乘问题
 */
public class factorialTest {

    public static void main(String[] args) {
        int factorial = factorial(5);
        System.out.println("factorial = " + factorial);
    }

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

}

输出结果

递归能解决的问题

• 各种数学问题如:8皇后问题﹐汉诺塔,阶乘问题，迷宫问题,球和篮子的问题(google编程大赛)
• 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
• 将用栈解决的问题。递归代码比较简洁。

递归需要遵守的重要规则

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

迷宫问题

迷宫问题是栈这一块很经典的问题。

迷宫大致可分为三种，简单迷宫、多通路迷宫：通路间不带环、多通路迷宫：通路间带环，其中带环多通路迷宫是最复杂的，解决它，要把栈与递归结合起来，下来我们来一个一个分析吧，先从简单迷宫开始。

给定一个迷宫Maze，并给定迷宫的路口和出口，用递归的方式搜索一条从入口到出口的可行路径（其中红色为围墙，蓝色为可行路），若存在这条路径，则打印出路径，若不存在路径，则输出信息，表示没有路径。

package recursion;

import java.awt.geom.AffineTransform;

/**
 * 递归求解迷宫
 */
public class Maze {

    public static void main(String[] args) {
        //创建二维数组，模拟迷宫。
        int[][] maze = new int[8][7];
        //使用1表示墙。上下为墙，设置为1.
        for (int i = 0; i < 7; i++) {
            maze[0][i] = 1;
            maze[7][i] = 1;
        }
        //左右为1，设置1
        for (int i = 0; i < 8; i++) {
            maze[i][0] = 1;
            maze[i][6] = 1;
        }

        //设置障碍物
        maze[3][1] = 1;
        maze[3][2] = 1;


        System.out.println("=============init maze ==============");
        //输出迷宫
        for (int[] data : maze) {
            for (int item : data){
                System.out.printf("%4d",item);
            }
            System.out.println();
        }
        System.out.println("=============init maze success========");

        //使用递归找出结果,[1][1]开始
        setWay(maze,1,1);
        System.out.println("=============success========");
        for (int[] data : maze) {
            for (int item : data){
                System.out.printf("%4d",item);
            }
            System.out.println();
        }
    }

    /**
     * 使用递归找出结果
     * 从[i][j] 出发
     * 若球儿能走到maze[6][5]的位置，则找打通路
     * 约定：
     *      [i][j]=0 该坐标点没走过，1表示墙，2为通路，3为已经走过，死路。
     *      确定一个策略，寻路方向 下，右，上，左的顺序。走不通则回溯
     * @param maze 二维数组地图
     * @param i  开始坐标
     * @param j
     * @return
     */
    public static boolean setWay(int[][] maze,int i,int j){
        if (maze[6][5] == 2){ //找到通路
            return true;
        }else {
            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 { //不等于0 ，可能是1,2,3,因为都不能走，所以返回false
                return false;
            }
        }
    }
}

输出结果