更多详情内容请访问:数据结构与算法系列文章导读

1、递归要素

  • 明确递归的终止条件
  • 提取重复的逻辑,缩小问题的规模不断递去
  • 给出递归终止时的处理办法

1653548321315

2、递归应用场景

  1. 问题的定义是按递归定义的(Fibonacci 函数,阶乘,…);
  2. 问题的解法是递归的(有些问题只能使用递归方法来解决,例如,汉诺塔问题,…);
  3. 数据结构是递归的(链表、树等的操作,包括树的遍历,树的深度,…)。

3、递归与栈的关系

常常听到 “递归的过程就是出入栈的过程”,这句话怎么理解?

1653550791930

从上面的分析的递归问题来看,递归对问题的处理顺序,是遵循了先入后出(先开始的问题最后结束)的规律,这天然地符合栈这种数据结构的特性

递归和栈之间有一种紧密的联系。事实上,大部分的编译器是使用栈来实现递归的。当调用一个方法的时候,编译器会把这个方法的所有参数及其返回地址(这个方法返回时控制达到的地方)都压入栈中,然后把控制转移给这个方法。

当这个方法返回时,这些值退栈。参数消失,并且控制权重新回到返回地址处。

事实上,我们可以把任意一个递归程序转换成一个使用栈的程序。本质上做的转换是本来由编译器来维护的栈,变为由开发人员来维护。

所以两者的关系是:"递归算法可以使用数据栈来进行非递归化,同时借助数据栈而实现的非递归算法,也可以被递归化。两者是可逆的

4、如何思考递归

在初学递归的时候, 看到一个递归实现, 我们总是难免陷入不停的验证之中,比如上面提及的阶乘,求解 Factorial(n) 时,我们总会情不自禁的发问,Factorial(n-1) 可以求出正确的答案么?接着我们就会再用 Factorial(n-2) 去验证……不停地往下验证直到 Factorial(0)

对递归这样的不适应,和平时习惯的思维方式有关。习惯的思维是:已知 Factorial(0),乘上 1 就等于 Factorial(1),再乘以 2 就等于 Factorial(2)……直到乘到 n。

而递归和我们的思维方式正好相反。

那我们怎么判断这个递归计算是否是正确的呢?Paul Graham 提到一种方法:

如果下面这两点是成立的,我们就知道这个递归对于所有的 n 都是正确的。

  1. 当 n=0,1 时,结果正确;
  2. 假设递归对于 n 是正确的,同时对于 n+1 也正确。

5、递归解决问题案例

1.1迷宫问题

迷宫问题

使用二维数组模拟出一个迷宫,“1”代表城墙,右下角的“0”是终点位置,给一个起点位置,如果在不穿过城墙的情况下可以到达终点。

1653377133841

小球得到的路径,与程序员设置的找路策略有关,即找路的上下左右的顺序。因此我们假定一个找路策略:

  1. 判断下面是否可以走?
  2. 下面不行,判断右边是否可以走?
  3. 右边不行,判断上面是否可以走?
  4. 上面不行,判断左面是否可以走?
  5. 如果都不能走,那么这个点就不能走到终点。

每次走的时候都要经历这五个步骤,似乎一直在重复,但是重复的似乎又有点不太一样,这时候就可以用递归的思想来解决

而想要求出最短路径的方法也很简单,只需要要把找路的规则穷举一遍,保存每一种找路规则走的路径长度,然后进行比较即可

public class Maze {

    public static void main(String[] args) {
        // 先创建一个二维数组,模拟迷宫
        int[][] map = new int[8][7];
        // 使用1 表示墙
        // 上下全部置为1
        for (int x = 0; x < 7; x++) {
            map[0][x] = 1;
            map[7][x] = 1;
        }
        // 左右全部置为1
        for (int x = 0; x < 8; x++) {
            map[x][0] = 1;
            map[x][6] = 1;
        }
        //设置挡板, 1 表示
        map[3][1] = 1;
        map[3][2] = 1;
        // 输出地图
        System.out.println("地图的情况");
        for (int x = 0; x < 8; x++) {
            for (int y = 0; y < 7; y++) {
                System.out.print(map[x][y] + "   ");
            }
            System.out.println();
        }

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

        //输出新的地图, 小球走过,并标识过的递归
        System.out.println("\n小球走过,并标识过的地图的情况");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + "   ");
            }
            System.out.println();
        }
    }

    /**
     * 使用递归回溯来给小球找路
     * 当 map[x][y] 为 0 表示该点没有走过;当为 1 表示墙;2 表示通路可以走;3 表示该点已经走过,但是走不通
     * 在走迷宫时,需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通,再回溯
     * @param map 表示地图
     * @param x 从哪个位置开始出发的横坐标
     * @param y 从哪个位置开始出发的纵坐标
     * @return 找到通路 map[6][5],返回true,否则返回false
     */
    public static boolean setWay(int[][]map, int x, int y) {
        if (map[6][5] == 2) { // 通路已经找到
            return true;
        } else {
            if (map[x][y] == 0) { // 如果当前这个点还没有走过
                map[x][y] = 2; // 假定该点是可以走通.
                if(setWay(map, x+1, y)) {//向下走
                    return true;
                } else if (setWay(map, x, y+1)) { //向右走
                    return true;
                } else if (setWay(map, x-1, y)) { //向上
                    return true;
                } else if (setWay(map, x, y-1)){ // 向左走
                    return true;
                } else {
                    //说明该点是走不通,是死路
                    map[x][y] = 3;
                    return false;
                }
            } else {
                // 如果map[i][j] != 0 , 可能是 1, 2, 3
                return false;
            }
        }
    }
}

