[数据结构与算法]数据结构与算法——递归

目录

一、递归

1.1 递归需要遵守的重要规则

1.2 迷宫回溯问题

1.3 八皇后问题

一、递归

1.1 递归需要遵守的重要规则

• 执行一个方法时，就创建一个新的受保护的独立栈空间。
• 方法的局部变量是独立的，不会相互影响。
• 递归必须向退出递归的条件逼近，否则会无限递归，出现StackOverflowError。
• 当一个方法执行完毕或遇到return，则返回。遵守谁调用则将结果返回给谁。

1.2 迷宫回溯问题

?定义一个迷宫，其中1表示墙面，求最短的迷宫线路（线路用2表示）。

代码：

public class Maze {
    //定义集合存储所有走法的线路
    List<List<Integer>> path = new ArrayList<>();

    public static void main(String[] args) {
        int maze[][] = {
                {0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1, 0},
                {0, 1, 0, 0, 0, 1, 0},
                {0, 1, 0, 1, 0, 0, 0},
                {0, 0, 0, 1, 0, 1, 1},
                {0, 1, 0, 0, 0, 0, 0}
        };

        //定义集合存储经过路径坐标，坐标的行列存储在相邻位置
        List<Integer> step = new ArrayList<>();

        Maze mazeObj = new Maze();
        mazeObj.findWay(maze, 0, 0, maze.length, maze[0].length, step);
        mazeObj.printMin(maze);
    }

    public void findWay(int[][] maze, int i, int j, int n, int m, List<Integer> step) {
        //处理越界、遇墙、已走过的线路
        if (i < 0 || i >= n || j < 0 || j >= m || maze[i][j] == 1 || maze[i][j] == 2) {
            return;
        }

        //判断是否到达终点
        if (i == n - 1 && j == m - 1) {
            //添加终点坐标
            step.add(i);
            step.add(j);
            //标记为已走过
            maze[i][j] = 2;
            //将线路存入res集合
            path.add(new ArrayList<>(step));
            //回溯
            maze[i][j] = 0;
            step.remove(step.size() - 1);
            step.remove(step.size() - 1);
        } else {
            //添加当前坐标
            step.add(i);
            step.add(j);
            //标记为已走过
            maze[i][j] = 2;
            //递归
            findWay(maze, i + 1, j, n, m, step);
            findWay(maze, i, j + 1, n, m, step);
            findWay(maze, i - 1, j, n, m, step);
            findWay(maze, i, j - 1, n, m, step);
            //回溯
            maze[i][j] = 0;
            step.remove(step.size() - 1);
            step.remove(step.size() - 1);
        }
    }

    //输出最短的迷宫线路
    private void printMin(int[][] maze){
        int size = Integer.MAX_VALUE;
        int index = 0;

        //从path中获取最短路径
        for (int i = 0; i < path.size(); i++) {
            if (path.get(i).size() < size) {
                size = path.get(i).size();
                index = i;
            }
        }

        //在maze数组中将最短路径的线路标记为2
        List<Integer> step = path.get(index);
        for (int i = 0; i < step.size(); i += 2) {
            maze[step.get(i)][step.get(i + 1)] = 2;
        }

        //输出迷宫线路
        System.out.println("迷宫线路:");
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                System.out.print(maze[i][j] + " ");
            }
            System.out.println();
        }
    }
}

结果：

1.3 八皇后问题

在8×8格的国际象棋棋盘山摆放八个皇后，使其不能互相攻击，即任意两个皇后不能处于同一行、同一列或同一斜线上，求可能的解法数。

代码：

class Queues8 {
    //定义皇后数量
    static int max = 8;
    //定义解法数
    static int count = 0;

    public static void main(String[] args) {
        Queues8 queues8 = new Queues8();
        //定义棋盘，空位用.表示，皇后用Q表示
        char[][] board = new char[max][max];
        //填充空位
        for (char[] c : board) {
            Arrays.fill(c, '.');
        }
        queues8.backtrack(board, 0);
        System.out.println("一共有" + count + "种解法。");
    }

    //回溯算法
    public void backtrack(char[][] board, int row) {
        //每行都放置了皇后，返回结果
        if (row == board.length) {
            count++;
            print(board);
            return;
        }

        int n = board[row].length;
        //调整皇后在该行的位置
        for (int col = 0; col < n; col++) {
            //判断是否可以放置皇后
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                //进入下一行放皇后
                backtrack(board, row + 1);
                //回溯
                board[row][col] = '.';
            }
        }
    }

    //判断是否可以在board[row][col]放置皇后
    public boolean isValid(char[][] board, int row, int col) {
        int n = board.length;
        //检查列是否有皇后冲突
        for (int i = 0; i < n; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        //检查右上方是否有皇后冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        //检查左上方是否有皇后冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    //输出皇后摆放位置
    public void print(char[][] board) {
        for (char[] chars : board) {
            System.out.print(new String(chars) + " ");
        }
        System.out.println();
    }
}

结果（部分）：

?

?