递归

2023-03-31 21:48| 来源: 网络整理| 查看: 265

1.8 递归 1.8.1 了解递归

递归在程序语言中简单的理解是：方法自己调用自己

递归需要遵守的规则在这里插入图片描述递归调用机制

递归每次执行(调用)一次方法时，会在内存开辟一个栈空间

递归方法从哪里开始进入递归，返回的时候就从哪里返回跳出

可以看下图方便理解：在这里插入图片描述

递归简单案例了解打印阶乘

//用递归方法求阶乘 public class Factorial{ public static void main(String[] args){ int N = 5; for(int n = 0; n if(n // 初始化迷宫地图 i = i1; j = j1; endX = x; endY = y; map = new int[i][j]; // 设置墙壁 for(int j=0;j map[i][0] = 1; map[i][j1-1] = 1; } } public static void showMap(){ // 输出迷宫地图 for(int i1=0;i1 System.out.print(map[i1][j1]+" "); } System.out.println(); } } /** * * @param startX 开始探索格子的X坐标 * @param startY 开始探索格子的Y坐标 * @return 返回该点是否可通 * 说明: 1.当map[i][j]=0 表示小球这个点还没走到， * =1 表示墙 * =2 表示格子走过，但是我们不能再次走了 * =3 表示该点已经尝试走过，但是发现无法走通 * 2.走迷宫的策略下i+1 右j+1 上i-1 左j-1 * 3.从最开始格子开始，按照策略(下右上左)行走， * 遇到目标格子（终点），直接返回true * 遇到已知的无法通过格子（map[i][j] != 0）返回 * 遇到未知格子（map[i][j]=0）尝试探索将该格子的四个方向，只要该格子四个方向有一个可以通过返回true。否则将该格子设置为无法通过map[i][j]=3 * 4. 不同的行走策略都会导致最终寻找到的路径的不同，现在行走策略找到的路径不一定是最短路径 */ public static boolean findWay(int startX,int startY){ // 1. 判断终点是否走通过 if(map[endX][endY] == 2) return true; // 2.如果现所处格子未探索过(map[startX][startY]==0),开始按照策略行走 if(map[startX][startY] == 0){ // 暂且将当前格子设置为2 map[startX][startY] = 2; if(findWay(startX+1,startY)) // 向下 return true; else if (findWay(startX,startY+1)) // 向右 return true; else if(findWay(startX-1,startY)) // 向上 return true; else if(findWay(startX,startY-1)) // 向左 return true; else { // 如果四个方向都是死路，将现在格子标记为map[][] = 3 map[startX][startY] = 3; return false; } }else // 如果当前格子是已知格子map[][] = 1,2,3 直接返回false return false; } public static void main(String[] args) { initMap(7,8,5,4); // 手动添加障碍物 map[2][3] = 1; map[3][2] = 1; System.out.println("迷宫初始地图: "); showMap(); findWay(2,2); System.out.println("寻找后的迷宫地图: "); showMap(); } }

输出结果:

迷宫初始地图: 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 寻找后的迷宫地图: 1 1 1 1 1 1 1 1 1 0 2 2 2 0 0 1 1 0 2 1 2 0 0 1 1 0 1 0 2 0 0 1 1 0 0 0 2 0 0 1 1 0 0 0 2 0 0 1 1 1 1 1 1 1 1 1 1.8.3 递归解决八皇后问题

问题介绍：在这里插入图片描述思路分析：借用代码随想录的一张图解来简要说明递归的过程

定义一个max 定义有多少个皇后默认8定义一维数组array 保存皇后放置位置的结果写一个方法打印皇后摆放的位置写一个方法判断当前皇后n摆放位置是否会和前面摆放皇后冲突（同一列同一条斜线）同一列 array[i] = array[n]同一条斜线 abs(n-i) = abs(array[n]-array[i])因为在放置皇后的时候n是不断递增的，所以n根本不可能会相同，所以不可能会出现同一行的情况写一个方法放置第n个皇后（开始递归）摆放一个皇后n，无冲突，开始摆放下一个皇后n+1；有冲突，修改摆放列的位置array[n]，直到无冲突；如果无论怎么修改摆放列都会冲突，回溯到上一个皇后n-1，修改上一个皇后的摆放位置array[n-1]，重新开始下一个皇后n的摆放直到n==max （代表前0—max-1的皇后都摆放完毕，即全部皇后摆放完毕，开始输出摆放位置，结束本次递归）

实现代码与输出结果：

代码：

