侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

数据结构--递归(java实现)

林贤钦
2020-05-05 / 0 评论 / 9 点赞 / 763 阅读 / 0 字
温馨提示:
本文最后更新于 2020-05-09,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

数据结构--递归(java实现)

这篇主要讲递归,先用一个简单的例子99乘法表,再说一下注意事项,再然后举两个例子,用递归来解决迷宫问题和八皇后问题

概念

简单来说:递归就是方法自己调用自己,每次调用时传入不同的变量,递归有助于编程者解决复杂的问题,同时可以让代码变得整洁。

简单举例

99乘法表

public class MultiTable {
    public static void main(String args[]) {
        m(9);
    }
    public static void m(int i) {
        if (i == 1) {
            System.out.println("1*1=1 ");
        } else {
            m(i - 1);
            for (int j = 1; j <= i; j++) {
                System.out.print(j + "*" + i + "=" + j * i + " ");
            }
            System.out.println();
        }
    }
}

结果

11=1
1
2=2 22=4
1
3=3 23=6 33=9
14=4 24=8 34=12 44=16
15=5 25=10 35=15 45=20 55=25
1
6=6 26=12 36=18 46=24 56=30 66=36
1
7=7 27=14 37=21 47=28 57=35 67=42 77=49
18=8 28=16 38=24 48=32 58=40 68=48 78=56 88=64
19=9 29=18 39=27 49=36 59=45 69=54 79=63 89=72 9*9=81

分析

在99乘法表中,调用 m(int i)方法,递归退出条件就是 i==1,当i=1的时候,方法结束,返回上层方法,上层的代码就会走完,然后继续返回上层,直到结束。

递归的方式调用图示:

每一个方法的调用都会产生一个栈帧,压入到方法栈,当递归调用的时候,方法栈中栈帧的图示和上图类似。
去掉方法中栈帧的引用关系更加直观:如下图所示:

递归需要遵守的重要规则

  1. 执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
  2. 方法的局部变量时独立的,不相互影响
  3. 如果方法中使用的是引用类型的变量(如数组),就会共享该引用类型的数据。
  4. 递归必须向退出递归的条件逼近,否则就是无限递归,出现死龟
  5. 当一个方法实行完毕,或则遇到return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕。

递归能解决什么样的问题?

  • 各种数学问题:八皇后,汉诺塔,阶乘,迷宫,球和篮子等问题
  • 各种算法中也会使用到递归,如快排,归并排序,二分查找,分治算法等。
  • 将用栈解决的问题,递归代码比较简洁
  • 树形结构,比如我课设的时候使用的spring security ,其中用递归来将权限菜单数据封装成树形结构的形式返回前端。

迷宫问题

如图,我们用二维数组模拟迷宫,1代表墙壁,无法通行

//先创建一个二维数组,模拟迷宫地图
int[][] map = new int[8][7];
//使用1表示墙
// 上下全部置为1
for (int i = 0; i < 7; i++) {
    map[0][i]=1;
    map[7][i]=1;
}
//左右全部置为1
for (int i = 0; i < 8; i++) {
    map[i][0]=1;
    map[i][6]=1;
}
//设置挡板 ,1表示
map[3][1]=1;
map[3][2]=1;
map[5][3]=1;
map[4][4]=1;
map[4][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();
}

迷宫的地图

地图的情况
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 1 0 1 0 1
1 0 0 1 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1

约定

  1. map 表示地图
  2. i、j 表示从地图的哪个位置开始出发
  3. 如果小球能够到map[6][5]说明通路已经找到
  4. map[i][j]为0表示该点没走过,当为1表示墙,2表示通路可以走,3表示走过但是走不通
  5. 走迷宫的时候需要一个策略,下->右->上->左 ,如果走不通再回溯
public static boolean setWay(int[][]map,int i,int j){
    if (map[6][5]==2){//通路已经找到了
        return true;
    }else{
        if (map[i][j]==0){ //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  3
            return false;
        }
    }
}

调用递归方法

setWay(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 1 1 1 1 1 1
1 2 0 0 0 0 1
1 2 2 2 0 0 1
1 1 1 2 2 2 1
1 0 1 3 1 2 1
1 0 0 1 0 2 1
1 0 0 0 0 2 1
1 1 1 1 1 1 1


八皇后问题

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

八皇后问题算法思路分析

  1. 第一个皇后先放在第一行第一列
  2. 第二个皇后放在第二行第二列,然后判断是否ok,如果不ok,继续放在第二列,第三列,依次把所有列都放完,找到一个合适
  3. 继续第三个皇后,还是第一列,第二列······直到第8个皇后也能放在一个不冲突的位置,算是找到了一个正确的解
  4. 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放在第一列的所有的正确解全部得到
  5. 再回头继续第一个皇后放第二列,后面继续执行1234步骤,直到得到全部解

代码实现

1、定义数据
//定义一个max表示共有多少个皇后
int max=8;
//定义一个数组array,保存皇后放置位置的结果,比如arr ={0,4,7,5,2,6,1,3}
int[] array = new int [max];
//统计解法个数
static int count =0;
//统计判断次数
static int judgeCount =0;
2、方法print将皇后摆放的位置输出
//将皇后摆放的位置输出
private void print(){
    count++;
    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i]+" ");
    }
    System.out.println();
}
3、 就去检测该皇后是否和前面已经摆放的皇后冲突(核心)
  • array[i] == array[n] 表示判断第n个皇后和前面的n-1个皇后是在同一列

  • Math.abs(n-1) == Math.abs(array[n] -array[i]) 表示判断第n个皇后是否和第i皇后在同一斜线

  • 判断是否在同一行,因为每次n都是在递增,所以不用

/**
* 查看当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突
* @param n 表示第n-1个皇后
* @return
*/
private boolean judge(int n){
    judgeCount++;
    for (int i = 0; i < n; i++) {
        if (array[i] == array[n]||Math.abs(n-i)== Math.abs(array[n]-array[i])){
            return false;
        }
    }
    return true;
}
4、递归方法check(核心)
private void check(int n){
    if (n==max){
        // n ==max 摆放好了
        print();
        return;
    }
    // 依次放入皇后,并判断是否冲突
    for (int i = 0; i < max; i++) {
        //先把当前这个皇后 n 放入该行的第一列
        array[n]=i;
        //判断当放置第n个皇后到i列时,是否冲突
        if (judge(n)){
            //不冲突,接着放n+1 个皇后
            check(n+1);
        }
        //如果冲突,就继续执行array[n] = i ,即将第n个皇后放置在本行的后移的一个位置
    }
}
5、 main方法调用
public static void main(String[] args) {
    QueenB queenB = new QueenB();
    queenB.check(0);
    System.out.println(count);
    System.out.println(judgeCount);
}
6、结果

0 4 7 5 2 6 1 3
0 5 7 2 6 3 1 4
···
···
···
7 2 0 5 1 4 6 3
7 3 0 2 5 1 6 4
92
15720

9

评论区