Examples of problems whose solution can only be recursion

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.

Answer 3

If you allow appropriate data structures it is always possible to solve such recursion by introducing a stack which holds the "return point" of your original calls.

Answer 4

It depends on what you mean by iterative. If you mean just not having a function that calls itself, then you can always avoid recursion by using a stack explicitly.

Answer 5

although in this case a queue might be more appropriate:

def delete(path):
    todo = queue()
    todo.put(path)
    while todo:
        item = todo.get()
        if item.isdir():
           empty = True
           for entry in item.listdir():
               todo.put(entry)
               empty = False
           if empty:
               item.delete()
           else:
               todo.put(item)
        else:
           item.delete()