方法递归调用

方法递归调用

———基本介绍

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

pubilc void f1(){
    f1();
}
//方法f1还是方法f1,也就表示一直调用同一个方法

· 递归能解决什么问题？

1. 各种数学问题如：8皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子的问题(google编程 大赛)[简单演示]

2. 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等

3. 将用栈解决的问题->递归代码比较简洁

 

 

 

递归 (recursion)

1.打印问题 2.阶乘问题

public class recursion {
    public static void main(String[] args) {
        T t = new T();
        t.test(10);
    }
}
​
class T {
    //分析
    public void test(int n){
        if (n > 2){
            test(n - 1);
            //递归在这里产生
        }
        System.out.println("n="+n);
    }
}

1. 首先是这个打印的代码 ,我们编写了一个类 叫做 T , 其中编写了一个方法 test ,方法的内容为 如果 n > 2 的话 ,就执行test方法本身 ,而执行的过程当中会将 n -1 ,也就表示这个递归方法具有一个终止条件

2. 假设传参进去的数字为 4 ,首先进行判断 4 > 2 那么就执行一个递归, 此时 栈空间 的 test方法栈加 1, 也就是开辟出来一个新的栈 ,之后 4-1依次类推

3. 当递归到n = 2的时候 ,就不会产生新的方法栈 ,而是开始执行代码后面的语句 ,也就是打印 n ,此时n 为2 ,因此第一个打印的就是 2 ,之后n = 2的栈就结束了生命 ,往下就是 n = 3的栈 ,打印输出 n = 3之后 按照顺序一直执行到 n = 4 ,此时方法就使用结束了

//阶乘

public int factorial(int n){
    if(n==1) {
        return 1;
    }else{
        return factorial(n - 1) * n;
    }
}

假设我们传入的参数是3 ,首先进入代码中

1. 3不等于1 ,因此进入递归 factorial(n – 1) * n ,也就是 (3 – 1) * 3 ,也就是 factorial(2) * n

2. 接下来就执行 n = 2继续判断, 继续递归开辟一个新的栈空间 ,最终得到 factorial(1) * 1

3. 进入这个递归发现符合条件 n == 1,此时就终止递归 ,从最顶级的递归从上而下来执行

4. 简化下来也就是 : n = 1 * 2 * 3

5. 因此结果就为 6

6. 详细来讲就是从顶级的递归逐级往下返回 ,符合条件之后返回的数值是1 ,因此就返回到第二层带入进去就是 , 1 * 2 = 2 , 2再返回到下一级就是 2 * 3 = 6 返回结束 结果就为 6了 ,这个代码就可以实现指定数字的阶乘

 

递归重要规则

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

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

3. 如果方法中使用的是引用类型变量 ( 比如数组,对象 ), 就会共享该引用类型 的数据.

4. 递归必须向退出递归的条件逼近，否则就是无限递归，出现 StackOverflowError(栈溢出), 死龟了

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

 

代码示例 , 斐波那契数列的实现 ,以及 猴子吃桃子的问题

1. 斐波那契数列 1 1 2 3 5 …………… ,按照规律就是前面两个数相加得到后面一个数, 问题是求 第n个数是多少

2. 猴子吃桃问题具体就是 ,每天吃一半外加再吃一个 ,最终到第10天就只剩下 1个

 

public class RecursionExercise01 {
    public static void main(String[] args) {
        TX t1 = new TX();
        System.out.println("当n=7时对应的斐波那契数为"+t1.Fibonacci(7));
        System.out.println(t1.eat_peaches(1));;
    }
}
​
class TX {
    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;
        }
    }
​
    public int eat_peaches(int day){
        if (day == 10){
            return 1;
        }else if (day>=1 && day <=9){
            return (eat_peaches(day + 1) + 1) * 2;
        }else{
            return -1;
        }
    }
}

代码分析

首先是斐波那契数列 1 1 2 3 5 8 ……..

1. 首先 当 n = 1 ,也就是第一个数字 ,为 1

2. 当 n = 2 的时候 ,第二个数字还是为 1

3. 当 n >= 3的时候 ,可以发现数字是由前面两个数字相加得到的数字

4. 假设我想要得到 n = 5的数字 ,那么就是 第三位 和 第四位相加 , 也就是 n -2 + n -1

