使用尾递归检索文件夹和子文件夹以读取 java 中的文件

Question

我正在使用一种方法的正常递归来迭代并从 java 中的文件夹和子文件夹中获取文件。

谁能帮我把它改成尾递归方法？我不明白什么是尾递归。对我理解会有用。

public void findFiles(String filePath) throws IOException {
    List<File> files = Files.list(Paths.get(filePath))
                            .map(path -> path.toFile())
                            .collect(Collectors.toList());

    for(File file: files) {
        if(file.isDirectory()){ 
                if(file.list().length == 0){
                        boolean isDeleted = file.delete();

                }else{
                    findFiles(file.getAbsolutePath());
                }
        }else{
            //process files
        }
    }
}

这是我的普通递归，有人可以帮我写一个尾递归吗？

我尝试了一种方法，但我不确定这是否是尾递归以及它是如何工作的。

public static void findFiles(String filePath) throws IOException{
    List<File> files = Files.list(Paths.get(filePath))
                            .map(path -> path.toFile())
                            .collect(Collectors.toList());

    for(File file: files) {
        if(file.isDirectory() && file.list().length == 0){
             boolean isDeleted = file.delete();
        }else if(!file.isDirectory()){
                System.out.println("Processing files!!!" +  file.getAbsolutePath());
        }
        if(file.isDirectory()) {
                findFiles(file.getAbsolutePath());
        }
    }

}

提前致谢。

Answer 1

尾递归是一种特殊的递归，在递归调用之后不做任何事情，但是return。

一些编程语言通过优化调用堆栈来利用这一点，所以如果你有一个非常深的递归，你就不会以堆栈溢出而告终（除了内存和调用效率提升本身）。

经常使用的技巧是添加一个额外的 accumulator 参数，它会处理任何未完成的数据。由于这可能会降低递归函数的可用性，因此它通常是单独完成的，因此对于函数的用户来说它看起来很简单。

所以在你的例子中它会是这样的，正常的 findFiles() 只是准备递归调用，而 private findFilesRecursive() 正在做尾递归工作。

public void findFiles(String filePath) throws IOException {
  //we use a Deque<> for Last In First Out ordering (to keep subfolders with their parent)
  Deque<Path> paths = new ArrayDeque<Path>();  
  paths.add(Paths.get(filePath);
  return findFilesRecursive(paths);  
}

private void findFilesRecursive(Deque<Path> pending) {
  if (pending.isEmpty()) {
    //base case, we are ready
    return;
  }

  Path path = pending.removeFirst();
  if (Files.isRegularFile(path)) {
    //todo: process the file

  } else {
      //it is a directory, queue its subfolders for processing
     List<Path> inside = Files.list(path).collect(Collectors.toList());
     if (inside.isEmpty() {
       Files.delete(path);
     } else {
       //we use LIFO so that subfolders get processed first
       inside.forEach(pending::addFirst);
     }
  }

  //tail recursion, we do nothing after we call it
  return findFilesRecursive(pending);  
}

请注意，Java 不（yet）利用尾递归。 Scala 和 Kotlin 等其他编程语言也是如此。

旁注，Path 通常比旧的 File 更强大，您不需要在您的情况下将 Path 更改为 File。

使用尾递归检索文件夹和子文件夹以读取 java 中的文件

Retrieve folders and subfolders to read a file in java using tail recursion

java

filesystems

recursion

tail-recursion

java-8