学习来源–>传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）
推荐这位大佬的文章 ;掌握递归—>什么是递归，通过这篇文章，让你彻底搞懂递归
ml- 1.递归的简易案例
- 2.迷宫问题
- 3.八皇后问题
1.递归的简易案例
递归,在方法自身内调用自己,但是传递参数不同; 调用后一直到最后,然后再一步步地把获得的结果返回到调用的位置.
public class Demo {
public static void main(String[] args) {
getNum(5);
}
//简易递归案例;
public static void getNum(int n){
if(n > 2){
getNum(n - 1);
}
System.out.println("n-->"+ n);
}
}
得到结果
n-->2 n-->3 n-->4 n-->5
模拟过程图解
具体的调用过程;
- main() , getNum(5)
- 此时 n=5; getNum(5) 条件判断后–> getNum(4);
- 此时 n=4; getNum(4) 条件判断后–> getNum(3);
- 此时 n=3; getNum(3) 条件判断后–> getNum(2);
- 此时 n=2; getNum(2) 条件判断–> sout输出 n=2;
- 返回; sout 输出 n=3;
- 返回; sout 输出 n=4;
- 返回; sout 输出 n=5;
- 最终结果 2 ; 3; 4; 5;
但是,若给执行条件外加一层else{};那么执行的结果就只有一个
public class Demo {
public static void main(String[] args) {
getNum2(5);
}
//简易递归案例2;
public static void getNum2(int n){
if(n > 2){
getNum2(n - 1);
}
//若在其中加入else语句;
else {
System.out.println("n-->"+ n);
}
}
}
执行结果
n-->2
过程模拟图解;
当调用的结果返回时,发现符合 (n>2) 的条件,他也就不会再去走另一条路了
若加入else语句; 在返回时,由于不符合条件,不再执行sout输出
- main() , getNum(5)
- 此时 n=5; getNum(5) 条件判断后–> getNum(4);
- 此时 n=4; getNum(4) 条件判断后–> getNum(3);
- 此时 n=3; getNum(3) 条件判断后–> getNum(2);
- 此时 n=2; getNum(2) 条件判断–> sout输出 n=2;
- 返回;
- 返回;
- 返回;
- 最终结果 2 ;
阶乘的案例;
public class Demo {
public static void main(String[] args) {
//阶乘调用;
int i = factorial(5);
//System.out.println(i);
}
//阶乘递归;
public static int factorial(int num){
return num == 1 ? 1 :num*factorial(num-1);
}
}
图解就不做图了;
具体过程为–>
2.迷宫问题
- main() ; factorial(5);
- num =5; factorial(5) --> 5 * factorial(4)
- num =4; factorial(4) --> 4 * factorial(3)
- num =3; factorial(3) --> 3 * factorial(2)
- num =2; factorial(2) --> 2 * factorial(1)
- num =1; factorial(1) --> 得到 1 接着向上执行;
- num =2; 2*factorial(1)–> 得到 2 接着向上执行;
- num =3; 3*factorial(2)–> 得到 6 接着向上执行;
- num =4; 4*factorial(3)–> 得到 24 接着向上执行;
- num =5; 5*factorial(4)–> 得到 120 得到最终结果为 120;
有一个小球要从黑色的位置到达对角处
0 -> 表示没走的点位; 1 ->表示围墙(不能通过); 2 ->表示走过的可行点; 3 ->表示走过的不可行点;
这就需要用到回朔法;小球在向前探索的过程中,遇到围墙就需要改变方向;
下面这种是以 下->右 ->上 -> 左的方向 前进的;
public class MazeDemo {
public static void main(String[] args) {
//定义二维数组作为迷宫;
int[][] mazeArray = new int[8][7];
//规定: 0 -> 表示没走的点; 1 ->表示围墙; 2 ->表示走过的可行点; 3 ->表示走过的不可行点;
//先初始化构造迷宫; 上下左右用围墙; 以及中间几个特殊点作为围墙;
for (int i = 0; i < 7; i++) {
mazeArray[0][i] = 1;
mazeArray[7][i] = 1;
}
for (int i = 0; i < 8; i++) {
mazeArray[i][0] = 1;
mazeArray[i][6] = 1;
}
//其他点的围墙
mazeArray[2][1] = 1;
mazeArray[2][2] = 1;
mazeArray[3][1] = 1;
mazeArray[3][2] = 1;
mazeArray[3][3] = 1;
mazeArray[3][4] = 1;
//输出查看原迷宫;
System.out.println("通行前的迷宫===>");
for (int[] ints : mazeArray) {
for (int i : ints) {
System.out.print(i + "t");
}
System.out.println();
}
//调用方法1,执行;
System.out.println(getSWay1(mazeArray, 1, 1));
System.out.println("下右上左==>通行后的迷宫===>");
for (int[] ints : mazeArray) {
for (int i : ints) {
System.out.print(i + "t");
}
System.out.println();
}
}
public static boolean getSWay1(int[][] mazeArray, int i, int j) {
//定义结束点;
if (mazeArray[6][5] == 2) {
return true;
}
//若点位为0,即初始点;
if (mazeArray[i][j] == 0) {
//假设取到的点位是可行点;可以向四个方向移动,下->右->上->左; 若还不可行,则将此点位标记为不可行点;
mazeArray[i][j] = 2;
if (mazeArray[i + 1][j] == 0) {
getSWay1(mazeArray,i+1, j);
return true;
} else if (mazeArray[i][j + 1] == 0) {
getSWay1(mazeArray,i, j+1);
return true;
} else if (mazeArray[i - 1][j] == 0) {
getSWay1(mazeArray,i-1, j);
return true;
} else if (mazeArray[i][j - 1] == 0) {
getSWay1(mazeArray,i, j-1);
return true;
} else {
mazeArray[i][j] = 3;
return false;
}
} else {
//点位的其余情况,直接不通过;
return false;
}
}
}
执行
通行前的迷宫===> 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 true 下右上左==>通行后的迷宫===> 1 1 1 1 1 1 1 1 2 2 2 0 0 1 1 1 1 2 2 2 1 1 1 1 1 1 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 1 1 1 1 1 1
当然,也可以采用其他的方向;
比如:上 ->右 ->下-> 左
public class MazeDemo {
public static void main(String[] args) {
//定义二维数组作为迷宫;
int[][] mazeArray = new int[8][7];
//规定: 0 -> 表示没走的点; 1 ->表示围墙; 2 ->表示走过的可行点; 3 ->表示走过的不可行点;
//先初始化构造迷宫; 上下左右用围墙; 以及中间几个特殊点作为围墙;
for (int i = 0; i < 7; i++) {
mazeArray[0][i] = 1;
mazeArray[7][i] = 1;
}
for (int i = 0; i < 8; i++) {
mazeArray[i][0] = 1;
mazeArray[i][6] = 1;
}
//其他围墙
mazeArray[2][1] = 1;
mazeArray[2][2] = 1;
mazeArray[3][1] = 1;
mazeArray[3][2] = 1;
mazeArray[3][3] = 1;
mazeArray[3][4] = 1;
//输出查看原迷宫;
System.out.println("通行前的迷宫===>");
for (int[] ints : mazeArray) {
for (int i : ints) {
System.out.print(i + "t");
}
System.out.println();
}
//执行方式2;
boolean result = getSWay2(mazeArray, 1, 1);
System.out.println(result);
System.out.println("上右下左==>通行后的迷宫===>");
for (int[] ints : mazeArray) {
for (int i : ints) {
System.out.print(i + "t");
}
System.out.println();
}
}
public static boolean getSWay2(int[][] mazeArray, int i, int j) {
//定义结束点;
if (mazeArray[6][5] == 2) {
return true;
}
//若点位为0,即初始点;
if (mazeArray[i][j] == 0) {
//假设取到的点位是可行点;可以向四个方向移动,上->右->下->左; 若还不可行,则将此点位标记为不可行点;
mazeArray[i][j] = 2;
if (getSWay2(mazeArray,i-1, j)) {
return true;
} else if (getSWay2(mazeArray,i, j+1)) {
return true;
} else if (getSWay2(mazeArray,i+1, j)) {
return true;
} else if (getSWay2(mazeArray,i, j-1)) {
return true;
} else {
mazeArray[i][j] = 3;
return false;
}
} else {
//点位的其余情况,直接不通过;
return false;
}
}
}
执行的路径
通行前的迷宫===> 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 true 上右下左==>通行后的迷宫===> 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 1 1 0 0 2 1 1 1 1 1 1 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 0 0 0 0 2 1 1 1 1 1 1 1 13.八皇后问题
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
本次解决思路,采用一维数组来表示每个皇后的位置;数组的下标索引作为皇后所在的行(从零开始的);
数组的元素值作为皇后的所在列位置
public class EightQueens {
public static void main(String[] args) {
EightQueens eq = new EightQueens();
//从第1个皇后开始; 即0;
eq.addQueen(0);
System.out.println("总共的解法为->"+count);
}
//定义时,考虑使用 一个一维数组解决即可;数组的索引下标表示行(从零开始的); 数组的元素表示当前皇后所在的列;
int queen = 8;
int[] queenArray = new int[queen];
//统计问题的解法;
static int count = 0;
//输出皇后的方法;
private void getQueenArray(){
//记录被调用的次数;
count ++;
for (int j : queenArray) {
System.out.print(j + "t");
}
System.out.println();
}
//添加皇后时,判断是否冲突问题; q: 表示第几个皇后;
private boolean isConflict(int q){
for (int i = 0; i < q; i++) {
//不在同一列;且不在间隔对角线;
if(queenArray[q]==queenArray[i] || Math.abs(q-i)==Math.abs(queenArray[q]-queenArray[i])){
return false;
}
}
return true;
}
//添加皇后; 第几个皇后;
public void addQueen(int num){
//添加结束;
if(num == queen){
getQueenArray();
return;
}
for (int i = 0; i < queen; i++) {
//添加;
queenArray[num] =i;
//若添加皇后时不冲突;
if(isConflict(num)){
addQueen(num+1);
}
}
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）