Java的递归、如何与流相结合

╰半夏微凉° 2021-09-12 08:38 242阅读 0赞

## 递归技术 ##

需求：扫描D:\\test所有子文件夹及子子文件夹下的.jpg文件。  
我们如果用循环来做这件事，我们不知道循环的结束条件，也不知道到底有多少层，所以比较麻烦。  
我们可以用一种新的思想：递归。  
递归举例：  
从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：  
从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：  
从前有一座山，山里有座庙，庙里有个老和尚，老和尚在给小和尚讲故事：  
。。。。。。。

故事如何才能结束：小和尚还俗了。庙塌了。山崩了。

Java中的递归：  
在方法的函数体中又调用了方法自己本身。  
**递归调用的细节**：必须要求递归中有可以让函数调用的结束条件。否则函数一直调用，就会导致内存溢出。

### 递归演示 ###

**练习1：需求：计算1~5的和值，不许使用循环。**  
分析和步骤：  
1）定义一个DiGuiDemo测试类；  
2）在这个类中的main函数中调用自定义函数，5作为函数的参数，使用一个变量sum来接收返回的和值，并输出和值sum；  
3）自定义add()函数接收传递的参数5；  
4）在自定义函数中书写if语句判断i是否大于1，如果大于1，则使用return返回i+add(i-1);  
5）否则i<=1时，返回1；

package cn.xuexi.digui.demo;
    /*
     * 练习1：需求：计算1~5的和值，不许使用循环。
     * 递归演示
     */
    public class DiGuiDemo {
    
        public static void main(String[] args) {
            //调用自定义函数求1~5之间的和值
            int sum=add(5);
            System.out.println(sum);
        }
        /*
         * 自定义函数求1~5之间的和值
         * 5+4+3+2+1
         */
        public static int add(int n) 
        {
            /*
             * 判断n是否大于1
             */
            if(n>1)
            {
                //这里的add函数调用了函数自己本身的做法就是函数的递归调用
                return n+add(n-1);
            }
            //返回1作为递归的结束条件
            return 1;
        }
    }

上述代码图解如下图所示：

![2400330-b7686a462c2e5cb7.png][]

1.png

**练习2：需求：求5的阶乘！！**  
分析：

普及一下数学知识：  
方式1：5! = 5 \* 4 \* 3 \* 2 \* 1 = 120;

方式1 循环方式：  
代码如下所示：  
步骤：  
1）定义一个DiGuiDemo2测试类；  
2）在这个类中的main函数中调用自定义函数jc()，5作为函数的参数，使用一个变量result来接收返回的阶乘的值，并输出结果result；  
3）自定义jc()函数接收传递的参数5；  
4）在自定义函数中定义一个变量result=1，使用for循环来实现方式1求阶乘的结果，并返回result阶乘的值；

package cn.xuexi.digui.demo;
    /*
     * 练习2：需求：求5的阶乘！！
     * 方式1：5!=5*4*3*2*1=120
     */
    public class DiGuiDemo2 {
        public static void main(String[] args) {
            int result=jc(5);
            //输出阶乘后的结果
            System.out.println(result);//120
        }
        //使用方式一来求5的阶乘
        public static int jc(int n) {
            //定义 一个变量来接收阶乘后的结果
            int result =1;
            for (int i = 2; i <= n; i++) 
            {
                result=result*i;
            }
            return result;
        }
    }

方式2：使用递归思想来完成

5! = 5 * 4!
               4! = 4 * 3!
                        3! = 3 * 2!
                                 2! = 2 * 1!
                                          1! = 1*0!

找规律：n! = n \* (n-1)!  
补充：0!等于1  
结束条件：if(n <= 1) return 1;

方式2 递归方式：  
代码如下所示：  
步骤：  
1）定义一个DiGuiDemo3测试类；  
2）在这个类中的main函数中调用自定义函数jc2()，5作为函数的参数，使用一个变量result来接收返回的阶乘的值，并输出结果result；  
3）自定义jc2()函数接收传递的参数5；  
4）在自定义函数中书写if语句判断n是否小于等于1，如果小于等于1，则使用return返回1;  
5）否则n>1时，使用return返回n \* jc2(n - 1);