5. 知道这个公式之后就可以编写递归代码 -> return (fn - 2) + (fn - 1)

6. 同时如果n = 1 或者 2, 那么就返回1 ,这里写一个判断语句即可

猴子吃桃子问题分析

1. 问题中可以得知 ,是从第一天开始的桃子数 / 2 – 1 ,不断重复一直到 第十天(day10)

2. 那么已知day10的时候桃子数量是1 ,那么不妨可以进行一个反推

3. 也就是day9桃子数 为 ((day9 + 1) * 2 + 1)

4. 转换为公式也就是 –> return function(day + 1) * 2 + 1

 

 

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

1. 小球得到的路径，和程序员设置的找路策略有 关即：找路的上下左右的顺序相关

2. 再得到小球路径时，可以先使用( 下右上左 ) , 再改成( 上右下左 ), 看看路径是不是有变化

3. 测试回溯现象

4. 扩展思考：如何求出最短路径？

 

代码分析 :

1. 先创建一个迷宫 ,迷宫就用数组来表示 ,例如 int[][] map = new int[8][7]表示这个迷宫8行7列

2. 规定map数组的元素值 : 0表示可以走 ,1就表示有障碍物 ,不能走

3. 将最上面的一行和最下面的一行全部设置为1

public class MIGONG {
    public static void main(String[] args) {
        int [][] map = new int[8][7];
        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;
        //单独设置障碍物,也就是再数组对应的位置更改为1
        //0就是可以可以移动的位置
​
​
​
        //输出当前的迷宫数组
        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方法测试寻路功能
        Tmouse t1 = new Tmouse();
        t1.findway(map,1,1);
        //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 Tmouse {
    //使用递归回溯的思想来解决老鼠出迷宫
    //1.findway方法就是专门来找出迷宫的路径
    //2.如果找到返回true否则就返回false
    //3.map就是二维数组,即表示迷宫
    //4.方法中定义的i j 就是老鼠的位置 ,初始化的位置为[1][1]
    //5.由于是递归找路,因此要确定递归的终止条件,因此需要规定map数组的各个位置的含义
    //0表示可以走 1表示障碍物 2表示可以走 3表示走过,但是走不通是思路
    //6.当6,5的位置变成2了.就说明找到通路了,否则就继续找
    //7.定义一个寻路的策略,比如先走下面,走不通走下面,走不通走右边,走不通走上路,走不通走左路
    public boolean findway(int[][] map,int i,int j){
        if (map[6][5] == 2){
            //此时说明已经找到路了
            System.out.println("已找寻到通路,终止寻路!");
            return true;
        }else{
            if (map[i][j]==0){
                //说明这个位置可以走
                //假定可以走通
                map[i][j] = 2;
                //使用找路的策略进行测试,来确定这个位置是否真的可以走通
                if (findway(map,i+1,j)){
                    //先尝试走下面
                    return true;//走通返回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]=2是错的
                    map[i][j] = 3;
                    return false;
​
                }
​
            }else {
                //不为0就是1 2 3三种情况
                return false;
            }
​
        }
​
    }
}

分析一下这个代码

int [][] map = new int[8][7];
        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;

这里是在主类中设置一个障碍物 ,我们在迷宫的代码中定义的障碍物是 ,数组的数字1 ,因此我们只需要将二维数组的数组元素位置赋值为1即可 ,第一个循环是给 上下两行赋值 ,第二个循环是给左右两列赋值 ,最终的效果就是让迷宫形成一个外围 ,之后由于不是连续设置 ,因此就单独给特定的元素位置设置障碍物

//使用findway方法测试寻路功能
        Tmouse t1 = new Tmouse();
        t1.findway(map,1,1);
        //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();
        }

这里开始实例化我们编写好的寻路类方法 ,之后设置我们的起始位置为 t1.findway(map,1,1); ,由于我们递归的时候更改的是引用类型的对象 ,因此会影响到main栈 ,因此我们只需要打印迷宫数组本身就可以直接看到 ,寻路之后的结果

class Tmouse

定义一个类Tmouse

public boolean findway(int[][] map,int i,int j)

