递归

递归应用场景

递归的概念

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

递归调用规则

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

递归需要遵守的重要准则

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

递归-迷宫问题

• 代码实现

package com.datastructures.cn.recursion;

import java.util.Arrays;

public class Maze {
    public static void main(String[] args) {
        // 先创建一个二维数组
        // 模拟迷宫maze
        // 地图
        int[][] map = new int[8][7];
        // 使用 1 表示墙
        // 上下全部置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置挡板
        map[3][1] = 1;
        map[3][2] = 1;

        //地图的情况
        for (int[] ints : map) {
            System.out.println(Arrays.toString(ints));
        }

        System.out.println("====================================");


        // 使用递归回溯找路
        setWay(map, 1, 1);

        for (int[] ints : map) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 使用递归回溯来给小球找路
     * 如果小球能到map的（6，5），则说明找到通路
     * @param map 地图
     * @param x 坐标x
     * @param y 坐标y
     * @return 如果找到通路 返回true 否则返回false
     */
    public static boolean setWay(int[][] map, int x, int y) {
        //final int[][] go = new int[][]{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
        final int[][] go = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {-1, 0}};
        // 找到了
        if (map[6][5] == 2) {
            return true;
        }

        //当前这个点还没有走过
        if (map[x][y] == 0) {
            // 假定该店是可以走通的
            map[x][y] = 2;
            // 向四个方向走
            for (int i = 0; i < 4; i++) {
                int dx = x + go[i][0];
                int dy = y + go[i][1];
                if (setWay(map, dx, dy)) {
                    // 走通了 返回true
                    return true;
                }
            }
            // 走不通
            map[x][y] = 3;
        }

        return false;
    }
}