递归

:::info 💡 递归：可以在代码中，显著减少代码量；用简单代码解决复杂问题，提高代码的可读性；实际应用：比如用递归解决阶乘问题，斐波那契数列等。 :::

1 递归知识梳理

2 什么是递归？递归怎么用？

2.1 什么是递归❓

递归：就是在运行的过程中调用自己。

2.2 递归怎么用呢❓

2个基本条件： ①问题与子问题是相同问题时用递归来解决 ②递归必须有结束条件（也就是出口） 2个注意事项： ①递归需要想退出条件逼近[否则为死龟] ②递归执行次数不能太多，否则容易栈溢出

3 递归的案例

3.1 递归入门案例

指定一个大于2的整数，依次递减并在打印台，打印递减效果：

A：用递归解决：

//工具类
class Tools {
    public void diminishing(int n) {
        System.out.println("(递归递减)数为：" + n);
        if (n > 2) {
            diminishing(--n);
        }
    }
}
//测试类
public class Recursion {
    public static void main(String[] args) {
//        用递归解决递减问题
          //创建test对象
        Tools tool1 = new Tools();
         //调用递减函数
        tool1.diminishing(6);
}

💡递归调用的内存图解：

B：用循环解决上述问题：

public class Recursion {
    public static void main(String[] args) {
//        用循环解决递减问题
        diminishing2(6);
    }
    public static void diminishing2(int n){
        System.out.println("(循环递减)数为：" + n);
        while (n>2){
            n--;
            System.out.println("(循环递减)数为：" + n);
        }
    }
}

执行效果：

3.2 递归与循环有什么区别？

递归：是某个方法多次调用本身去解决问题，本质是调用方法，且方法调用用结束方法栈会弹栈，直到再次回到主函数【递归有去有回】；所以递归调用次数太多会占用栈内存。 循环：是在满足某些条件下多次执行某些语句，循环语句是由循环体及循环的终止条件两部分组成的【循环有去无回】。

【注意】：递归，传递的参数为基本类型时每次调用函数本身都会重新重新开辟局部变量空间，参数为应用类型时每次调用函数都用同一数据

3.3 斐波那契数列

public class Recursion2 {
    public static void main(String[] args) {
        /*
         * 给定一个整数N,求出小于N的斐波那契数列
         * */
        //   循环实现
        int N = 56;
        int a = 0;
        int b = 1;
        int c = 0;
        while (true){
            a = b;
            b = c;
            c = a + b;
            if (c>N)break;
            System.out.println(c);
        }
        //递归解决
        System.out.println("=====================================");
        int i = 1;
      while (true){
          if (fibonacci(i)>N){
              break;
          }
          System.out.println(fibonacci(i));
          i++;
      }
    }
    //递归实现
    public static int fibonacci(int n){
        if(n ==1 || n== 2){
            return  1;
        } else if (n>2){
            return fibonacci(n-1)+fibonacci(n-2);
        }else {
            return -1;
        }
    }
}

3.4 迷宫问题

①**需求分析：**

在地图上通过程序，找出通往终点的路径： “#”表示障碍物 “0”表示未通行路径 “*”表示走过路径 “%”表示走过且不能走路径

②效果展示
原始地图：

程序找出的路径：

③代码实现：

public class MiGong {
    public static void main(String[] args) {
        /*
        *   "#"表示障碍物
        *   “0"表示未通行路径
        *   "*"表示走过路径
        *   “%”表示走过且不能走路径
        *
        * */
        move();
    }
    //        制定路线规则：右——>下——>左——>上
    public static void move(){
        String map [][] = new String[8][8];
//        填充地图
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                map[i][j] = "0";
            }
        }
//        绘制障碍物
        for (int i = 0; i < map.length; i++) {
            map[0][i] = "#";
            map[7][i] = "#";
        }
        for (int i = 0; i <map[0].length ; i++) {
            map[i][0] = "#";
            map[i][7] = "#";
        }
        map[2][1] = "#";
        map[2][2] = "#";
        map[4][5] = "#";
        map[4][6] = "#";
        map[1][1] = "0";
        map[6][6] = "@";
//        设置障碍
        map[4][2] = "#";
        map[5][2] = "#";
        map[5][2] = "#";
        map[4][3] = "#";
        map[4][4] = "#";
        map[4][5] = "#";
        map[2][6] = "#";
        map[2][5] = "#";
        map[2][4] = "#";
//        打印地图
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }
        System.out.println("开始游戏！");
//        移动老鼠
        findWay(map,1,1);
        //        打印地图
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j]+"  ");
            }
            System.out.println();
        }
    }
    public static boolean findWay(String map [][],int row,int column){
        boolean flag = false;
//        "@"为终点，如果找到找到终点，则返回true
        if (map[row][column]=="@"){
            flag = true;
            map[row][column] = "赢";
            return flag;
        }else if (map[row][column]=="0"){
//            "0"为可通过路径，为"0"则把此点标记为已通过路径"&"并先向右走一步
            map[row][column] = "*";
            if (findWay(map,row,column+1)){//向右走
                flag = true;
                return flag;
            }else if (findWay(map,row+1,column)){//向下走
                flag = true;
                return flag;
            }else if (findWay(map,row,column-1)){//向左走
                flag = true;
                return flag;
            }else if (findWay(map,row-1,column)){//向上走
                flag = true;
                return flag;
            }else {
                flag = false;
                map[row][column] = "%";
                return flag;
            }
        }else{
            flag = false;
            return flag;
        }
    }
}