方法递归调用

发布于:2023-01-02 ⋅ 阅读:(175) ⋅ 点赞:(0)

目录

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

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

         递归的重要规则 : 

练习1(递归斐波那契):

练习 2 (猴子吃桃):

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

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


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

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

第一种: 

public class Recursion01 {
    public static void main(String[] args) {
        T t1 = new T();
        t1.test(4);  
    }
}

class T {
    //分析   
    public void test (int n ){
        if (n > 2 ){
            test(n - 1);
        }
        System.out.println("n="+n);  //输出n=2  n=3   n=4
    }
}

结果: 

 第二种: (与前面代码大体一致,唯一变化的是,添加了 “ else ” )

public class Recursion01 {
    public static void main(String[] args) {
        T t1 = new T();
        t1.test(4);  
    }
}

class T {
    //分析   
    public void test(int n) {
        if (n > 2) {
            test(n - 1);
        } else {
            System.out.println("n=" + n); //只 输出n=2
        }
    }
}

结果  : 

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

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

public class Recursion01 {
    public static void main(String[] args) {
        T t1 = new T(); 
        int res = t1.factorial(5);
        System.out.println("res=" + res);
    }
}

class T {
    //分析   
    //factorial  阶乘
    public int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1) * n;
        }
    }
}

分析图:

 结果: 

 递归的重要规则 : 

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 斐波那契数 是前两个数的和
  这里就是一个递归的思路  

public interface RecursionExercise01 {
    public static void main(String[] args) {

        T1 t1 = new T1();
        int n = 7;
        int res = t1.fibonacci(n);
        if (res != -1) {
            System.out.println("当 n = " + n + "对应的斐波那契数=" + res);
        }
    }
}
class T1 {
    public int fibonacci(int n) {
        if (n >= 1) {
            if (n == 1 || n == 2) {
                return 1;
            } else {
                return fibonacci(n - 1) + fibonacci(n - 2);
            }
        } else {
            System.out.println("要求输入的 n>=1 的整数");
            return -1;
        }
    }
}

结果: 

练习 2 (猴子吃桃):

猴子吃桃子问题: 有一堆桃子 , 猴子第一天吃了其中的一半 , 并再多吃了一个 ! 以后每天都吃其中的一半,然后再多吃一个。当到了第10天时,想再吃时(即还没吃),发现只有一个桃子了。问题:最初共有多少个桃子?

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

public interface RecursionExercise01 {
    public static void main(String[] args) {
        T1 t1 = new T1();
        int day = 1;
        int peachNum = t1.peach(day);
        if (peachNum != -1){
            System.out.println("第"+day+"天 有"+peachNum+"个桃子");
        }
    }
}


class T1 {
    public int peach(int day) {
        if (day == 10) {//第10天只有一个桃子
            return 1;
        } else if (day >= 1 && day <= 9) {
            return (peach(day + 1) + 1) * 2;  //后一天
        } else {
            System.out.println("day 在1-10 ");
            return -1;
        }
    }

}

结果: 

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

题目:

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


        思路:


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


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

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

public class MiGong {
    public static void main(String[] args) {
        
        int[][] map = new int[8][7];
        //3. 将最上面的一行和最下面的一行,全部设置为 1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //4. 将最右边的一列和最左边的一列 , 全部设置为 1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;

        //输出当前地图
        System.out.println("======当前地图情况=======");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "");//输出一行
            }
            System.out.println();
        }
    }
}

结果 : 

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

使用递归回溯的思想

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 在迷宫里分别表示的含义:

 代码实现

public class MiGong {
    public static void main(String[] args) {
        // 迷宫问题
        //思路:
        //1. 先创建迷宫,用二维数组表示 int[][] map = new int[8][7] ;
        //2. 先规定 map 数组的元素值 : 0 表示走, 1 表示障碍物

        int[][] map = new int[8][7];
        //3. 将最上面的一行和最下面的一行,全部设置为 1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //4. 将最右边的一列和最左边的一列 , 全部设置为 1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
//       下面是上下左右都走不了的情况
//        map[2][1] = 1;
//        map[2][2] = 1;
//        map[1][2] = 1; 

        //输出当前地图
        System.out.println("======当前地图情况=======");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "");//输出一行
            }
            System.out.println();
        }
        //使用findWay给老鼠找路
        T2 t1 = new T2();
        t1.findWay(map, 1, 1);

        System.out.println("\n======找路的情况如下=====");

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "");//输出一行
            }
            System.out.println();
        }
    }
}

class T2 {
    //使用递归回溯的思想来解决老鼠出迷宫

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

    public boolean findWay(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 (findWay(map, i + 1, j)) { // 先走 下
                    return true;
                } else if (findWay(map, i, j + 1)) { // 右
                    return true;
                } else if (findWay(map, i - 1, j)) { // 上
                    return true;
                } else if (findWay(map, i, j - 1)) {// 左
                    return true;
                } else {
                    map[i][j] = 3;
                    return false;
                }
            } else {//map[i][j]=1,2,3
                return false;
            }
        }
    }
}

结果 : 

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

代码实现:

public class MiGong {
    public static void main(String[] args) {
        // 迷宫问题

        //思路:
        //1. 先创建迷宫,用二维数组表示 int[][] map = new int[8][7] ;
        //2. 先规定 map 数组的元素值 : 0 表示走, 1 表示障碍物

        int[][] map = new int[8][7];
        //3. 将最上面的一行和最下面的一行,全部设置为 1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //4. 将最右边的一列和最左边的一列 , 全部设置为 1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;

        //输出当前地图
        System.out.println("======当前地图情况=======");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "");//输出一行
            }
            System.out.println();
        }
        //使用findWay给老鼠找路
        T2 t1 = new T2(); 
        t1.findWay2(map, 1, 1);

        System.out.println("\n======找路的情况如下=====");

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + "");//输出一行
            }
            System.out.println();
        }
    }
}
class T2 {
//  修改找路策略 , 看看路径是否有变化
    //  下 -> 右 -> 上 -> 左   ===>  上 -> 右 -> 下  -> 左
    public boolean findWay2(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 (findWay2(map, i - 1, j)) { // 先走 上
                    return true;
                } else if (findWay2(map, i, j + 1)) { // 右
                    return true;
                } else if (findWay2(map, i + 1, j)) { // 上
                    return true;
                } else if (findWay2(map, i, j - 1)) {// 左
                    return true;
                } else {
                    map[i][j] = 3;
                    return false;
                }
            } else {//map[i][j]=1,2,3
                return false;
            }
        }
    }
}

结果 : 

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

思路:

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

代码实现 : 

public class HanoiTower {
    public static void main(String[] args) {
        Tower tower = new Tower();
        tower.move(5, 'A', 'B', 'C');
    }
}

class Tower {

    //方法
    //num 表示要移动的个数,a,b,c 分别表示 A塔 , B塔 , C塔
    public void move(int num, char a, char b, char c) {
        //如果只有一个盘 num=1
        if (num == 1) {
            System.out.println(a + "->" + c);
        } else {
            //如果有多个盘,可以看成两个,最下面的和上面的所有盘
            //(1)先移动上面所有的盘到 b ,借助 c
            move(num - 1, a, c, b);
            //(2)最下面的这个盘,移动到c
            System.out.println(a + "->" + c);
            //(3)再把b塔的所有盘 ,移动到c ,借助a
            move(num - 1, b, a, c);
        }
    }
}

效果演示:

 

 结果:


网站公告

今日签到

点亮在社区的每一天
去签到