详解Java递归(Recursion)通过递归解决迷宫回溯及八皇后问题

发布网友 发布时间：2024-09-26 02:35

我来回答

共1个回答

热心网友 时间：2024-09-27 23:46

什么是递归

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

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

递归调用机制

下面给大家举两个小案例来帮助大家快速的理解递归！

一.打印问题public static void test(int n){if(n > 2){test(n - 1);}System.out.println("n="+n);}

递归调用规则

当程序执行到一个方法时候，就会开辟一个独立的空间(栈)。

每个空间的数据(局部变量)，是独立的。

控制台运行结果

二.阶乘问题public static int factorial(int n){if(n == 1){return 1;} else {return factorial(n-1)*n;}}

了解完上面的调用规则后，我们先往方法中传一个为2的参数大家想想会是什么结果？

如果他传入的不为1会进入else分支此时这个地方就会变为下面这种结果。

return factorial(n-1)*n; //factorial(2-1) * 2

减1后进入递归方法 n == 1 直接返回所以最终结果为2

我们如果吧参数改为3呢？

return factorial(n-1)*n; //factorial(3-1) * 3

再次递归后

return factorial(n-1)*n; //factorial(2-1) * 2

以此类推最终的结果为 123 = 6 我们运行一下看看

递归能解决什么问题？

各种数学问题如：8皇后问题，汉罗塔，阶乘问题，迷宫问题，球和篮子的问题(google编程大赛)

各种算法中也会使用到递归如：快排，归并排序，二分查找，分治算法等。

将用栈解决的问题改为递归代码会比较整洁。

递归需要遵守什么规则？

执行一个方法时，就创建一个新的受保护的独立空间(栈空间)

方法的局部变量是独立的，不会相互影响，比如上面的n变量

如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据

递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError栈溢出，死归了

当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

迷宫问题

需求说明

小球得到的路径，和程序员设置的找路策略有关。即：找路的上下左右的顺序相关。

再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化。

测试回溯现象

思考如何求出最短的路径？

为了简化需求我们用控制台的数字来模拟迷宫地图并完成相关操作！

新建一个初始化地图方法

//初始化地图方法public static int[][] initMap(){//先创建一个二维数组，模拟一个八行七列的迷宫地图int[][] map = new int[8][7];//使用数字1表示墙上下全部置为1for (int i=0;i<7;i++){map[0][i] = 1;map[7][i] = 1;}//左右全部置为1for (int i=0;i<8;i++){map[i][0] = 1;map[i][6] = 1;}//设置挡板map[3][1] = 1;map[3][2] = 1;return map;}

输出查看地图情况

public static void main(String[] args) {int[][] map = initMap();//输出地图System.out.println("地图的情况");for (int i=0;i<8;i++){for (int j=0;j<7;j++){System.out.print(map[i][j] + "");}System.out.println();}}

编写下右上左找路方法

/** * 使用递归回溯来给小球找路 * @param map 表示地图 * @param i j 从那个位置开始找 * @return 如果找到通路，就返回true，否则返回false * 如果小球能到 map[6][5]位置，则说明通路找到了 * 约定：当map[i][j] 为0表示该点没有走过当为1表示墙。如果为2表示通路可以走，3表示该路走过了但是没有走通 * 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 如果该点走不通再回溯 */public static boolean setWay(int[][] map,int i,int j){if (map[6][5] == 2){ //通路已经找到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 3return false;}}}

测试

public static void main(String[] args) {int[][] map = initMap();//输出地图System.out.println("地图的情况");for (int i=0;i<8;i++){for (int j=0;j<7;j++){System.out.print(map[i][j] + "");}System.out.println();}//使用递归回溯给小球找路从第一行第一列开始setWay(map,1,1);//setWay2(map,1,1);//输出新的地图，小球走过，并标识过的递归System.out.println("小球走过，并标识过的地图的情况");for (int i=0;i<8;i++){for (int j=0;j<7;j++){System.out.print(map[i][j] + "");}System.out.println();}}

编写上右下左方法观察路线变化

//修改找路策略，改成 上->右->下->左public static boolean setWay2(int[][] map,int i,int j){if (map[6][5] == 2){ //通路已经找到return true;}else {if (map[i][j] == 0){ //如果当前这个点还没有走过//按照策略 上->右->上->左map[i][j] = 2; //假设该点可以走通if (setWay2(map,i-1,j)){ //向上走return true;} else if (setWay2(map,i,j+1)){ //向右走return true;} else if (setWay2(map,i+1,j)){ //向下走return true;} else if (setWay2(map,i,j-1)){ //向左走return true;} else {//说明该点是走不通的，是死路map[i][j] = 3;return false;}}else { //如果map[i][j] !=0，可能是1 2 3return false;}}}

重新测试

public static int factorial(int n){if(n == 1){return 1;} else {return factorial(n-1)*n;}}0

修改地图测试回溯功能

public static int factorial(int n){if(n == 1){return 1;} else {return factorial(n-1)*n;}}1

运行并测试

八皇后问题

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

八皇后问题算法思路分析

第一个皇后先放第一行第一列

第二个皇后放在第二行第一列，然后判断是否OK(判断是否冲突)，如果不OK，继续放在第二列，第三列，依次吧所以列都放完，找到一个合适

继续第三个皇后，还是第一列，第二列......直到第八个皇后也能放在一个不冲突的位置，算是找到了一个正确解

当得到一个正确解时，在栈退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正缺解，全部得到。

然后回头继续第一个皇后放第二列，后面继续循环执行1,2,3的步骤。

说明：理论上应该创建一个二维数组表示棋盘，但是实际上可以通过算法用一个一维数组即可解决问题。arr[8] = {0,4,7,5,2,6,1,3} //对应arr下标，表示第几行，即第几个皇后，arr[i] = val，val表示第i+1个皇后，放在第i+1行的第val+1列。

代码实现

public static int factorial(int n){if(n == 1){return 1;} else {return factorial(n-1)*n;}}2

运行并测试

原文：https://juejin.cn/post/7099443445625782286