【数据结构与算法】递归、回溯、八皇后 一文打尽！

递归

引言： 递归算法是计算机科学中一种强大而又神秘的概念。它的简洁性和优雅性使得它在许多领域都得到广泛应用，例如数学、计算机科学和算法设计。本文将带你一起探索递归算法的精髓，解开其无限奥秘。

第一部分：什么是递归算法？

递归算法是一种自引用的算法，它通过将大问题分解为更小的相似子问题来解决复杂的计算任务。递归算法的核心思想在于将一个问题分解为一个或多个基本情况和一个或多个规模较小但同样结构的子问题。这些子问题将继续被分解，直到达到基本情况，然后逐层返回结果，最终解决原始问题。

第二部分：递归算法的基本原理

在使用递归算法时，我们需要明确两个关键要素：基本情况和递归关系。

1. 基本情况：基本情况是指递归过程中的终止条件。当问题达到基本情况时，递归停止，直接返回结果。基本情况的定义必须确保问题规模足够小，可以直接求解。
2. 递归关系：递归关系定义了如何将原始问题分解为规模较小但同样结构的子问题。通过递归关系，我们能够将问题逐步分解，并将子问题的解合并为原始问题的解。

第三部分：递归算法的应用场景——一个小故事

从前有座山山里有座庙，庙里有个小和尚。这个小和尚喜欢讲故事，有一天他开始讲了一个故事：“从前有座山山里有座庙，庙里有个小和尚，小和尚再说一个故事 故事的内容是...”

这个故事似乎永远没有结束的样子。听众们开始思考，这个故事是如何结束的呢？

递归的思想在这个故事中展现得淋漓尽致。小和尚讲的故事不断重复，每次故事的结尾都是开始的部分，形成了一个无限循环的过程。这种无限循环的特性正是递归的本质。

在这个故事中，小和尚讲的故事本身就是一个子问题，而每个子问题又以同样的方式继续展开，不断地迭代下去。

第四部分：递归算法在开发中的应用和经典问题

递归算法在开发中有广泛的应用。它可以用来解决各种问题，包括但不限于以下情况：

• 树和图的遍历：递归算法可以应用于树和图的深度优先搜索（DFS）和广度优先搜索（BFS）等遍历算法。
• 排列和组合：递归算法可以生成所有可能的排列和组合，如全排列、子集生成等。
• 分治算法：递归算法可以将一个大问题分解为多个子问题，并将子问题的解合并为整体解，如归并排序、快速排序等。
• 动态规划：递归算法可以用于解决动态规划问题，通过将问题分解为子问题，并保存子问题的解，避免重复计算，提高效率。

在面试中，递归算法经常被用作考察候选人的问题解决能力和算法思维。以下是一些经典的使用递归的面试问题：

• 阶乘计算：使用递归算法计算给定数的阶乘。
• 斐波那契数列：使用递归算法生成斐波那契数列的第n项。
• 二叉树相关问题：如二叉树的遍历、判断是否为二叉搜索树等。
• 字符串处理：如字符串反转、判断回文串等。

第五部分：用Java实现递归 下面是一个简单的Java代码示例，用于计算给定数的阶乘：

public class RecursionExample {
    public static int factorial(int n) {
        // 基本情况：当n为0或1时，直接返回1
        if (n == 0 || n == 1) {
            return 1;
        }
        // 递归关系：将问题分解为规模较小的子问题
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        int number = 5;
        int result = factorial(number);
        System.out.println("Factorial of " + number + " is: " + result);
    }
}

这个比较简单 那我们就继续引入一个较为复杂一点的案例

迷宫问题

迷宫问题是一个经典的应用递归思想的例子。它通常描述为在一个二维的迷宫中，从起点到达终点的路径规划问题。现在我们来说明如何通过递归来分析和解决迷宫问题。

1. 问题分析：
   • 首先，我们需要明确问题的输入和输出。在迷宫问题中，输入是一个迷宫地图，包含起点、终点以及障碍物的位置信息。输出是一条从起点到终点的路径，或者判断是否存在可行路径。
   • 其次，我们要考虑如何表示迷宫和路径。通常我们可以使用二维数组或矩阵表示迷宫，其中不可通过的区域可以用特定的符号或数字表示。路径可以用一个列表或栈来保存经过的位置。
   • 最后，我们需要定义问题的规模和边界条件。规模是指迷宫的大小，边界条件是指起点和终点的位置是否在合法范围内。