package cn.xuexi.digui.demo;
    /*
     * 方式2：使用递归思想来解决5的阶乘
     *方式一： 5!=5*4*3*2*1;
     *方式二：5!=5*4!
     *            4!=4*3!
     *                  3!=3*2!
     *                        2!=2*1!
     *                              1!=1*0!
     *找规律：n!=n*(n-1)!
     *找结束条件:
     *  if(n<=1) return 1;
     */
    public class DiGuiDemo3 {
        public static void main(String[] args) {
            // 调用函数求5的阶乘
            int result=jc2(5);
            System.out.println(result);//120
        }
        //自定义函数求5的阶乘
        public static int jc2(int n) {
            // 结束条件
            if(n<=1)
            {
                return 1;
            }
            return n*jc2(n-1);
        }
    }

上述代码内存图解如下所示：

![2400330-886469840065ae8a.png][]

2.png

### 递归注意事项 ###

1）递归必须有结束条件，否则栈内存会溢出，称为死递归！栈炸了。

![2400330-5d838678802f8a2a.png][]

3.png

栈内存溢出报的异常如下所示：

![2400330-dc1c0d7e8d3fda7f.png][]

4.png

2）递归次数不能太多，否则栈溢出。炸了

![2400330-d101b2473148cf5b.png][]

5.png

栈内存溢出报的异常如下所示：

![2400330-c34415e6832eaff0.png][]

6.png

3）构造函数不能递归，内存溢出，编译直接报错。

![2400330-b5fcdec0ebee775f.png][]

7.png

**总结：递归容器容易导致内存溢出。即使递归调用中有结束条件，但是如果递归的次数太多，也会发生内存溢出。**

**所以在开发中使用函数的递归调用时需谨慎。**

### 递归练习 ###

斐波那契数列或者叫做黄金分割数列或者叫做兔子数列：  
不死神兔问题：有1对兔子，从出生的第3个月开始，每个月都生1对兔子，假如兔子都不死，问第n个月有几对兔子。  
斐波那契数列思想的图解如下图所示：

![2400330-8653b78da2d04219.png][]

8.png

斐波那契数列思想如下所示：  
找规律：  
月份(n)： 1 2 3 4 5 6 7 8 9 10 .....  
兔子对数(f)： 1 1 2 3 5 8 13 21 34 55 .....  
f(n) = f(n-1) + f(n-2)

找出口：  
if(n <= 2) return 1;

代码实现如下所示：  
分析和步骤：  
1）定义一个测试类DiguiDemo4 ；  
2）在DiguiDemo4类中调用自定义函数countRabbits(),指定月份作为参数，就是想看第几个月有多少对兔子，使用一个整数变量接收返回来的兔子的对数num，输出打印结果；  
3）自定义函数countRabbits()根据用户指定的月份输出对应月份的兔子的对数；  
4）使用判断结构判断月份n是否小于等于2，如果是返回1对；  
5）如果月份大于2，分别递归调用函数countRabbits(n-1)+countRabbits(n-2),并将兔子的对数返回给调用者；

package cn.xuexi.digui.demo;
    /*
     * 递归练习，斐波那契数列 
     *      月份 ：    1   2   3   4   5   6   7   8   9   10.。。。
     * 兔子对数：      1   1    2   3    5   8   13   21  34    55.。。。
     * 求第n个月的兔子对数
     */
    public class DiGuiDemo4 {
        public static void main(String[] args) {
            // 定义一个函数计算兔子的对数
            int num=countRabbits(6);//6表示月份
            //输出第n个月兔子的对数
            System.out.println(num);
        }
        //自定义函数统计第n个月兔子的对数  
        public static int countRabbits(int n) //n表示月份
        {
            // 结束条件
            if(n<=2)
            {
                return 1;
            }
            //规律
            return countRabbits(n-1)+countRabbits(n-2);
        }
    }

### 综合练习 ###

练习1：扫描D:\\test所有子文件夹及子子文件夹下的.jpg文件，输出其绝对路径  
需求：扫描D:\\test所有子文件夹及子子文件夹下的.jpg文件，输出其绝对路径。  
分析：  
首先我们可以拿到D:\\test下的所有儿子，我们判断儿子是不是文件夹，如果是，再次扫描儿子的文件夹，然后获取儿子下面的所有子文件和子文件夹，即就是D:\\test的孙子，然后我们再判断孙子是不是文件夹等等，以此类推，最后我们输出其绝对路径；

思路：  
A：封装父目录的File对象；  
B：获取父目录下的所有儿子的File数组；  
C：循环遍历，获取每个儿子；  
D：判断是否是文件夹  
是：回到步骤B 继续获取孙子  
否：判断是否是.jpg 结束递归的条件  
是：打印  
否：不管  
我们发现：B到D的过程是不断重复。我们可以封装成递归的函数。

