• 方法递归调用

    目录

    递归举例 1 ：  “ 打印问题  ”  

    递归举例 2 ：  “ 阶乘问题  ”  

             递归的重要规则 ： 

    练习1（递归斐波那契）：

    练习 2 （猴子吃桃）：

    递归调用应用实例 - 迷宫问题 

    递归调用应用实例 -汉诺塔

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

    递归举例 1 ：  “ 打印问题  ”  

    第一种： 

    1. public class Recursion01 {
    2.     public static void main(String[] args) {
    3.         T t1 = new T();
    4.         t1.test(4);  
    5.     }
    6. }
    7.  
    8. class T {
    9.     //分析   
    10.     public void test (int n ){
    11.         if (n > 2 ){
    12.             test(n - 1);
    13.         }
    14.         System.out.println("n="+n);  //输出n=2  n=3   n=4
    15.     }
    16. }

    结果： 

     第二种： （与前面代码大体一致，唯一变化的是，添加了 “ else ” ）

    1. public class Recursion01 {
    2.     public static void main(String[] args) {
    3.         T t1 = new T();
    4.         t1.test(4);  
    5.     }
    6. }
    7.  
    8. class T {
    9.     //分析   
    10.     public void test(int n) {
    11.         if (n > 2) {
    12.             test(n - 1);
    13.         } else {
    14.             System.out.println("n=" + n); //只 输出n=2
    15.         }
    16.     }
    17. }

    结果  ： 

    该图是对打印问题的分析：

    递归举例 2 ：  “ 阶乘问题  ”  

    1. public class Recursion01 {
    2.     public static void main(String[] args) {
    3.         T t1 = new T(); 
    4.         int res = t1.factorial(5);
    5.         System.out.println("res=" + res);
    6.     }
    7. }
    8.  
    9. class T {
    10.     //分析   
    11.     //factorial  阶乘
    12.     public int factorial(int n) {
    13.         if (n == 1) {
    14.             return 1;
    15.         } else {
    16.             return factorial(n - 1) * n;
    17.         }
    18.     }
    19. }

    分析图：

     结果： 

     递归的重要规则 ： 

    1. 执行一个方法时 ，就创建一个新的受保护的独立空间（ 栈空间  ） 


    2. 方法的局部变量是独立的 ， 不会相互影响   ， 比如 n 变量


    3. 如果方法中使用的是引用类型变量（ 比如数组） ， 就会共享该引用类型的数据


    4. 递归必须向退出递归的条件逼近 ， 否则就是 无限递归 ， 出现  “  Stack OverflowError ， 死龟了： ”


    5. 当一个方法执行完毕 ， 或者遇到 return ， 就会返回 ，遵守谁调用 ，就将结果返回给谁 ， 同时当方法执行完毕或者返回时 ， 该方法也就执行完毕。

    练习1（递归斐波那契）：

    请使用递归的方式求出斐波那契数 1 ，1 ， 2 ，3 ，5 ，8 ，13…… 给你一个整数 n ， 求出它的值是多少

    思路分析：

     当 n = 1 斐波那契数 是1
     当 n = 2 斐波那契数 是1
     当 n >= 3 斐波那契数 是前两个数的和
      这里就是一个递归的思路  

    1. public interface RecursionExercise01 {
    2.     public static void main(String[] args) {
    3.  
    4.         T1 t1 = new T1();
    5.         int n = 7;
    6.         int res = t1.fibonacci(n);
    7.         if (res != -1) {
    8.             System.out.println("当 n = " + n + "对应的斐波那契数=" + res);
    9.         }
    10.     }
    11. }
    12. class T1 {
    13.     public int fibonacci(int n) {
    14.         if (n >= 1) {
    15.             if (n == 1 || n == 2) {
    16.                 return 1;
    17.             } else {
    18.                 return fibonacci(n - 1) + fibonacci(n - 2);
    19.             }
    20.         } else {
    21.             System.out.println("要求输入的 n>=1 的整数");
    22.             return -1;
    23.         }
    24.     }
    25. }

    结果： 

    练习 2 （猴子吃桃）：

    猴子吃桃子问题： 有一堆桃子 ， 猴子第一天吃了其中的一半 ， 并再多吃了一个 ！ 以后每天都吃其中的一半，然后再多吃一个。当到了第10天时，想再吃时（即还没吃），发现只有一个桃子了。问题：最初共有多少个桃子？

        思路分析：  逆推
        1. day = 10 时  有 1 个桃子
        2. day = 9 时， 有 （day10 + 1） * 2 = 4
        3. day = 8 时， 有（day9 + 1 ） * 2 = 10
        4。 规律就是 前一天的桃子 = （ 后一天的桃子 + 1 ） * 2
        5. 递归

    1. public interface RecursionExercise01 {
    2.     public static void main(String[] args) {
    3.         T1 t1 = new T1();
    4.         int day = 1;
    5.         int peachNum = t1.peach(day);
    6.         if (peachNum != -1){
    7.             System.out.println("第"+day+"天 有"+peachNum+"个桃子");
    8.         }
    9.     }
    10. }
    11.  
    12.  
    13. class T1 {
    14.     public int peach(int day) {
    15.         if (day == 10) {//第10天只有一个桃子
    16.             return 1;
    17.         } else if (day >= 1 && day <= 9) {
    18.             return (peach(day + 1) + 1) * 2;  //后一天
    19.         } else {
    20.             System.out.println("day 在1-10 ");
    21.             return -1;
    22.         }
    23.     }
    24.  
    25. }

    结果： 

    递归调用应用实例 - 迷宫问题 

    题目：

    1. 小球得到的路径 ， 和程序员设置的找路策略有关 ， 即： 找路的上下左右的顺序相关
