Examples of problems whose solution can only be recursion [duplicate]

Question

Possible Duplicate:
Can every recursion be converted into iteration?

Are there problems in which one must use recursion and there is no way to do it iteratively ? For instance deleting the files within a sub-folder's .

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();
}

I can't think of an iterative version of the above one as we must be knowing before hand how many level of folders are actually there and if we introduce a new sub folder we'll have to change the code.Is it possible to make an iterative version of the above code in such a way that future code change won't be required ?

Answer 1

You can always use a stack yourself to store the necessary variables without calling the function recursively.

In this case, one would do a depth first traversal of the file tree in order to delete the files 'deepest down' first before the owning directory etc.

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();

}

Answer 2

You can always solve a problem without recursion. Then only thing that you can't do without recursion is to show how recursion works.

Your example for deleting subfolders can be solved using a list and a loop.