步骤：  
1）创建测试类FileTest1；  
2）在FileTest1类的main函数中封装父目录D:\\test的对象parent；  
3）调用递归扫描的函数scanFolders(parent);  
4）自定义函数scanFolders()，使用父目录对象parent调用listFiles()函数获得父目录下所有儿子的File数组files;  
5）循环遍历，获取每个儿子对象file；  
6）使用file对象调用isDirectory()函数判断是否是文件夹；  
7）如果是文件夹，则递归调用scanFolders(file)函数;  
8）如果不是文件夹，肯定是文件，使用file对象调用getName()函数获得文件的全名，调用endsWith()函数判断后缀名是否是.jpg,如果是输出文件所属的绝对路径；

package cn.xuexi.file.test;
    import java.io.File;
    /*
     * 需求：扫描D:\\test所有子文件及子子文件下的.jpg文件，输出其绝对路径。
     * 思路：
     * A:创建父目录
     * B:调用函数查找文件或者文件夹
     * C:通过父目录对象调用函数获取所有儿子的File数组
     * D:循环遍历所有的儿子,dir表示父目录D:\\test的每一个儿子
     *      a:判断获取的儿子dir是否是文件夹 如果是 执行步骤B
     *      b:不是，判断后缀名是否是.jpg,是，输出绝对路径
     * 
     * 我们发现：B到D的过程是不断重复。我们可以封装成递归的函数。
     */
    public class FileTest1 {
        public static void main(String[] args) {
            //封装父目录的对象
            File parent = new File("D:\\test");
            //调用函数查找文件或者文件夹
            scanFolderAndFile(parent);
        }
        //自定义函数扫描文件或者文件夹
        public static void scanFolderAndFile(File parent) {
            //通过父目录对象调用函数获取所有儿子的File数组
            File[] dirs = parent.listFiles();
            //循环遍历所有的儿子,dir表示父目录D:\\test的每一个儿子
            for (File dir : dirs) {
                /*
                 * 判断获取的儿子dir是否是文件夹
                 * 如果是文件夹，那么继续扫描或者查找儿子下面的所有文件或者文件夹
                 * 以此类推
                 * 如果不是文件夹，那么肯定是文件，判断后缀名是否是.jpg
                 *      如果是.jpg 则输出其绝对路径
                 */
                if(dir.isDirectory())
                {
                    //说明是文件夹  继续找儿子下面的文件或者文件夹 执行扫描函数
                    scanFolderAndFile(dir);
                }else
                {
                    /*
                     * 说明不是文件夹，是文件,我们判断是否是.jpg
                     * dir.getName()表示获取文件的名字  mm.jpg
                     */
                    if(dir.getName().endsWith(".jpg"))
                    {
                        //说明文件的后缀名是.jpg 输出其绝对路径
                        System.out.println(dir.getAbsolutePath());
                    }
                }
            }
        }
    }

带健壮性的代码：

上述代码不安全，  
1）比如在调用scanFolders(parent)函数时，如果parent变成null，那么scanFolders(File parent) 接收参数时，parent也为null，就会报空指针异常；  
判断parent是否为null，如果为null就抛异常；  
2）比如创建父目录对象时，指定的父目录在计算机中不存在，那么抛异常；  
使用parent对象调用exit()函数判断创建的文件夹是否存在，如果不存在，则抛异常。  
3）比如创建父目录对象时，指定的父目录是文件，那么抛异常；  
使用parent对象调用isFile()函数，如果是文件，则抛异常。

说明：除了上述三个问题，其他代码和上述代码一样。

代码如下：

//自定义函数扫描文件夹
        public static void scanFolderAndFile(File parent) 
        {
            //判断parent是否为null
            if(parent==null)
            {
                throw new RuntimeException("不能传递null");
            }
            //判断文件夹是否存在
            if(!parent.exists())
            {
                throw new RuntimeException("文件夹不存在");
            }
            //传递的是文件夹，不能是文件
            if(parent.isFile())
            {
                throw new RuntimeException("只能是文件夹");
            }
            // 获取父目录下面的所有儿子
            File[] files = parent.listFiles();
            //遍历上述数组
            for (File file : files) {
                /*
                 * 如果file对象中封装的是文件夹，那么可以把此文件夹当成父类
                 * 在扫描其下面的儿子
                 */
                if(file.isDirectory())
                {
                    //说明获得的是文件夹 再次回到scanFolderAndFile()函数处执行该函数
                    scanFolderAndFile(file);
                }else
                {
                    /*
                     * 说明file中封装的是文件
                     * 获得文件名字，然后判断后缀名是否是.jpg
                     * 如果是，则获取绝对路径
                     */
                    boolean boo = file.getName().endsWith(".jpg");
                    if(boo)
                    {
                        //说明后缀名是.jpg的文件 输出绝对路径
                        System.out.println(file.getAbsolutePath());
                    }
                }
            }
        }