1.2 八皇后问题

八皇后问题

八皇后问题:

八皇后问题是一个古老而著名的问题,是回溯算法和递归调用的典型案例。八皇后难题是要将八个皇后(Queen)放在棋盘上,任何两个皇后都不能互相攻击(即没有任意两个皇后是在同一行、同一列或者同一条对角线上),问一共有多少种摆法。

1653378310578

  1. 第一个皇后先放在第一行第一列
  2. 第二个皇后放在第二行第一列,然后判断能否在该位置放皇后,如果不可以,则继续放下一列,直至找到一个合适的位置
  3. 继续放置第三个皇后,还是第一列、第二列…直到第8个皇后也能放在一个不能相互攻击的位置,就找到了一个正确解
  4. 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯。即将第一个皇后放在第一列的所有解逐个得到
  5. 完成以上步骤之后,将第一个皇后放在第二列,后面循环执行1, 2, 3, 4 步骤

public class Queue8 {
    static int[] array = new int[8]; // 定义数组,保存皇后放置的位置,数组的下标表示的是行,元素的值表示的是该行的皇后摆放在哪一列
    static int count = 0;
    static int judgeCount = 0;

    public static void main(String[] args) {
        putQueen(0);
        System.out.printf("总共累积判断冲突 %d 次", judgeCount);
    }

    /**
     * 往第 row 行中放入皇后,row 最开始从 0 开始,即从上往下摆
     * @param row 第几行
     */
    public static void putQueen(int row) {
        // 如果 row = 8 了,说明皇后位置已经全部摆放完毕,直接返回
        if (row == 8) {
            printQueen();
            return;
        }
        for (int column = 0; column < 8; column++) {
            // 将皇后放入该位置前判断这个位置放置皇后后是否与其他位置冲突
            if (isAccessible(row, column)) {
                // 如果不冲突
                array[row] = column; // 放入皇后
                putQueen(row + 1); // 继续下一行
            }
        }
    }

    /**
     * 判断该位置能否摆放皇后
     * @param row 行数
     * @param column 列数
     * @return true 为可以摆放;false 为不可以摆放
     */
    public static boolean isAccessible(int row, int column) {
        judgeCount++; // 判断是否有冲突的
        int left = column - 1;  // 对角线左上 \
        int right = column + 1; // 对角线右上 /
        // 从当前行的上一行开始,向上遍历 (没有必要判断当前行的下面几行了,因为下面几行肯定没有放皇后)
        for (int i = row - 1; i >= 0; i--) {
            // 先判断上面行数的列是否有和该行列冲突的,false 为有冲突
            if (array[i] == column) {
                return false;
            }
            // 再判断上面行数的左对角线是否与该点有冲突,false 为有冲突
            if (array[i] == left) {
                return false;
            }
            // 最后判断上面行数的右对角线是否与该点有冲突,false 为有冲突
            if (array[i] == right) {
                return false;
            }
            // 如果都没有,则继续遍历该行上一行的上一行,以此类推,同时斜对角线的值会变动
            left--;
            right++;
        }
        // 如果全部都遍历完了,执行到此处,说明不冲突
        return true;
    }

    /**
     * 打印解法
     */
    public static void printQueen() {
        for (int row = 0; row < 8; row++) {
            for (int column = 0; column < 8; column++) {
                if (array[row] == column) {
                    System.out.print("Q ");
                }
                else {
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println("第" + (++count) + "种解法:" + Arrays.toString(array));
    }
}


END

本文作者:
文章标题:递归算法
本文地址:https://www.pendulumye.com/data-structure-and-algorithm/71.html
版权说明:若无注明,本文皆PendulumYe原创,转载请保留文章出处。
最后修改:2022 年 07 月 13 日
千山万水总是情,给个一毛行不行💋