递归技术
需求：扫描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；packagecn.xuexi.digui.demo;/*
*练习1：需求：计算1~5的和值，不许使用循环。
*递归演示
*/publicclassDiGuiDemo{publicstaticvoidmain(String[]args){//调用自定义函数求1~5之间的和值
intsum=add(5);
System.out.println(sum);
}/*
*自定义函数求1~5之间的和值
*5+4+3+2+1
*/
publicstaticintadd(intn)
{/*
*判断n是否大于1
*/
if(n>1)
{//这里的add函数调用了函数自己本身的做法就是函数的递归调用
returnn+add(n-1);
}//返回1作为递归的结束条件
return1;
}
}
上述代码图解如下图所示：
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阶乘的值；packagecn.xuexi.digui.demo;/*
*练习2：需求：求5的阶乘！！
*方式1：5!=5*4*3*2*1=120
*/publicclassDiGuiDemo2{publicstaticvoidmain(String[]args){intresult=jc(5);//输出阶乘后的结果
System.out.println(result);//120
}//使用方式一来求5的阶乘
publicstaticintjc(intn){//定义一个变量来接收阶乘后的结果
intresult=1;for(inti=2;i<=n;i++)
{
result=result*i;
}returnresult;
}
}
方式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);packagecn.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)return1;
*/publicclassDiGuiDemo3{publicstaticvoidmain(String[]args){//调用函数求5的阶乘
intresult=jc2(5);
System.out.println(result);//120
}//自定义函数求5的阶乘
publicstaticintjc2(intn){//结束条件
if(n<=1)
{return1;
}returnn*jc2(n-1);
}
}
上述代码内存图解如下所示：
2.png
递归注意事项
1)递归必须有结束条件，否则栈内存会溢出，称为死递归！栈炸了。
3.png
栈内存溢出报的异常如下所示：
4.png
2)递归次数不能太多，否则栈溢出。炸了
5.png
栈内存溢出报的异常如下所示：
6.png
3)构造函数不能递归，内存溢出，编译直接报错。
7.png
总结：递归容器容易导致内存溢出。即使递归调用中有结束条件，但是如果递归的次数太多，也会发生内存溢出。
所以在开发中使用函数的递归调用时需谨慎。
递归练习
斐波那契数列或者叫做黄金分割数列或者叫做兔子数列：
不死神兔问题：有1对兔子，从出生的第3个月开始，每个月都生1对兔子，假如兔子都不死，问第n个月有几对兔子。
斐波那契数列思想的图解如下图所示：
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),并将兔子的对数返回给调用者；packagecn.xuexi.digui.demo;/*
*递归练习，斐波那契数列
*月份：12345678910.。。。
*兔子对数：11235813213455.。。。
*求第n个月的兔子对数
*/publicclassDiGuiDemo4{publicstaticvoidmain(String[]args){//定义一个函数计算兔子的对数
intnum=countRabbits(6);//6表示月份
//输出第n个月兔子的对数
System.out.println(num);
}//自定义函数统计第n个月兔子的对数
publicstaticintcountRabbits(intn)//n表示月份
{//结束条件
if(n<=2)
{return1;
}//规律
returncountRabbits(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,如果是输出文件所属的绝对路径；packagecn.xuexi.file.test;importjava.io.File;/*
*需求：扫描D:\\test所有子文件及子子文件下的.jpg文件，输出其绝对路径。
*思路：
*A:创建父目录
*B:调用函数查找文件或者文件夹
*C:通过父目录对象调用函数获取所有儿子的File数组
*D:循环遍历所有的儿子,dir表示父目录D:\\test的每一个儿子
*a:判断获取的儿子dir是否是文件夹如果是执行步骤B
*b:不是，判断后缀名是否是.jpg,是，输出绝对路径
*
*我们发现：B到D的过程是不断重复。我们可以封装成递归的函数。
*/publicclassFileTest1{publicstaticvoidmain(String[]args){//封装父目录的对象
Fileparent=newFile("D:\\test");//调用函数查找文件或者文件夹
scanFolderAndFile(parent);
}//自定义函数扫描文件或者文件夹
publicstaticvoidscanFolderAndFile(Fileparent){//通过父目录对象调用函数获取所有儿子的File数组
File[]dirs=parent.listFiles();//循环遍历所有的儿子,dir表示父目录D:\\test的每一个儿子
for(Filedir: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()函数，如果是文件，则抛异常。
说明：除了上述三个问题，其他代码和上述代码一样。
代码如下：//自定义函数扫描文件夹
publicstaticvoidscanFolderAndFile(Fileparent)
{//判断parent是否为null
if(parent==null)
{thrownewRuntimeException("不能传递null");
}//判断文件夹是否存在
if(!parent.exists())
{thrownewRuntimeException("文件夹不存在");
}//传递的是文件夹，不能是文件
if(parent.isFile())
{thrownewRuntimeException("只能是文件夹");
}//获取父目录下面的所有儿子
File[]files=parent.listFiles();//遍历上述数组
for(Filefile:files){/*
*如果file对象中封装的是文件夹，那么可以把此文件夹当成父类
*在扫描其下面的儿子
*/
if(file.isDirectory())
{//说明获得的是文件夹再次回到scanFolderAndFile()函数处执行该函数
scanFolderAndFile(file);
}else
{/*
*说明file中封装的是文件
*获得文件名字，然后判断后缀名是否是.jpg
*如果是，则获取绝对路径
*/
booleanboo=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,如果是输出文件所属的绝对路径；packagecn.xuexi.file.test;importjava.io.File;importjava.io.FileFilter;/*
*思路：
A：创建父目录的File对象
B：获取父目录下的符合条件的儿子
条件是什么？
可以是文件夹也可以是.jpg文件
C：循环遍历，取出每个儿子
取出的儿子有两种情况：文件夹、.jpg文件
D：判断是否是文件夹
是：回到B
否：打印
B到D封装成递归函数
*/publicclassFileTest3{publicstaticvoidmain(String[]args){//封装父目录的对象
Fileparent=newFile("D:\\test");//调用函数查找文件或者文件夹
scanFolderAndFile(parent);
}publicstaticvoidscanFolderAndFile(Fileparent){//获取父目录下的符合条件的儿子这里需要使用过滤器
File[]files=parent.listFiles(newFileFilter(){publicbooleanaccept(Filepathname){//条件是文件夹或者后缀名是.jpg的文件
returnpathname.isDirectory()||pathname.getName().endsWith(".jpg");
}
});//循环遍历，取出每个儿子
for(Filefile:files){//判断是否是文件夹
if(file.isDirectory())
{//递归调用函数
scanFolderAndFile(file);
}else
{
System.out.println(file.getAbsolutePath());
}
}
}
}
来源：/p/73ae186721db
