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

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 2

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
            }
        }
    }
}