递归
是指某个方法在自己的方法体内直接或间接的调用自己。作用和嵌套循环有些类似,很多地方可以互换使用;
假设E盘下有文件夹A,现在要求扫描文件A下面的所有文件;该文件夹的树型结构图如下图所示
实例一:使用for循环实现package recursion;
import java.io.File;
import java.util.ArrayList;
import java.util.List;
/**
* 演示使用循环扫描某一目录下的所有文件,含子文件下的所有文件
* @author 学霸联盟 - 赵灿
*/
public class ForScanFile {
public static void main(String[] args) {
ForScanFile fs = new ForScanFile();
// 要扫描的文件夹
File initFile = new File("E:\\A");
//用于存储扫描结果的集合
List<File> fileList = new ArrayList<File>();
//调用scan方法
fs.scan(initFile, fileList);
//循环输出扫描结果
for (File file : fileList) {
//输出文件全名
System.out.println(file.getPath());
}
}
/**
* 扫描文件的方法
* @param file 被扫描的目录
* @param fileList 存储扫描结果的集合
*/
public void scan(File file, List<File> fileList) {
// 用于临时存放传入文件对象file,及其所有子文件夹和文件的集合
List<File> tempList = new ArrayList<File>();
// 先将file添加到临时集合中
tempList.add(file);
//注意:此处不能使用增强for循环迭代,否则会出现ConcurrentModificationException
//因为一个集合不能同时被迭代和修改
for (int i = 0; i < tempList.size(); i++) {
//获取集合中的元素
File f = tempList.get(i);
// 注意:这里判断使用的是集合中取出的File对象f,而不是参数file
if (f != null && f.exists() && fileList != null) {
// 如果这个file是文件
if (f.isFile()) {
// 将这个文件加入到结果集合中
fileList.add(f);
} else {
// 如果file对象不是文件,就说明是文件夹
// 首先要获取这个文件夹下所有文件对象的数组
File[] files = f.listFiles();
// 判断这个数组是否为null
if (files != null) {
// 将获得的数组files中的每一个值都加入到临时集合中
// 这是保证外层循环能够扫描传入的file下整个结构的关键代码
for (File nextFile : files) {
// 将所有的文件对象加入临时集合
tempList.add(nextFile);
}
}
}
}
}
}
}
实例二:改用递归后的实现代码package recursion;import java.io.File;import java.util.ArrayList;import java.util.List;/** * 演示递归算法 * 使用递归扫描某文件夹下的所有文件(包含子文件夹下的文件) * 对于这个需求使用循环很难实现 * 因为程序运行之前,并不知道文件夹下有多少层 * 所以就无法确定要嵌套多少层的循环 * @author 学霸联盟 - 赵灿 */public class RecursionDemo { public static void main(String[] args) { RecursionDemo rd = new RecursionDemo(); // 要扫描的文件夹 File initFile = new File("E:\\A"); //用于存储扫描结果的集合 List<File> fileList = new ArrayList<File>(); //调用scan方法,执行完此句代码,会在栈内存中创建一个scan方法的栈帧 rd.scan(initFile, fileList); //循环输出扫描结果 for (File file : fileList) { //输出文件全名 System.out.println(file.getPath()); } } /** * 扫描文件的方法 * @param file 被扫描的目录 * @param fileList 存储扫描结果 */ public void scan(File file, List<File> fileList) { // 首先通过判断保证这个file对象存在 if (file != null && file.exists() && fileList != null) { // 如果这个file是文件 if (file.isFile()) { // 将这个文件加入到结果集合中 fileList.add(file); } else { // 如果file对象不是文件,就说明是文件夹 //首先要获取文件夹下所有文件的数组 File[] files = file.listFiles(); //判断这个数组是否为null if(files != null){ // 循环递归调用自己,并把文件夹对象file和存储文件的集合传入 for(File f:files){ //执行完此句代码,会重新在栈内存中创建一个新的scan方法的栈帧 //执行一次,就会创建一个新的栈帧。所以,这里有可能会出现栈内存用尽的错误 scan(f, fileList); } } } } }}
分别使用循环和递归遍历这个属性图的顺序如下
1、for循环遍历文件夹A的步骤是,先将A加入临时集合tempList,然后开始遍历tempList;在遍历的过程中,将B1、B2、B3加入到tempList中;当遍历tempList的循环结构进入下一次循环时,取出的对象就是B1,加入tempList的顺序是C1、C2、C3,然后取出的对象时B2,加入tempList的是C4,然后是D1、D2、D3这样的顺序
加入tempList的顺序,也就是遍历的顺序。A 、B1、B2、B3、C1、C2、 C3、C4、D1、D2、D3
2、而递归的顺序是A、B1、C1、D1、C2、D2、D3、C3、B2、C4、B3
注意:File对象可能是目录(文件夹),也可能是文件。
递归和循环的区别
嵌套循环 | 递归 | |
方法栈帧 | 如果循环内不调用任何方法,则循环永远只会使用这一个栈帧 | 调用一次方法,就要重新创建一个新的方法栈帧,可能会出现栈内存耗尽的错误 |
局部变量 | 如果某局部变量在循环语句之上声明,则这个变量只占用一个内存空间 | 如果某个局部变量在递归调用语句之上声明,则只要重建一个该方法的栈帧,这个局部变量就会在新建的方法栈帧中占用一次内存空间 |