解决方案只能递归的问题示例

Question

可能重复:
每次递归都可以转换为迭代吗？

是否存在必须使用递归的问题,并且无法迭代地执行此操作？例如,删除子文件夹中的文件.

public static boolean deleteFile(String sFilePath)
{
  File oFile = new File(sFilePath);
  if(oFile.isDirectory())
  {
    File[] aFiles = oFile.listFiles();
    for(File oFileCur: aFiles)
    {
       deleteFile(oFileCur.getAbsolutePath());
    }
  }
  return oFile.delete();
}

我无法想到上面那个的迭代版本,因为我们必须事先知道实际存在多少级别的文件夹,如果我们引入一个新的子文件夹,我们将不得不更改代码.是否可以制作上述代码的迭代版本,以便将来不需要更改代码？

Answer 1

您总是可以自己使用堆栈来存储必要的变量,而无需递归调用函数.

在这种情况下,人们会对文件树进行深度优先遍历,以便在拥有目录之前首先删除文件"最深处".

public static void deleteFile(String sFilePath)
{
  File oFile = new File(sFilePath);
  Stack<File> filesToDelete = new Stack<File>();
  Stack<File> directoriesToDelete = new Stack<File>();

  filesToDelete.push(oFile);

  while (! filesToDelete.empty())
  {
    oFile = filesToDelete.pop();

    if(oFile.isDirectory())
    {
      File[] aFiles = oFile.listFiles();
      for(File oFileCur: aFiles)
      {
        filesToDelete.push(oFileCur);
      } 

      // it's a directory, delete it at the end
      // note that we'll see directories 
      // 'deeper down' later but we'll have
      // to delete them before those 'higher up'
      // so use a stack here to delete them
      // after all non-directories were
      // deleted
      directoriesToDelete.push(oFile);

    }
    else
      // it's a file, delete right now
      oFile.delete();

  }

  // delete the directories
  while (! directories.empty())
    directoriesToDelete.pop().delete();

}