递归概念

递归概述:以编程的角度来看，递归指的是方法定义中调用方法本身的现象

递归解决问题的思路: 1、把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解 2、递归策略只需少量的程序就可描述出阶梯过程所需要的多次重复计算

递归解决问题要找到两个内容: 1、递归出口:否则会出现内存溢出。即需要让这个递归停止的条件 2、递归规则:与原问题相似的规模较小的问题

提示:每次递归，都是在给栈压数据，压得越多，计算速度越慢，足够多或者没有出口，就会爆栈，即控制台出现报错

递归概念的练习

xxxxxxxxxx
package ch18;

public class a_5_1测试 {

    public static void main(String[] args) {

        //回顾不死神兔问题，求第20个月兔子的对数
        //每个月的兔子对数:1,1,2,3,5,8,...
        int[] arr = new int[20];

        arr[0] = 1;
        arr[1] = 1;

        for (int i=2; i<arr.length; i++){
            arr[i] = arr[i-1]+arr[i-2];
        }
        //普通的解决问题写法
        System.out.println(arr[19]);

        //如何使用递归来解决
        //调用下面写好的方法
        System.out.println(f(20));//直接写会报StackOverflowError错误，即当堆栈溢出发生时抛出一个应用程序递归太深
        //上面那行报错的原因是下面我们写的递归方法没有写停止条件，会一直递归下去，导致内存溢出
        //解决方法:在下面的方法里面加一个if else判断
    }
    
//-----------------------------------------------------------------------------------------------------------------

    //如何使用递归来解决。首先就是要定义一个方法
    //定义一个方法f(n),表示第n个月的兔子对数
    //那么，第n-1个月的兔子对数就表示为f(n-1)
    //同理，第n-2个月的兔子对数就表示为f(n-2)
    //具体操作如下
    public static int f(int n){
        if (n==1 || n==2){//当是第一个月或第二个月时
            return 1;
        } else{ //从第三个月开始才是符合我们递归规则的
            return f(n-1)+f(n-2);
        }

    }
}

递归求阶乘

案例:递归求阶乘 需求:用递归求5的阶乘，并把结果输出在控制台

分析: 1、阶乘的概念:一个正整数的阶乘是所有小于及等于该数的正整数的积，自然数n的阶乘写作n! 举例5的阶乘为5!=54321 2、递归出口:1!=1 3、递归规则:n!=n*(n-1)!

思路: 1、定义一个方法，用于递归求阶乘，参数为一个int类型的变量 2、在方法内部判断该变量的值是否是1 3、如果是，就返回1。如果不是，就返回n*(n-1)! 4、调用方法 5、输出结果

递归求阶乘的练习

package ch18;

public class a_6_1测试 {

    public static void main(String[] args) {
        //4、调用方法
        int result = jc(5);
        //5、输出结果
        System.out.println("5的阶乘是: "+result);
    }

    //1、定义一个方法，用于递归求阶乘，参数为一个int类型的变量
    public static int jc(int n){
        //2、在方法内部判断该变量的值是否是1
        if (n==1){
            //3、如果是1，就返回1
            return 1;
        } else{
            //3、如果不是1，就返回n*(n-1)!。n*(n-1)!的意思是'n'乘以'(n-1)的阶乘'
            return n*jc(n-1);
        }
        
    }
}

使用递归来遍历目录

案例:遍历目录 需求:给定一个路径D:\huanf\java\src，请通过递归完成遍历该目录下的所有内容，并把所有文件的绝对路径输出在控制台

思路: 1、根据给定的路径创建一个File对象 2、定义一个方法，用于获取给定目录下的所有内容，参数为第1步创建的File对象 3、获取给定的File目录下所有的文件或目录的File数组 4、遍历该File数组，得到每一个File对象 5、判断该File对象是否是目录 (1)是:递归调用 (2)不是:获取绝对路径输出在控制台 6、调用方法

使用递归来遍历目录的练习

xxxxxxxxxx
package ch18;

import java.io.File;

public class a_7_1测试 {

    public static void main(String[] args) {
        //1、根据给定的路径创建一个File对象
        File srcFile = new File("D:\\huanf_基础\\java\\src");
        //6、调用方法
        getAllFilePath(srcFile);
    }

    //2、定义一个方法，用于获取给定目录下的所有内容，参数为第1步创建的File对象
    public static void getAllFilePath(File srcFile){
        //3、获取给定的File目录下所有的文件或目录的File数组
        File[] fileArray = srcFile.listFiles();
        //4、遍历该File数组，得到每一个File对象
        if (fileArray != null){
            for (File file : fileArray){
                //5、判断该File对象是否是目录
                if (file.isDirectory()){//(1)是:递归调用
                    getAllFilePath(file);
                } else{//(2)不是:获取绝对路径输出在控制台
                    System.out.println(file.getAbsolutePath());
                }
            }
        }
    }
}