public class QueenN { // N皇后问题 private int max; // N 表示皇后个数 private int[] array; // 记录N皇后摆放位置 private int count; // 记录N皇后有几种解法 public boolean NoClash(int n){ // 判断摆放第n个皇后的时候是否会与之前皇后的摆放位置发生冲突 /** * array[n] == array[i] 判断是否同列 * Math.abs(n-i) == Math.abs(array[n]-array[i]) 判断是否同斜线(Math.abs解决正负斜线问题) */ for(int i=0;i this.max = max; array = new int[max]; } public void show(){ // 输出一个解法N皇后的摆放位置 count++; System.out.print("["+count+"]: "); for(int i=0;i // n为当前皇后标号 // n = max时,所有皇后都摆放完毕结束递归 if(n == max){ // 当n=max的时候,会return到上一层(上一行) show(); return; } // for(int i=0;i // 如果摆放冲突,会自动开始下一列的皇后摆放,直到所有列都尝试过或者摆放成功 putChess(n+1); // 如果不冲突,开始下一个皇后的摆放 } } // 若所有列摆放皇后都不合适，会自动return回溯到上一个皇后,调整摆放位置后再次开始下一层皇后的摆放 } // 测试使用八皇后有92种解法 public static void main(String[] args) { QueenN queen8 = new QueenN(); queen8.init(8); // 修改数字即可更改为N皇后问题 // queen8.show(); queen8.putChess(0); System.out.println("总计解法: "+queen8.count); } }

输出结果：

[1]: 0 4 7 5 2 6 1 3 [2]: 0 5 7 2 6 3 1 4 [3]: 0 6 3 5 7 1 4 2 [4]: 0 6 4 7 1 3 5 2 [5]: 1 3 5 7 2 0 6 4 [6]: 1 4 6 0 2 7 5 3 [7]: 1 4 6 3 0 7 5 2 [8]: 1 5 0 6 3 7 2 4 [9]: 1 5 7 2 0 3 6 4 [10]: 1 6 2 5 7 4 0 3 [11]: 1 6 4 7 0 3 5 2 [12]: 1 7 5 0 2 4 6 3 [13]: 2 0 6 4 7 1 3 5 [14]: 2 4 1 7 0 6 3 5 [15]: 2 4 1 7 5 3 6 0 [16]: 2 4 6 0 3 1 7 5 [17]: 2 4 7 3 0 6 1 5 [18]: 2 5 1 4 7 0 6 3 [19]: 2 5 1 6 0 3 7 4 [20]: 2 5 1 6 4 0 7 3 [21]: 2 5 3 0 7 4 6 1 [22]: 2 5 3 1 7 4 6 0 [23]: 2 5 7 0 3 6 4 1 [24]: 2 5 7 0 4 6 1 3 [25]: 2 5 7 1 3 0 6 4 [26]: 2 6 1 7 4 0 3 5 [27]: 2 6 1 7 5 3 0 4 [28]: 2 7 3 6 0 5 1 4 [29]: 3 0 4 7 1 6 2 5 [30]: 3 0 4 7 5 2 6 1 [31]: 3 1 4 7 5 0 2 6 [32]: 3 1 6 2 5 7 0 4 [33]: 3 1 6 2 5 7 4 0 [34]: 3 1 6 4 0 7 5 2 [35]: 3 1 7 4 6 0 2 5 [36]: 3 1 7 5 0 2 4 6 [37]: 3 5 0 4 1 7 2 6 [38]: 3 5 7 1 6 0 2 4 [39]: 3 5 7 2 0 6 4 1 [40]: 3 6 0 7 4 1 5 2 [41]: 3 6 2 7 1 4 0 5 [42]: 3 6 4 1 5 0 2 7 [43]: 3 6 4 2 0 5 7 1 [44]: 3 7 0 2 5 1 6 4 [45]: 3 7 0 4 6 1 5 2 [46]: 3 7 4 2 0 6 1 5 [47]: 4 0 3 5 7 1 6 2 [48]: 4 0 7 3 1 6 2 5 [49]: 4 0 7 5 2 6 1 3 [50]: 4 1 3 5 7 2 0 6 [51]: 4 1 3 6 2 7 5 0 [52]: 4 1 5 0 6 3 7 2 [53]: 4 1 7 0 3 6 2 5 [54]: 4 2 0 5 7 1 3 6 [55]: 4 2 0 6 1 7 5 3 [56]: 4 2 7 3 6 0 5 1 [57]: 4 6 0 2 7 5 3 1 [58]: 4 6 0 3 1 7 5 2 [59]: 4 6 1 3 7 0 2 5 [60]: 4 6 1 5 2 0 3 7 [61]: 4 6 1 5 2 0 7 3 [62]: 4 6 3 0 2 7 5 1 [63]: 4 7 3 0 2 5 1 6 [64]: 4 7 3 0 6 1 5 2 [65]: 5 0 4 1 7 2 6 3 [66]: 5 1 6 0 2 4 7 3 [67]: 5 1 6 0 3 7 4 2 [68]: 5 2 0 6 4 7 1 3 [69]: 5 2 0 7 3 1 6 4 [70]: 5 2 0 7 4 1 3 6 [71]: 5 2 4 6 0 3 1 7 [72]: 5 2 4 7 0 3 1 6 [73]: 5 2 6 1 3 7 0 4 [74]: 5 2 6 1 7 4 0 3 [75]: 5 2 6 3 0 7 1 4 [76]: 5 3 0 4 7 1 6 2 [77]: 5 3 1 7 4 6 0 2 [78]: 5 3 6 0 2 4 1 7 [79]: 5 3 6 0 7 1 4 2 [80]: 5 7 1 3 0 6 4 2 [81]: 6 0 2 7 5 3 1 4 [82]: 6 1 3 0 7 4 2 5 [83]: 6 1 5 2 0 3 7 4 [84]: 6 2 0 5 7 4 1 3 [85]: 6 2 7 1 4 0 5 3 [86]: 6 3 1 4 7 0 2 5 [87]: 6 3 1 7 5 0 2 4 [88]: 6 4 2 0 5 7 1 3 [89]: 7 1 3 0 6 4 2 5 [90]: 7 1 4 2 0 6 3 5 [91]: 7 2 0 5 1 4 6 3 [92]: 7 3 0 2 5 1 6 4 总计解法: 92

【本文地址】

公司简介

联系我们