首页 > 嗟来之食 > 树的遍历与递归
2018
06-06

树的遍历与递归

最近做一个统计工作,需要遍历一些文件,一个文件夹下面有很多层的小文件,如何算出这个文件夹下面有多少文件?相信很多人第一时间都能想到递归遍历,这是最直接,最简单的办法。在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,可能会导致栈溢出。当文件夹深度足够深,递归的反复调用会导致方法一直无法释放,造成jvm的栈溢出。那我们该怎么办?
如何遍历文件夹
学过数据结构的都知道,文件夹就类似于数据结构的中的树,遍历文件夹就如同遍历树。常见的遍历思想有深度优先遍历和广度优先遍历,其中递归遍历就属于深度优先遍历的一种。
一、递归遍历
public void traverseFile_recursion(File root) {
if (root != null) {
if (root.isDirectory()) {
File[] files = root.listFiles();
for (File f : files) {
traverseFile_recursion(f);
}
} else {
System.out.println(root.getPath());
}
}
}
递归方法遍历很容易看懂,递归函数的优点是定义简单,逻辑清晰。这里不细说了,看上面代码就OK了。
二、非递归的深度优先遍历
public void traverseFile_depth(File root) {
Stack<File> fileStack = new Stack<>();
File file;
if (root != null && root.isDirectory()) {
fileStack.push(root);
}
while (!fileStack.isEmpty()) {
file = fileStack.pop();
File[] files = file.listFiles();
for (File f : files) {
if (f.isDirectory()) {
fileStack.push(f);
} else {
System.out.println(f.getPath());
}
}
}
}
深度优先遍历,借助了一个栈,然后按次序读取文件夹的元素,并判断如果是文件夹则把该文件夹入栈。然后栈顶的文件夹再出栈,遍历,以此类推,直到所有的文件夹都出栈,再也没有文件夹入栈。
三、广度优先遍历
public void traverseFile_Width(File root) {
Queue<File> fileQueue = new ArrayDeque<>();
File file;
if (root != null && root.isDirectory()) {
fileQueue.add(root);
}
while (!fileQueue.isEmpty()) {
file = fileQueue.remove();
File[] files = file.listFiles();
for (File f : files) {
if (f.isDirectory()) {
fileQueue.add(f);
} else {
System.out.println(f.getPath());
}
}
}
}
广度优先遍历,借助了一个队列,然后按次序读取文件夹的元素,并判断如果是文件夹则把该文件夹加入队尾,然后队首的文件夹再出队,遍历,以此类推,直到所有的文件夹都出队,再也没有文件夹入队。
关于递归的性能问题

虽然递归方法在解决一些问题时,逻辑思路很清晰,在很多情况下递归还是不建议使用的,效率偏低,严重的情况下,会造成栈溢出。解决办法是使用尾递归或者使用循环方式。理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。下面,举例子说明一下

一、斐波拉契数列
斐波拉契数列指的是这样一个数列:1、1、2、3、5、8、13、21、34、……第1个和第2个数是1,从第3个位置起,每个数等于它前面两个数的和。求第 n 个位置的数是多少?
使用递归方法实现很简单,方法如下:
public long fun1(int x) {
if (x == 1)
return 1;
else if (x == 2)
return 1;
else {
return fun1(x – 1) + fun1(x – 2);
}
}
测试代码如下:
public static void main(String[] args) {
long start_time = System.currentTimeMillis();
long result = new Fibo().fun1(46);
System.out.println("结果: " + result);
long end_time = System.currentTimeMillis();
System.out.println("耗时: " + (end_time – start_time));
}
以下是基于我的PC(i7-7700,16G-DDR4-2400)的执行结果:
位置:46
结果: 1836311903
耗时: 5170
位置:47
结果: 2971215073
耗时: 8355
位置:48
结果: 4807526976
耗时: 13377
位置:49
结果: 7778742049
耗时: 21941
位置:50
结果: 12586269025
耗时: 34915
位置:51
结果: 20365011074
耗时: 57158
看这个时间增加,你还想用递归求吗?求位置51的用时接近一分钟。
下面用循环来实现:
public long fun2(int x) {
long num1 = 1;
long num2 = 1;
long result = 0;
if (x == 1) {
return 1;
} else if (x == 2) {
return 1;
} else {
for (int i = 3; i <= x; i++) {
result = num1 + num2;
num1 = num2;
num2 = result;
}
return result;
}
}
同样测试位置 51 的结果:
结果: 20365011074
耗时: 0
几乎是秒算出结果。再看看100位置:
结果: 3736710778780434371
耗时: 1
同样几乎是秒出结果。这说明,用循环的方式,时间几乎是常数级的。若要用递归方式求100位置的,我想我可以让程序执行,然后去睡觉了。
二、遍历打印 List 元素
上面关于递归使用,由于迭代层次还没到一定级别,所以只能时间长,还没到栈溢出的地步,下面我们测试一下遍历上万元素的了 List ,来说明,上代码:
public static void printElement(Iterator<Integer> iterator) {
if (!iterator.hasNext()) {
return;
} else {
System.out.println(iterator.next());
printElement(iterator);
}
}
测试代码:
public static void main(String[] args) {
List<Integer> list = new ArrayList();
for (int i = 0; i < 20000; i++) {
list.add(i);
}
long start_time = System.currentTimeMillis();
printElement(list.iterator());
long end_time = System.currentTimeMillis();
System.out.println("耗时: " + (end_time – start_time));
}
我们用递归的方式遍历 List ,运行结果部分截图:

程序崩了,报的错,正是栈溢出。下面用循环方式遍历:
public static void printElement2(Iterator<Integer> iterator) {
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
测试结果部分截图如下:

方法调用时的内存情况
下面摘录《数据结构预算法分析-Java语言描述》中的几段话:
说明了方法调用的过程,由此也解释了深层次递归性能低的原因。

当调用一个新方法时,主调例程的所有局部变量需要由系统存储起来,否则被调用的新方法将会重写由主调例程的变量所使用的内存。不仅如此,该主调例程的当前位置也必须要存储,以便在新方法运行完后知道向哪里转移。这些变量一般由编译器指派给机器的寄存器,但存在某些冲突(通常所有的方法都是获取指定给1号寄存器的某些变量),特别是涉及到递归的时候。该问题类似于平衡符号的原因在于,方法调用和方法返回基本上类似于开括号和闭括号。

当存在方法调用的时候,需要存储的所有重要信息,诸如寄存器的值(对应变量的名字)和返回地址 (它可从程序计数器得到,一般情况是在一个寄存器中)等, 都要以抽象的方法存在“一张纸上”并被置于一个堆(pile)的顶部。然后控制转移到新方法,该方法自由地用它的一些值替代这些寄存器。如果它又进行其它的方法调用,那么它也遵循相同的过 程。当该方法要返回时,它查看堆顶部的那张“纸”并复原所有的寄存器,然后进行返回转移。

显然,所有全部工作均可由一个栈来完成,而这正是在实现递归的每一种程序设计语言中实际发生的事实。所储存的信息或称为活动记录(activation record),或叫做帧栈(stack frame)。

在实际计算机中的栈常常是从内存分区的高端向下增长,而在许多非Java系统中是不检测溢出的。失控递归可能导致栈溢出。

最后编辑:
作者:
这个作者貌似有点懒,什么都没有留下。

留下一个回复