2. 再得到小球路径时，可以先使用（下右上左）， 再改成（上右下左），看看路径是不是有变化
3. 测试回溯现象
4. 扩展思考： 如何求出最短路径？


            思路：


            1. 先创建迷宫，用二维数组表示 int[][] map = new int[8][7] ;


            2. 先规定 map 数组的元素值 ： 0 表示走， 1 表示障碍物
     

    一 、下面代码是老鼠还没有走的时候，只是地图的形状

    1. public class MiGong {
    2.     public static void main(String[] args) {
    3.         
    4.         int[][] map = new int[8][7];
    5.         //3. 将最上面的一行和最下面的一行，全部设置为 1
    6.         for (int i = 0; i < 7; i++) {
    7.             map[0][i] = 1;
    8.             map[7][i] = 1;
    9.         }
    10.         //4. 将最右边的一列和最左边的一列 ， 全部设置为 1
    11.         for (int i = 0; i < 8; i++) {
    12.             map[i][0] = 1;
    13.             map[i][6] = 1;
    14.         }
    15.         map[3][1] = 1;
    16.         map[3][2] = 1;
    17.  
    18.         //输出当前地图
    19.         System.out.println("======当前地图情况=======");
    20.         for (int i = 0; i < map.length; i++) {
    21.             for (int j = 0; j < map[i].length; j++) {
    22.                 System.out.print(map[i][j] + "");//输出一行
    23.             }
    24.             System.out.println();
    25.         }
    26.     }
    27. }

    结果 ： 

    二、 测试回溯现象 （下面则是老鼠在地图上走的路线）

    使用递归回溯的思想

1. findWay 方法就是专门来找出迷宫路径
2，如果找到， 就返回 true ，否则返回 false
3. map 就是二维数组， 即表示迷宫
4. i、j 就是老鼠的位置，初始化 的位置为 （1， 1）
5. 因为我们是递归的找路， 所以我先规定 map 数组的各个值的含义
    0 表示可以走，1 表示障碍物，2 表示可以走， 3 表示 走过， 但是走不通
