将递归转换成迭代的形式

Question

众所周知，递归调用会把中间结果压到栈中，而且每次调用函数都会将参数，局部变量压栈，这样的话，会导致大量地消耗栈空间，而且，每次函数调用还要将下一次指令执行的位置压栈，这些上下文（Context）切换会导致不少开销，甚至会导致栈溢出（OS给程序开发的栈只定义了几MB的容量）。所以，有必要将常规的递归转换成尾递归，而现在很多编译器也比较智能，能自动将尾递归转换成迭代的形式。因为迭代的形式性能高于尾递归，尾递归高于常规递归。因为有一个需求，需要将工程中的svn文件全部删除，我写了如下代码，这些代码是用常规递归写的，不知如何换成迭代的形式或者尾递归，请大神们帮帮忙，将下面转换成迭代的形式，尾递归也可以代码如下：package net.liuyx.java;import java.io.File;public class Delete {
private static int counter = 0;
private static int svnCount = 0; /**
 * @param args文件名
 * 删除工程中的svn文件
 */
public static void main(String[] args) {
for (String arg : args)
handleFile(new File(arg));
System.out.println("Delete all together " + svnCount + " svn files");
}

/*
 *递归遍历文件夹下的所有文件
 */
private static void handleFile(File f) {
if (f.exists()) {
File[] files = f.listFiles();
if (files != null)
for (File file : files)
if (file.getName().contains("svn")) {
deleteAllFiles(file);
++svnCount;
} else
handleFile(file);
}
}

/*
 * 删除一个文件夹下的所有文件
 */
private static void deleteAllFiles(File f) {
if (f.exists()) {
File[] files = f.listFiles();
if (files != null) {
for (File file : files)
if (file.isDirectory()) {
deleteAllFiles(file);
file.delete();
System.out.println("successly delete " + (++counter)
+ ",it's name " + file.getName());
} else if (file.isFile()) {
file.delete();
System.out.println("successly delete " + (++counter)
+ ",it's name " + file.getName());
}
}
f.delete();
System.out.println("successly delete " + (++counter)
+ ",it's name " + f.getName());
}
}}

Answer 1

嗯哪，util包中有个类叫Stack。
你可以维护自己的一个Stack对象，需要调用deleteAllFiles的时候，将节点压栈到自己的Stack对象。
然后，做While循环，处理该Stack对象，每次Pop一个出来进行处理，直到Stack对象中所有节点均Pop完了。

Answer 2

自己使用stack，跟系统使用的Java栈又有何区别呢？再者，Stack都过时不用了。

Answer 3

自己使用stack，跟系统的Java栈当然有区别..
Java的方法栈深度只有几k(2k-3k吧)，你可以自己写代码测试下
java.util的Stack是基于数组实现的，
数组基本你不OOM，长度方面是不会出问题的
我记得在某本书上见过把递归转为迭代的很机械的方法，
就是用stack做的(想了半天想不起是哪本书，看又没人提醒下)

Answer 4

更正一下：Java的方法栈深度只有几k(2k-3k吧)
这句我说错了,深度跟具体当时的变量情况有关， public static void main(String args[]) {
try {
a();
} catch (Error e) {
System.out.println(c);
}
} static int c = 0;
private static void a(){
c ++;
a();
}比如这段，a()只执行了c++,
我电脑上c只能达到13000,
也就是它的深度,
如果在a()里面干点其他是，比如声明个变量，打印个常量之类的
深度会立马减少很多

Answer 5

Java栈空间默认值配得小，容易递归溢出。自己的Stack对象在堆中，没有递归溢出的麻烦了。

Answer 6

其实Java栈有时候也是从堆中分配的内存，只不过Java方法栈的空间默认只有400K，而本地方法栈的空间默认为128K，那么使用语言内置的方法栈或者类库中的Stack就没有多少区别了，再者，可能因为函数式语言的影响，比如Erlang，Java的方法栈容量是可以调整的，你们可以看看这个链接：http://stackoverflow.com/questions/860550/stack-overflows-from-deep-recursion-in-java我的意思是把这种递归转换成迭代或者尾递归，这样对于整个内存空间来说，能省到不少。就像你们前面说的，你在方法内部声明变量，会消耗局部变量区空间，执行指令时又会消耗操作数栈，方法返回或者异常派发时又会消耗帧数据区，每一次方法调用都会分配栈帧，而Java栈就是由这些栈帧组成的，你栈帧消耗了，Java栈空间自然消耗了，递归深度也自然就小了
我这里想弄的是一个算法问题，不是解决栈溢出。貌似所有的递归都可以转换成迭代（这好像是我在编程珠玑里面看到的），这玩意儿比较费脑经，但是在代码优化的时候用得着，希望你们能帮帮忙

Answer 7

stackoverflow那个帖子我去看过了..说实话没怎么看懂他的实现..
这两天想了下，
可以用链表实现，不知道符合你的要求不？public static void main(String[] args) {
File file = new File("testDir1");
LinkedList<File> linkedList = new LinkedList<File>();
linkedList.add(file);
int count = 0;
while(linkedList.size() > 0){
File head = linkedList.removeFirst();
if(head.isDirectory()){
for(File subFile : head.listFiles()){
linkedList.add(subFile);
}
}else{
if(head.getAbsolutePath().endsWith(".txt")){
head.delete();
count ++;
}
}
}
System.out.println("delete:" + count);
}

Answer 8

不是啊，老大，你这个是搜索.svn关键字，然后删除该文件，我那个是搜索svn关键字，这个是文件夹，下面有很多文件，但是文件名称没有包含svn三个字的也要全部删除

Answer 9

链表和堆栈，不都是Collection嘛，没有本质区别。

Answer 10

嗯，的确，这样是要快点，中间过程不断执行I/O操作，每次都要中断，把路径缓存起来统一处理I/O请求是要快不少，但是空间消耗量没少多少哦，就少了一些指令的压栈。其实，我就是想多了解下尾递归（因为把常规递归转换成尾递归，再转成迭代就简单了），因为我看一本书上讲给递归优化，把递归转换成迭代，即可提高不少效率，只可惜这方面的修为不够，简单的递归换成迭代还可以，稍微繁琐一点的就傻眼了