递归

概念：

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

递归规则：

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

迷宫问题：

使用递归算法在迷宫中找到终点。（这里只是为了理解什么是回溯算法，无需纠结，算法的好坏）

public class migong {
    public static void main(String[] args) {
        // 创建迷宫地图  约定 1 = 墙 ，2 = 这条路可以走通 ，3 = 表示这点已经走过
        /**
         * 1    1   1   1   1   1   1
         * 1  起点   0    0   0   0   1
         * 1    0   0   0   0   0   1
         * 1    1   1   0   0   0   1
         * 1    0   0   0   0   0   1
         * 1    0   0   0   0   0   1
         * 1    0   0   0   0 终点   1
         * 1    1   1   1   1   1   1
         */
        int[][] map = new int[8][7];

        // 初始化地图
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        for (int i = 1; i < 7; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        map[3][1] = 1;
        map[3][2] = 1;
        
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j]+"\t");
            }
            System.out.println();
        }

        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]+"\t");
            }
            System.out.println();
        }
    }

    // 约定 1 = 墙 ，2 = 这条路可以走通 ，3 = 表示这点已经走过
    // 寻路策略： 下右上左
    /**
     *
     * @param map 地图
     * @param i 起始位置
     * @param j
     * @return boolean
     */
    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]  == 1 2 3  剩下来的情况1.墙2.已经走过3.走不通
                return false;
            }
        }
    }
}