练习2：使用过滤器实现练习  
演示：需求：扫描D:\\test所有子文件夹及子子文件夹下的.jpg文件，输出其绝对路径。  
要求：使用过滤器实现。  
思路：  
A：创建父目录的File对象  
B：获取父目录下的符合条件的儿子  
条件是什么？  
可以是文件夹 也可以是.jpg文件  
C：循环遍历，取出每个儿子  
取出的儿子有两种情况：文件夹、.jpg文件  
D：判断是否是文件夹  
是：回到B  
否：打印  
B到D封装成递归函数

步骤：  
1）创建测试类FileTest2；  
2）在FileTest2类的main函数中封装父目录D:\\test的对象parent；  
3）调用递归扫描的函数scanFolders(parent);  
4）自定义函数scanFolders()，使用父目录对象parent调用listFiles(**new** FileFilter())函数获得父目录下所有儿子的File数组files;  
5）使用过滤器FileFilter接口的匿名内部类作为listFiles()函数的参数，匿名内部类实现accept函数；  
6在accept函数体中使用父目录的儿子对象调用isDirectory()函数和getName().endsWith(".jpg")函数来判断父目录 的儿子是否是文件夹或者后缀名是.jpg的文件；  
7）使用判断结构判断files数组是否有文件或者文件夹；  
8）如果有，则循环遍历数组files；  
9）使用file对象调用isDirectory()函数判断是否是文件夹；  
10）如果是文件夹，则递归调用scanFolders(file)函数;  
11）如果不是文件夹，肯定是文件，使用file对象调用getName()函数获得文件的全名，调用endsWith()函数判断后缀名是否是.jpg,如果是输出文件所属的绝对路径；

package cn.xuexi.file.test;
    import java.io.File;
    import java.io.FileFilter;
    /*
     * 思路：
     A：创建父目录的File对象
     B：获取父目录下的符合条件的儿子
     条件是什么？
     可以是文件夹 也可以是.jpg文件
     C：循环遍历，取出每个儿子
     取出的儿子有两种情况：文件夹、.jpg文件
     D：判断是否是文件夹
     是：回到B
     否：打印
     B到D封装成递归函数
     */
    public class FileTest3 {
        public static void main(String[] args) {
            // 封装父目录的对象
            File parent = new File("D:\\test");
            // 调用函数查找文件或者文件夹
            scanFolderAndFile(parent);
        }
        public static void scanFolderAndFile(File parent) {
            // 获取父目录下的符合条件的儿子 这里需要使用过滤器
            File[] files=parent.listFiles(new FileFilter() {
                public boolean accept(File pathname) {
                    // 条件是文件夹或者后缀名是.jpg的文件
                    return pathname.isDirectory() || pathname.getName().endsWith(".jpg");
                }
            });
            //循环遍历，取出每个儿子
            for (File file : files) {
    //          判断是否是文件夹
                if(file.isDirectory())
                {
                    //递归调用函数
                    scanFolderAndFile(file);
                }else
                {
                    System.out.println(file.getAbsolutePath());
                }
            }
        }
    }

[2400330-b7686a462c2e5cb7.png]: /images/20210809/a64e790b93084040b079b6d1245b5381.png
[2400330-886469840065ae8a.png]: /images/20210809/a61227ec8d0a4f8eb47452a46af9b879.png
[2400330-5d838678802f8a2a.png]: /images/20210809/08c1f2a12a7d48cab56a9f99862b33f9.png
[2400330-dc1c0d7e8d3fda7f.png]: /images/20210809/b28df3cb090346cba166d98789460b60.png
[2400330-d101b2473148cf5b.png]: /images/20210809/2a2da9c2fccb4c3c978660ad8757a6c6.png
[2400330-c34415e6832eaff0.png]: /images/20210809/df9fab198814420ba0da151d4a5fffc2.png
[2400330-b5fcdec0ebee775f.png]: /images/20210809/0da77efabcd440e78dae97643756ef64.png
[2400330-8653b78da2d04219.png]: /images/20210809/d233b40e00b14637a1d4160ed203144a.png