方法递归调用

目录

递归举例 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);
        }
    }
}

效果演示：

 结果：