CODEWITHSUNDEEP
c#.netalgorithmrecursionstack
palswim
palswim

Reputation: 12140

Eliminate Recursion from Delete Empty Directories Algorithm

I think I formerly knew how to do this, but it seems that I have forgotten.

I have a recursive algorithm to remove all empty directories in a directory tree:

static bool DeleteDirectoriesRecursive(string path)
{
    var remove = true;
    foreach (var dir in System.IO.Directory.GetDirectories(path))
    {
        remove &= DeleteDirectoriesRecursive(dir);
    }
    if (remove &= (System.IO.Directory.GetFiles(path).Length == 0))
        System.IO.Directory.Delete(path);
    return remove;
}

I'm trying to eliminate the recursion from this algorithm, not so much to "fix" the algorithm (i.e., the similar question doesn't use the remove variable, but I would like to keep it).

I have started a new function, using the Stack<> class, but I can't think of a good way to return to the base path and take the actions that the sub-directories have determined. I guess unraveling non-tail recursion takes a bit more effort.

Upvotes: 2

Views: 1398

Answers (2)

Steve Wortham
Steve Wortham

Reputation: 22220

Since Gabe mentioned the possibility of a StackOverflowException when using recursion I was inspired to make this work without it. I used the code here as a starting point. And here's what I came up with...

public static bool DeleteDirectories(string root)
{
    bool removed = false;

    var dirs = new Stack<string>();
    var emptyDirStack = new Stack<string>();
    var emptyDirs = new Dictionary<string, int>();

    if (!System.IO.Directory.Exists(root))
    {
        throw new ArgumentException();
    }
    dirs.Push(root);

    while (dirs.Count > 0)
    {
        string currentDir = dirs.Pop();

        string[] subDirs;
        try
        {
            subDirs = System.IO.Directory.GetDirectories(currentDir);
        }
        catch (UnauthorizedAccessException e)
        {
            Console.WriteLine(e.Message);
            continue;
        }
        catch (System.IO.DirectoryNotFoundException e)
        {
            Console.WriteLine(e.Message);
            continue;
        }

        if (Directory.GetFiles(currentDir).Length == 0)
        {
            emptyDirStack.Push(currentDir);
            emptyDirs.Add(currentDir, subDirs.Length); // add directory path and number of sub directories
        }

        // Push the subdirectories onto the stack for traversal.
        foreach (string str in subDirs)
            dirs.Push(str);
    }

    while (emptyDirStack.Count > 0)
    {   
        string currentDir = emptyDirStack.Pop();
        if (emptyDirs[currentDir] == 0)
        {
            string parentDir = Directory.GetParent(currentDir).FullName;
            Console.WriteLine(currentDir); // comment this line
            //Directory.Delete(currentDir); // uncomment this line to delete
            if (emptyDirs.ContainsKey(parentDir))
            {
                emptyDirs[parentDir]--; // decrement number of subdirectories of parent
            }
            removed = true;
        }
    }

    return removed;
}

A few notes:

  1. Crawling a tree without recursion isn't too incredibly difficult and it's accomplished in the MSDN article I linked to above. But this particular example is a little more complex than theirs.
  2. I'm storing every directory which contains no files in the emptyDirs Dictionary, along with the number of subdirectories it contains.
  3. Since the order in which the directories are deleted is critical, I had to run through the emptyDirs Dictionary in reverse order (I used Linq to accomplish this).

I imagine there are more efficient methods but this isn't too bad, and it seems to work in my testing.

UPDATE : I got rid of the reversed dictionary in favor of a 2nd stack. I still use the dictionary for fast lookups, however.

Upvotes: 1

Ry-
Ry-

Reputation: 224913

The sans-recursion version is much more difficult and not much more efficient, so I would just recommend keeping your recursion. Also, here's a version that's a little cleaner:

static bool DeleteDirectoriesRecursive(DirectoryInfo d)
{
    bool remove = true;

    foreach (DirectoryInfo c in d.GetDirectories())
    {
        remove &= DeleteDirectoriesRecursive(c);
    }

    if (remove && d.GetFiles().Length == 0) {
        d.Delete();
        return true;
    }

    return false;
}

Upvotes: 1

Related Questions