6。当 map[6][5] = 2 就说明找到通路 就可以 ，否则继续找
7. 先确定老鼠找路策略  下 -> 右 -> 上 -> 左

    下图是 i 与 j 在迷宫里分别表示的含义：

     代码实现：

    1. public class MiGong {
    2.     public static void main(String[] args) {
    3.         // 迷宫问题
    4.         //思路：
    5.         //1. 先创建迷宫，用二维数组表示 int[][] map = new int[8][7] ;
    6.         //2. 先规定 map 数组的元素值 ： 0 表示走， 1 表示障碍物
    7.  
    8.         int[][] map = new int[8][7];
    9.         //3. 将最上面的一行和最下面的一行，全部设置为 1
    10.         for (int i = 0; i < 7; i++) {
    11.             map[0][i] = 1;
    12.             map[7][i] = 1;
    13.         }
    14.         //4. 将最右边的一列和最左边的一列 ， 全部设置为 1
    15.         for (int i = 0; i < 8; i++) {
    16.             map[i][0] = 1;
    17.             map[i][6] = 1;
    18.         }
    19.         map[3][1] = 1;
    20.         map[3][2] = 1;
    21. //       下面是上下左右都走不了的情况
    22. //        map[2][1] = 1;
    23. //        map[2][2] = 1;
    24. //        map[1][2] = 1; 
    25.  
    26.         //输出当前地图
    27.         System.out.println("======当前地图情况=======");
    28.         for (int i = 0; i < map.length; i++) {
    29.             for (int j = 0; j < map[i].length; j++) {
    30.                 System.out.print(map[i][j] + "");//输出一行
    31.             }
    32.             System.out.println();
    33.         }
    34.         //使用findWay给老鼠找路
    35.         T2 t1 = new T2();
    36.         t1.findWay(map, 1, 1);
    37.  
    38.         System.out.println("\n======找路的情况如下=====");
    39.  
    40.         for (int i = 0; i < map.length; i++) {
    41.             for (int j = 0; j < map[i].length; j++) {
    42.                 System.out.print(map[i][j] + "");//输出一行
    43.             }
    44.             System.out.println();
    45.         }
    46.     }
    47. }
    48.  
    49. class T2 {
    50.     //使用递归回溯的思想来解决老鼠出迷宫
    51.  
    52.     //1. findWay 方法就是专门来找出迷宫的路径
    53.     //2. 如果找到 ， 就返回 true ，否则返回 false
    54.     //3. map 就是二维数组 ，即表示迷宫
    55.     //4. i、j 就是老鼠的位置，初始化的位置为（ 1，1）
    56.     //5. 因为我们是递归的找路，所以我先规定 map 数组的各个值的含义
    57.     //   0 表示可以走， 1 表示障碍物 , 2 表示可以走 ， 3 表示走过 ，但是走不通是死路
    58.     //6. 当 map[6][5] = 2 就说明找到通路 就可以 ，否则就继续找
    59.     //7. 先确定老鼠找路策略  下 -> 右 -> 上 -> 左
    60.  
    61.     public boolean findWay(int[][] map, int i, int j) {
    62.  
    63.         if (map[6][5] == 2) {//说明已经找到
    64.             return true;
    65.         } else {
    66.             if (map[i][j] == 0) {//当前这个位置 0 ，说明表示可以走
    67.                 //我们假定可以走通
    68.                 map[i][j] = 2;
    69.                 //使用找路策略，来确定该位置是否真的可以走通
    70.                 // 下 -> 右 -> 上 -> 左
    71.                 if (findWay(map, i + 1, j)) { // 先走 下
    72.                     return true;
    73.                 } else if (findWay(map, i, j + 1)) { // 右
    74.                     return true;
    75.                 } else if (findWay(map, i - 1, j)) { // 上
    76.                     return true;
    77.                 } else if (findWay(map, i, j - 1)) {// 左
    78.                     return true;
    79.                 } else {
    80.                     map[i][j] = 3;
    81.                     return false;
    82.                 }
    83.             } else {//map[i][j]=1,2,3
    84.                 return false;
    85.             }
    86.         }
    87.     }
    88. }

    结果 : 

     三、  修改找路策略 ， 看看路径是否有变化
       下 -> 右 -> 上 -> 左   ===>  上 -> 右 -> 下  -> 左

    代码实现：

    1. public class MiGong {
    2.     public static void main(String[] args) {
    3.         // 迷宫问题
    4.  
    5.         //思路：
    6.         //1. 先创建迷宫，用二维数组表示 int[][] map = new int[8][7] ;
    7.         //2. 先规定 map 数组的元素值 ： 0 表示走， 1 表示障碍物
    8.  
    9.         int[][] map = new int[8][7];
    10.         //3. 将最上面的一行和最下面的一行，全部设置为 1
    11.         for (int i = 0; i < 7; i++) {
    12.             map[0][i] = 1;
    13.             map[7][i] = 1;
    14.         }
    15.         //4. 将最右边的一列和最左边的一列 ， 全部设置为 1
    16.         for (int i = 0; i < 8; i++) {
    17.             map[i][0] = 1;
    18.             map[i][6] = 1;
    19.         }
    20.         map[3][1] = 1;
    21.         map[3][2] = 1;
    22.  
    23.         //输出当前地图
    24.         System.out.println("======当前地图情况=======");
    25.         for (int i = 0; i < map.length; i++) {
    26.             for (int j = 0; j < map[i].length; j++) {
    27.                 System.out.print(map[i][j] + "");//输出一行
    28.             }
    29.             System.out.println();
    30.         }
    31.         //使用findWay给老鼠找路
    32.         T2 t1 = new T2(); 
    33.         t1.findWay2(map, 1, 1);
    34.  
    35.         System.out.println("\n======找路的情况如下=====");
    36.  
    37.         for (int i = 0; i < map.length; i++) {
    38.             for (int j = 0; j < map[i].length; j++) {
    39.                 System.out.print(map[i][j] + "");//输出一行
    40.             }
    41.             System.out.println();
    42.         }
    43.     }
    44. }
    45. class T2 {
    46. //  修改找路策略 ， 看看路径是否有变化
    47.     //  下 -> 右 -> 上 -> 左   ===>  上 -> 右 -> 下  -> 左
    48.     public boolean findWay2(int[][] map, int i, int j) {
    49.  
    50.         if (map[6][5] == 2) {//说明已经找到
    51.             return true;
    52.         } else {
    53.             if (map[i][j] == 0) {//当前这个位置 0 ，说明表示可以走
    54.                 //我们假定可以走通
    55.                 map[i][j] = 2;
    56.                 //使用找路策略，来确定该位置是否真的可以走通
    57.                 // 下 -> 右 -> 上 -> 左
    58.                 if (findWay2(map, i - 1, j)) { // 先走 上
    59.                     return true;
    60.                 } else if (findWay2(map, i, j + 1)) { // 右
    61.                     return true;
    62.                 } else if (findWay2(map, i + 1, j)) { // 上
    63.                     return true;
    64.                 } else if (findWay2(map, i, j - 1)) {// 左
    65.                     return true;
    66.                 } else {
    67.                     map[i][j] = 3;
    68.                     return false;
    69.                 }
    70.             } else {//map[i][j]=1,2,3
    71.                 return false;
    72.             }
    73.         }
    74.     }
    75. }

    结果 ： 

    递归调用应用实例 -汉诺塔

    思路：

     num 表示要移动的个数，a，b，c 分别表示 A塔 ， B塔 ， C塔
 如果只有一个盘 num=1
 如果有多个盘，可以看成两个，最下面的和上面的所有盘