创建一个方法 ,方法名为findway ,返回的类型为布尔类型(即 true , false) ,传参的类型为数组 ,也就是我们传参的迷宫本体 以及对应的位置

if (map[6][5] == 2){
            //此时说明已经找到路了
            System.out.println("已找寻到通路,终止寻路!");
            return true;
        }

设置寻路终点位置 ,也就是位于元素map[6][5]的位置 ,打印找到路的信息 ,返回布尔值 true

else{
    if (map[i][j]==0){
    //说明这个位置可以走
    //假定可以走通
    map[i][j] = 2;
    //使用找路的策略进行测试,来确定这个位置是否真的可以走通
    if (findway(map,i+1,j)){
    //先尝试走下面
    return true;//走通返回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]=2是错的
        map[i][j] = 3;
        return false;
}

如果符合当前位置的数字为0的条件 ,就开始执行我们的主要的移动操作的代码 ,也就是对某一个方向进行移动 ,移动到不能移动为止 ,首先我们在起始位置为0 ,走过之后将这个位置改写为2 , 之后开始判断方法findway(map,i+1,j)也就是先进行移动更改当前的位置(map ,i + 1 , j)移动之后将这个位置传参到方法findway中去 ,之后按照方法进行判断没有问题之后再进行移动(还是按照原先的方式移动 ) ,如果出现了问题 ,例如遇到了障碍物或者这条路走过 ,就会返回false ,此时就会进行下面的判断也就是 else if (findway(map,i,j+1)) 以此类推一直到重点坐标为map[6][5]为止 ,同时我们的移动顺序分别是 下 -> 右 ->上 -> 左 ,同时我们也可以通过更改位置来改变完成到重点的路线 ,例如按照 右 -> 下 -> 上 ->左 的方式 ,走完最后一个判断方向还是没有到达重点的话 ,就触发了 else条件 ,也就是我们走的路线一开始就走错了 ,返回false之后将当前的位置更改为3 ,重新走按照规定的路线走一遍 ,此时迷宫地图走过的地方数字就会改变因此也不必担心老路重走

 

else {
                //不为0就是1 2 3三种情况
                return false;
            }

如果没有到终点的话 ,进入一个分支判断 ,也就是判断当前的位置 map[i][j] ,如果为0 ,就说明这个位置没有走过 ,因此可以往这个位置移动(也就是我们上面移动的具体递归代码)

如果不为 0 ,即表示这个位置存在三种情况分别用 数字 1 ,2 ,3表示 ,如果是数字1则表示这个位置是障碍 ,不能往障碍物的地方移动 ,如果是数字2 ,说明这个位置已经走过了 ,如果是数字3的话 ,就表示之前在这个位置走过并且这个位置是错误的

而以上判断的 1 2 3三种情况 ,总结都是不能走 ,因此这里我们直接写一个false返回即可

 

测试回溯现象

所谓回溯现象就是指重新从开头的位置继续寻路 ,具体一天就是将原本的图中布置一个障碍物 ,使得小球按照下右上左的方向寻路的时候触发这样的现象

更加具体一点就是 : 小球从原先的位置向下走走到障碍物转换位置向右, 向右一步都无法移动就又遇到障碍物了 ,因此小球放弃往右将方向更改为向上 ,但是向上就会触发之前的位置已经走过了(也就是要走的位置为2) ,此时小球就会更改为向左 ,但是向左仍然不能移动 ,左边还是障碍物(也就是数字1) ,因此出发了所有寻路机制的小球就会将目前的死路位置数字更改为3 ,也就是这个位置没有方法抵达终点的含义 ,同时返回到起点 ,再从走的方向的下一个方向开始走 ,也就是回溯的原理

 

 

 

<由于设置图片比较麻烦 ,这一段设置图片的话会更加容易理解, 具体一点就是 ,将原先的障碍物摆放不变将map[2][2]的位置更改为障碍物(也就是1)>

 

如何计算出最短路径<扩展提问>

穷举法 ,我的想法就是遍历多次一直遍历完所有的遍历 ,之后在通过记录每次遍历之后得到的二维数组中的2的数量 ,来判断二维数组中2最少的寻路方法

 

首先一直寻路的话 ,可能需要写一个带判断的循环 ,循环条件是寻路到再次寻路会和之前的重复 ,因此还需要记录每次寻路