【数据结构】递归算法与应用

一、递归概述

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

二、递归的调用机制

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

三、递归解决的问题

1. 各种数学问题如：8 皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题（google 编程大赛）
2. 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等
3. 将用栈解决的问题 --> 递归代码比较简洁

四、递归的原则

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

五、迷宫问题

package work.rexhao.recursion;

import java.util.Scanner;

public class mazeDemo {
   

    static int size;
    static String[] map;
    static int ans = 0;
    static boolean[][] flag;

    public static void main(String[] args) {
   
        System.out.println("输入地图的大小:");
        Scanner sc = new Scanner(System.in);
        size = Integer.parseInt(sc.nextLine());
        System.out.println("输入地图:");
        map = new String[size];
        flag = new boolean[size][size];
        for (int i = 0; i < size; i++) {
   
            map[i] = sc.nextLine();
        }
        int x = 0, y = 0;
        for (int i = 0; i < size; i++) {
   
            for (int j = 0; j < size; j++) {
   
                if (map[i].charAt(j) == 'B') {
   
                    x = i;
                    y = j;
                }
            }
        }
        maze(x, y);
        System.out.println(ans);
        sc.close();
    }

    public static void maze(int x, int y) {
   
        if (check(x, y) && map[x].charAt(y) == 'E') {
   
            ans++;
            return;
        }
        flag[x][y] = true;
        if (check(x + 1, y)) {
   
            maze(x + 1, y);
        }
        if (check(x - 1, y)) {
   
            maze(x - 1, y);
        }
        if (check(x, y + 1)) {
   
            maze(x, y + 1);
        }
        if (check(x, y - 1)) {
   
            maze(x, y - 1);
        }
        flag[x][y] = false;
    }

    public static boolean check(int x, int y) {
   
        if (x >= size || y >= size || x < 0 || y < 0) {
   
            return false;
        } else
            return (map[x].charAt(y) == '.' || map[x].charAt(y) == 'E') && !flag[x][y];
    }
}

六、回溯算法（八皇后问题）

1、八皇后问题介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯 • 贝瑟尔于1848 年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法(92)。

2、思路分析

1. 相同剪枝：如果在同一行/列，舍弃
2. 斜向剪枝：对于y=x方向，行+列为定值；对于y=-x方向，行-列为定值

3、代码实现

package work.rexhao.recursion;

public class queueEight {
   
    public static int[] chess = new int[8];
    public static int ans = 0;
    public static int[] x1; // 对角线1
    public static int[] x2; // 对角线2

    public static void main(String[] args) {
   
        queue(chess, 0);
        System.out.println(ans);
    }

    public static void queue(int[] chess, int times) {
   
        /*
         * 退出条件
         */
        if (times == 8) {
   
            /*
             * 重复
             */
            for (int i = 0; i < 8; i++) {
   
                for (int j = 0; j < 8; j++) {
   
                    if(i == j) continue;
                    if (chess[i] == chess[j]) {
   
                        return;
                    }
                }
            }
            /*
             * 对角线
             */
            x1 = new int[20];
            x2 = new int[20];
            for (int i = 0; i < 8; i++) {
   
                x1[chess[i] - i + 8]++;
                x2[i + chess[i]]++;
            }
            for (int i = 0; i < 20; i++) {
   
                if (x1[i] > 1 || x2[i] > 1) {
   
                    return;
                }
            }
            for(int i: chess) {
   
                System.out.print(i + " ");
            }
            System.out.println();
            ans++;
            return;
        }

        /*
         * 递归
         */
        for (int i = 1; i < 9; i++) {
   
            chess[times] = i;
            queue(chess, times + 1);
        }

    }
}