C#: How to make this method non-recursive

Question

I have this recursive method which deletes empty folders:

    private void DeleteEmpty(DirectoryInfo directory)
    {
        foreach (var d in directory.GetDirectories())
        {
            DeleteEmpty(d);
        }

        if (directory.GetFileSystemInfos().Length == 0)
        {
            try
            {
                directory.Delete();
            }
            catch (Exception)
            {
                // Already gone, no permission, not empty, et cetera
            }
        }
    }

How can I refactor this method so that it is not recursive?

Answer 1

Create a queue that has all the directories in the starting directory, then while it's not empty, take the next item, check if the directory's empty, if it is delete it, if not add all the subdirectories to the queue.

I don't know C#, but if there isn't a standard queue type, a linked list or mutable array type thing would work just as well.

Pseudocode;

directories = empty queue
until directories is not empty
    next = directories.shift
    if next is an empty folder
        delete it
    or else
        add all the subdiretories to the queue

Answer 2

The standard refactoring is to store the data you would otherwise be passing to the function in a LIFO (i.e. a stack) or FIFO queue. Note that this doesn't change asymptotic space usage; you're using your own data structure rather than the call stack.

If you can define a "next sibling" function, you can visit the nodes with constant additional space. This is because the graph of directories (sans files) is essentially undirected due to parent pointers. Pseudocode:

nextBranchingSibling(sibling):
  while sibling exists
    if sibling has children
      return sibling
    sibling = nextSibling(sibling)
  return null

nextBranch(node):
  if node is marked
      unmark node
  else
      if nextBranchingSibling(firstChild(node)) exists
          return nextBranchingSibling(firstChild(node))
  if nextBranchingSibling(nextSibling(node)) exists
      return nextBranchingSibling(nextSibling(node))
  mark parent(node)
  return parent(node)

prune(node):
  while node exists:
    tmpNode = node
    node    = nextBranch(node)
    if count of tmpNode's children is 0
      delete tmpNode

Note that you're not actually using O(1) space total, since the directory structure is itself O(n). Methods like DirectoryInfo.GetDirectories can remove the need for loops in nextBranchingSibling.

Answer 3

private static Queue<DirectoryInfo> directoryQueue = new Queue<DirectoryInfo>();
private void DeleteEmpty(DirectoryInfo directory)
{
    directoryQueue.Enqueue(directory);
    while (directoryQueue.Count > 0)
    {
        var current = directoryQueue.Dequeue();
        foreach (var d in current.GetDirectories())
        {
            directoryQueue.Enqueue(d);
        }

        if (directory.GetFileSystemInfos().Length == 0)
        {
            try
            {
                directory.Delete();
            }
            catch (Exception)
            {
                // Already gone, no permission, not empty, et cetera
            }
        }
    }
}

Answer 4

You could use a local Stack and loop while the stack is not empty.

public void DeleteDirectories(DirectoryInfo directoryInfo, bool deleteFiles)
{
 Stack<DirectoryInfo> directories = new Stack<DirectoryInfo>();
 directories.Push(directoryInfo);

 while (directories.Count > 0)
 {
  var current = directories.Peek();

  foreach (var d in current.GetDirectories())
   directories.Push(d);

  if (current != directories.Peek())
   continue;

  if (deleteFiles)
   foreach (var f in current.GetFiles())
   {
    f.Delete();
   }

  if (current.GetFiles().Length > 0 || current.GetDirectories().Length > 0)
   throw new InvalidOperationException("The directory " + current.FullName + " was not empty and could not be deleted.");

  current.Delete();

  directories.Pop();
 }
}

Answer 5

Try this:

private void DeleteEmpty(string path)
{
    string[] directories = Directory.GetDirectories(
        path, "*", SearchOption.AllDirectories);

    // you should delete deeper directories first
    //      .OrderByDescending(
    //          dir => dir.Split(Path.DirectorySeparatorChar).Length)
    //              .ToArray();

    foreach (string directory in directories)
    {
        DirectoryInfo info = new DirectoryInfo(directory);
        if (info.GetFileSystemInfos().Length == 0)
        {
            info.Delete();
        }
    }

    // If you wanna a LINQ-ish version
    // directories.Where(dir => 
    //     new DirectoryInfo(dir).GetFileSystemInfos().Length == 0)
    //         .ToList().ForEach(dir => Directory.Delete(dir));
}

Another performance step could be: if you tried to remove a directory and it contains files, all parent levels should be skipped since they WILL fail too.