黑马程序员技术交流社区

标题: 递归问题 [打印本页]

作者: 魏征 时间: 2012-5-4 16:30
标题: 递归问题
下列是一个指定路径下打印出所有文件名。应用的是递归，请问递归在内存中是如何实现的？有没有别的方法可以在指定路径下打印其所有的文件名的方法？请高手指教
public static void main(String[] args)
{
  File f=new File("d:\\java1");
  listFile(f);
}
public static void listFile(File dir)
{

  File []arr=dir.listFiles();
  for (File f:arr )
  {
if (f.isDirectory())
{
System.out.println(f.getName()+"::");
listFile(f);
}
else
System.out.println(f.getName());
  }
}

作者: 徐慧书 时间: 2012-5-4 21:58
楼主，递归最重要的两个因素之一便是出口，你的程序进来并没用判断 dir是否是文件，若是文件，你这程序便报错了。
你的程序使用的是深度搜索也就是所谓的DFS了，既然是递归当然也可以非递归实现了，主要要深度搜索，广度搜索，迭代实现，这里就给你举个广度优先搜索的非递归实现
import java.io.File;
import java.util.LinkedList;;

public class Test
{
public static void main(String[] args)
{
  File f=new File("d:\\java1");
  listFile(f);
}
public static void listFile(File dir)
{
  if(dir.isFile())
  {
   System.out.println(dir.getName());
   return;
  }
  LinkedList<File> list = new LinkedList<>();//实现了Queue 接口
  list.add(dir);
  while(list.size() > 0)
  {
   File file = list.pollFirst();
   if(file.isFile())
   System.out.println(file.getName());
   else {
System.out.println(file.getName()+"::");
for(File file2:file.listFiles())
{
list.add(file2);
}
}
  }
}
}
其他若也想了解，可以进一步交流算法经验噢！

作者: 永恒之翼网络 时间: 2012-5-4 23:10
上面的那位哥们答不错，我只补充一下递归在内存中是如何实现。它是同方法栈实现的，每次调用一个方法时，方法会进栈，遵循的是先进后出的原则。下面发现张图：
E:\javase20120302\day04\方法栈.bmp

作者: 永恒之翼网络 时间: 2012-5-4 23:11
上面的那位哥们答不错，我只补充一下递归在内存中是如何实现。它是同方法栈实现的，每次调用一个方法时，方法会进栈，遵循的是先进后出的原则。下面发现张图：
E:\javase20120302\day04\方法栈.bmp

作者: 魏征 时间: 2012-5-4 23:11

徐慧书发表于 2012-5-4 21:58
楼主，递归最重要的两个因素之一便是出口，你的程序进来并没用判断 dir是否是文件，若是文件，你这程序便报 ...

我的程序不会报错的，
else
System.out.println(f.getName());
如果非目录便打印其文件名。

作者: 永恒之翼网络 时间: 2012-5-4 23:20
上面的那位哥们答不错，我只补充一下递归在内存中是如何实现。它是同方法栈实现的，每次调用一个方法时，方法会进栈，遵循的是先进后出的原则。下面发现张图：

方法栈.jpg (56.68 KB, 下载次数: 48)

作者: 徐慧书 时间: 2012-5-5 09:23

魏征发表于 2012-5-4 23:11
我的程序不会报错的，
else
System.out.println(f.getName());

File []arr=dir.listFiles();
for (File f:arr )
可以仔细看看这两句代码，再者便是把d:\\java1改成某个文件试试

作者: 胡奎 时间: 2012-5-5 12:03
递归要不断的调用的方法，不断分配空间，效率一般比较低，可以用楼上大侠们算法实现，一般能用递归实现的，用循环就可以实现

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2