您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

递归(图文)

第十三双眼睛2022-06-17【数据结构与算法】人已围观

简介递归

递归能解决什么样得问题
能解决各种数学问题，如：八皇后问题，汉诺塔问题，阶乘问题，走迷宫问题。
各种算法中也会使用到递归，如快排，归并排序，二分查找，分治算法，
用栈解决得问题用递归解决，代码更简洁

递归需要遵守得重要规则
执行一个方法时，就创建一个受保护得独立得空间（栈帧）
方法得局部变量是独立得，不会互相影响
递归必须向退出得条件逼近，不能无休止得递归。
当一个方法执行完毕或者遇到return时，就会返回，遵守谁调用就会将结果返回给谁。
走迷宫案例:

package day004;
public class MiGong {
public static void main(String[] args) {
// 初始化地图
int [][] map = new int[8][7];
// 设置墙
for(int i=0;i<7;i++){
map[0][i]=1;
map[7][i]=1;
}
// 设置墙
for(int i=0;i<8;i++){
map[i][0]=1;
map[i][6]=1;
}
// 设置墙
map[3][1]=1;
map[3][2]=1;
// 打印地图
for(int i=0;i<8;i++){
for(int j=0;j<7;j++){
System.out.printf("%d\t",map[i][j]);
}
System.out.println();
}
// 分割线
System.out.println("===========");
setWay(map,1,1);
// 打印路径
for(int i=0;i<8;i++){
for(int j=0;j<7;j++){
System.out.printf("%d\t",map[i][j]);
}
// 打印完一行后换行
System.out.println();
}
}
/**
*
* @param map
* @param i 表示从地图得哪个位置处罚
* @param j
* 如能到[6][5]表示小球能到
* 当map[i][j]为0时没有走过 2表示可以走通 3表示走不通
* 走迷宫时,下右上左，如果走不通
* @return
*/
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-1,j)){
return true;
}else {
map[i][j]=3;
return false;
}
}else {
return false;
}
}
}
}

八皇后问题

package day004;
public class Queue8 {
static int max = 8;
static int arr[] = new int[8];
public static void main(String[] args) {
check(0);
}
private static void check(int n){
if(n==max){
print();
return;
}
for(int i=0;i<max;i++){
arr[n]=i;
if(judge(n)){
check(n+1);
}
}
}
private static boolean judge(int n){
for(int i=0;i<n;i++){
if(arr[i]==arr[n] || Math.abs(n-i) ==Math.abs(arr[n]-arr[i])){
return false;
}
}
return true;
}
public static void print(){
for(int i=0;i<8;i++){
System.out.print(arr[i]);
}
System.out.println();
}
}

Tags：递归

很赞哦！ ()

上一篇：前缀，中缀，后缀表达式(图文)

下一篇：冒泡排序(图文)