（1）先移动上面所有的盘到 b ，借助 c
（2）最下面的这个盘，移动到c
（3）再把b塔的所有盘 ，移动到c ，借助a

    代码实现 ： 

    1. public class HanoiTower {
    2.     public static void main(String[] args) {
    3.         Tower tower = new Tower();
    4.         tower.move(5, 'A', 'B', 'C');
    5.     }
    6. }
    7.  
    8. class Tower {
    9.  
    10.     //方法
    11.     //num 表示要移动的个数，a，b，c 分别表示 A塔 ， B塔 ， C塔
    12.     public void move(int num, char a, char b, char c) {
    13.         //如果只有一个盘 num=1
    14.         if (num == 1) {
    15.             System.out.println(a + "->" + c);
    16.         } else {
    17.             //如果有多个盘，可以看成两个，最下面的和上面的所有盘
    18.             //（1）先移动上面所有的盘到 b ，借助 c
    19.             move(num - 1, a, c, b);
    20.             //（2）最下面的这个盘，移动到c
    21.             System.out.println(a + "->" + c);
    22.             //（3）再把b塔的所有盘 ，移动到c ，借助a
    23.             move(num - 1, b, a, c);
    24.         }
    25.     }
    26. }

    效果演示：

     

     结果：

  • 相关阅读:
    第八章 兼容多种模块标准的软件包封装
    鸡尾酒学习——长岛冰茶
    Maven多模块项目管理小结
    GPTS全网刷屏！定制增长速度指数增长
    Hive中内部表、外部表、分区表、分桶表之间的关系
    shiro详解-shiro史上最全学习笔记
    【Mac 教程系列第 18 篇】如何修改 iTerm2 的背景图片
    【QCustomPlot】下载
    `数学` 微积分基本定理
    剑指 Offer II 105. 岛屿的最大面积
  • 原文地址：https://blog.csdn.net/m0_57448314/article/details/126620828