2. 解决问题：
   • 首先，我们要确定递归函数的定义和结束条件。在迷宫问题中，可以定义一个递归函数来搜索路径，每次尝试从当前位置向上下左右四个方向移动，直到达到终点或无法继续移动为止。
   • 接下来，我们需要考虑递归函数的递归关系。在迷宫问题中，递归关系可以描述为：如果当前位置可通过且未被访问过，则将当前位置标记为已访问，并尝试向四个方向递归搜索路径。
   • 最后，我们要处理递归函数的返回值。如果找到一条路径，则返回该路径；如果无法找到路径，则返回空值或特定的标识。

我们先把这个迷宫用二维数组画出来：

// 先创建一个二维数组，模拟迷宫
		// 地图
		int[][] map = new int[8][7];
		// 使用1 表示墙
		// 上下全部置为1
		for (int i = 0; i < 7; i++) {
			map[0][i] = 1;
			map[7][i] = 1;
		}

		// 左右全部置为1
		for (int i = 0; i < 8; i++) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		//设置挡板, 1 表示
		map[3][1] = 1;
		map[3][2] = 1;

/**
	 * 
	 * @param map 表示地图
	 * @param i 从哪个位置开始找
	 * @param j 
	 * @return 如果找到通路，就返回true, 否则返回false
	 */
	public static boolean setWay(int[][] map, int i, int j) {
		if(map[6][5] == 2) { // 通路已经找到ok
			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] != 0 , 可能是 1， 2， 3
				return false;
			}
		}
	}

代码的逻辑如下：

1. 首先检查当前位置 (i, j) 是否为目标位置 (6, 5)，如果是，说明已经找到通路，返回 true。
2. 如果当前位置不是目标位置，那么再判断当前位置是否可走（map[i][j] == 0）。如果是可走的，继续执行下面的步骤；否则返回 false。
3. 将当前位置标记为已经走过（map[i][j] = 2）。
4. 依据下、右、上、左的顺序，依次尝试向四个方向移动。
   • 如果向下移动 (setWay(map, i+1, j)) 返回 true，说明找到了通路，直接返回 true。
   • 如果向右移动 (setWay(map, i, j+1)) 返回 true，说明找到了通路，直接返回 true。
   • 如果向上移动 (setWay(map, i-1, j)) 返回 true，说明找到了通路，直接返回 true。
   • 如果向左移动 (setWay(map, i, j-1)) 返回 true，说明找到了通路，直接返回 true。
5. 如果以上四个方向都没有找到通路，说明该点是走不通的，将该位置标记为死路（map[i][j] = 3），并返回 false。
6. 如果当前位置不可走（map[i][j] != 0），直接返回 false。

整个算法通过递归的方式，在每个位置上尝试四个方向的移动，直到找到通路或者所有路径都被尝试完毕。如果找到通路，返回 true，否则返回 false。在每次递归调用时，都会改变地图的状态，标记已经走过的路径，以及死路。

是否发现一个问题：

这个代码只按照了其中一种策略（即下 右 上 左的策略） 这样出来的路径就不一定是最短的 如果需要优化就要用到后面的贪心算法 到时候会专门出一期贪心算法的讲解。

但是这里我们要讲解的是这个递归的思路 可以非常简洁的解决了问题

那就再进一步 到了回溯 最经典的八皇后问题

回溯：

思想：

回溯是一种经典的算法思想，常用于解决在给定的搜索空间中找到所有可能解的问题。它的基本思想是通过尝试不同的选择，当发现当前选择并不是有效的解决方案时，回溯到上一步并尝试其他选择，直到找到所有的解或者确定不存在解。

方法：

1. 定义问题的解空间：确定问题的解可以表示为一棵树的结构，每个节点代表一个可能的解，通过在树上进行深度优先搜索来遍历所有可能的解。
2. 定义候选集：确定每个节点的子节点是什么。候选集表示在当前节点上可以进行选择的所有可能选项。
3. 编写递归函数：递归函数负责遍历解空间树。在每个节点上，递归函数检查当前节点是否是一个有效解决方案，如果是，则将其添加到结果集中。然后，递归地调用自身来继续探索下一个节点。
4. 定义结束条件：在递归函数中，定义结束条件来判断是否到达了解空间的叶子节点或满足特定条件的节点。当满足结束条件时，递归函数停止递归，回溯到上一步进行其他选择。
5. 回溯：在递归函数中，当发现当前选择不是有效解决方案时，需要回溯到上一步并尝试其他选择。回溯是通过撤销对当前节点的选择，恢复到上一步状态，并继续遍历其他可能的选择

八皇后：

八皇后问题是一个经典的组合问题，其目标是在一个8×8的棋盘上放置8个皇后，使得任意两个皇后都不能互相攻击，即不能在同一行、同一列或同一对角线上。

解决八皇后问题的思路如下：

