Получить папки и подпапки для чтения файла в Java с помощью хвостовой рекурсии - PullRequest
Новая
       53

Получить папки и подпапки для чтения файла в Java с помощью хвостовой рекурсии

0 голосов
/ 20 февраля 2019

Я использую обычную рекурсию для метода итерации и для получения файлов из папок и подпапок в 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());
        }
    }

}

Заранее спасибо.

1 Ответ

0 голосов
/ 20 февраля 2019

Хвостовая рекурсия - это особый вид рекурсии, который ничего не делает после рекурсивного вызова , но возвращает.

Некоторые языки программирования используют это преимущество, оптимизируя стек вызовов, так что если у вас очень глубокая рекурсия, вы не получите переполнения стека (не считая памяти и эффективности вызова сами по себе).

Часто используемая хитрость заключается в том, что вы добавляете дополнительный параметр аккумулятор , который обрабатывает все ожидающие данные.Так как это может сделать рекурсивную функцию менее пригодной для использования, это обычно делается отдельно, так что пользователю вашей функции это кажется простым.

Так что в вашем примере это будет так, обычный 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 не ( пока ) использует преимущества хвостовой рекурсии,Другие языки программирования, такие как Scala и Kotlin.

Примечание: Path обычно более мощный из старых File, вам не нужно менять Path на File в вашем случае.

...