网站建设是网络工程师吗,ftp 转 wordpress,靖江网站定制,石青网站推广软件递归递归需要遵守的重要规则1) 执行一个方法时#xff0c;就创建一个新的受保护的独立空间(栈空间)2) 方法的局部变量是独立的#xff0c;不会相互影响, 比如 n 变量3) 如果方法中使用的是引用类型变量(比如数组)#xff0c;就会共享该引用类型的数据.4) 递归 必须向退出递归…递归递归需要遵守的重要规则1) 执行一个方法时就创建一个新的受保护的独立空间(栈空间)2) 方法的局部变量是独立的不会相互影响, 比如 n 变量3) 如果方法中使用的是引用类型变量(比如数组)就会共享该引用类型的数据.4) 递归 必须向退出递归的条件逼近否则就是无限递归,出现 StackOverflowError死龟了:)5) 当一个方法执行完毕或者遇到 return就会返回 遵守谁调用就将结果返回给谁同时当方法执行完毕或者返回时该方法也就执行完毕迷宫问题迷宫问题示意图使用递归回溯来给小球找路说明1. map 表示地图2. i,j 表示从地图的哪个位置开始出发 (1,1)3. 如果小球能到 map[6][5] 位置则说明通路找到.4. 约定 当 map[i][j] 为 0 表示该点没有走过 当为 1 表示墙 2 表示通路可以走 3 表示该点已经走过但是走不通5. 在走迷宫时需要确定一个策略(方法) 下-右-上-左 , 如果该点走不通再回溯6.地图标记图-------------------------------------------------------地图的情况1 1 1 1 1 1 11 0 0 0 0 0 11 0 0 0 0 0 11 1 1 0 0 0 11 0 0 0 0 0 11 0 0 0 0 0 11 0 0 0 0 0 11 1 1 1 1 1 1代码实现package com.pierce.algorithm;public class MiGong {public static void main(String[] args) {// 先创建一个二维数组模拟迷宫// 地图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;}//设置挡板, 1 表示map[3][1] 1;map[3][2] 1;// map[1][2] 1;// map[2][2] 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();}//使用递归回溯给小球找路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();}}//使用递归回溯来给小球找路//说明//1. map 表示地图//2. i,j 表示从地图的哪个位置开始出发 (1,1)//3. 如果小球能到 map[6][5] 位置则说明通路找到.//4. 约定 当 map[i][j] 为 0 表示该点没有走过 当为 1 表示墙 2 表示通路可以走 3 表示该点已经走过但是走不通//5. 在走迷宫时需要确定一个策略(方法) 下-右-上-左 , 如果该点走不通再回溯/*** param map 表示地图* param i 从哪个位置开始找* param j* return 如果找到通路就返回 true, 否则返回 false*/public static boolean setWay(int[][] map, int i, int j) {// 通路已经找到 okif (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 boolean setWay2(int[][] map, int i, int j) {if (map[6][5] 2) { // 通路已经找到 okreturn 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;}}}}运行结果小球走过并标识过的 地图的情况1 1 1 1 1 1 11 2 0 0 0 0 11 2 2 2 0 0 11 1 1 2 0 0 11 0 0 2 0 0 11 0 0 2 0 0 11 0 0 2 2 2 11 1 1 1 1 1 1