1. 定义问题的解空间：在每一行放置一个皇后，每个皇后的位置可以表示为一个二维坐标 (row, col)，其中 row 表示行数，col 表示列数。因为每一行只能放置一个皇后，所以解空间可以看作是一个排列问题。
2. 定义候选集：候选集表示每个节点上可以进行选择的所有可能选项。对于每一行，皇后可以放置在该行的任意列上，所以候选集为 [0, 7]，表示列的范围。
3. 编写递归函数：递归函数负责遍历解空间树。在每个节点上，递归函数检查当前节点的选择是否满足不攻击的条件，如果是，则将其添加到结果集中。然后，递归地调用自身来继续探索下一行的选择。
4. 定义结束条件：在递归函数中，定义结束条件来判断是否已经放置了所有的皇后。当所有的皇后都被放置时，递归函数停止递归，回溯到上一行进行其他选择。
5. 回溯：在递归函数中，当发现当前选择不满足不攻击的条件时，需要回溯到上一列并尝试其他选择。回溯是通过撤销对当前节点的选择，恢复到上一步状态，并继续遍历其他可能的选择。

优化思路：

我们可以用一维数组来表示这个皇后棋盘 arr[8]的八个值就是 八个皇后的横坐标 （因为我们已经知道他们不会同行，即纵坐标默认不相同）

1. 定义问题的解空间：使用一个一维数组 arr，其中 arr[i] 表示第 i 行皇后的列位置。因为每一行只能放置一个皇后，所以解空间可以看作是一个排列问题。
2. 定义候选集：候选集表示每个节点上可以进行选择的所有可能选项。对于每一行，皇后可以放置在该行的任意列上，所以候选集为 [0, 7]，表示列的范围。
3. 编写递归函数：递归函数负责遍历解空间树。在每个节点上，递归函数检查当前节点的选择是否满足不攻击的条件，如果是，则将其添加到结果集中。然后，递归地调用自身来继续探索下一行的选择。
4. 定义结束条件：在递归函数中，定义结束条件来判断是否已经放置了所有的皇后。当所有的皇后都被放置时，递归函数停止递归，回溯到上一行进行其他选择。
5. 回溯：在递归函数中，当发现当前选择不满足不攻击的条件时，需要回溯到上一列并尝试其他选择。回溯是通过撤销对当前节点的选择，恢复到上一步状态，并继续遍历其他可能的选择。

具体步骤如下：

1. 初始化一个长度为 8 的一维数组 arr，将其所有元素初始化为 0
2. 从第一行开始逐行放置皇后，调用递归函数 backtrack(arr, 0)，其中第二个参数表示当前放置的行数。
3. 在递归函数 backtrack 中，首先判断是否已经放置了所有的皇后（即当前行数等于总行数），如果是，则将 arr 添加到结果集中。
4. 否则，遍历当前行的所有列，依次尝试放置皇后。对于每个位置，判断是否与已经放置的皇后冲突，如果不冲突，则将该位置记录到 arr 中，然后递归调用 backtrack(arr, row + 1) 进行下一行的放置。
5. 在回溯过程中，要记得撤销对当前节点的选择，即将 arr[row] 的值恢复为 -1，以便尝试其他选择。
6. 最终，返回结果集，即所有满足条件的皇后位置组合。

代码 实现：

public class Queue8 {
    static int MaxSize=8;
    static int[] arr=new int[MaxSize];
    static int count =0;
    public static void main(String[] args) {
        check(0);
        System.out.println("count:"+count);
    }

    /**
     *description<放置第n个皇后>

         * @param n 第n个皇后
         * @return void
         * @author SUZE
         * @time 2024/2/18-18:56
         */

    public static void check(int n){
        if (n==8){//每当n为8意味着已经放置了8个皇后了,因为其实0~7才是需要检验的
            printf();
            count++;
            return;
        }
        for (int i=0;i<MaxSize;i++){
            //先把第n个皇后 放在该行的第i列
            arr[n]=i;
            if (judge(arr,n)){
            check(n+1);//满足了则继续下一位
            }
        }

    }
/**
 *description<功能描述>
        [arr, i, n] 放置前n个皇后有无冲突
     * @return boolean
     * @author SUZE
     * @time 2024/2/18-18:57
     */

    public static boolean judge(int[] arr,int n) {
        for (int i=0;i<n;i++){
            // 同列皇后情况   两皇后处在斜线的情况 （即纵坐标之差等于横坐标之差 因为可能包含了四个象限所以用绝对值）
            if (arr[i]==arr[n]||Math.abs(arr[i]-arr[n])==Math.abs(i-n)){
                return false;
            }
        }
        return true;
    }

    public static void printf(){
        for (int i=0;i<MaxSize;i++){
            System.out.printf("%d ",arr[i]);
        }
        System.out.println();
    }

}

测试结果