Stack Data Structure Vs. Recursion

A while ago I had an epiphany around using a stack data structure instead of recursion. Yeah, I know old news for most of you. But I don’t care, I just got it and it feels good. Anyway’s, for those of you that haven’t had that revelation yet maybe this example can help you there.

Problem

I have a scenario where I have to loop through a directory structure and look for csproj-files. What I do with them is not relevant to this example.

Solution 1 – Recursion

So, being a creature of habit I went for the recursive approach.

class Program
{
    static void Main(string[] args)
    {

        string startAddress = "C:\\SomeDir";
        DirectoryInfo di = new DirectoryInfo(startAddress);

        TraverseForProjectFiles(di);
    }


    private static void TraverseForProjectFiles(DirectoryInfo currentDirectory)
    {
        foreach (FileInfo projFile in currentDirectory.GetFiles("*.csproj"))
        {
            //Do some stuff
            Console.WriteLine("Found file: {0}", projFile.FullName);
        }

        foreach (DirectoryInfo subDirectory in currentDirectory.GetDirectories())
        {
            TraverseForProjectFiles(subDirectory);
        }
    }
}

Solution 2 – Stack Data Structure

When I was done with my little program it hit me, this must be the perfect isolated little sample for trying out the stack approach. The generic stack class is available in the namespace System.Collections.Generic.

class Program
{
    static void Main(string[] args)
    {
        Stack<DirectoryInfo> dirStack = new Stack<DirectoryInfo>();
        string startAddress = "C:\\SomeDir";
        DirectoryInfo di = new DirectoryInfo(startAddress);

        dirStack.Push(di);

        while (dirStack.Count > 0)
        {
            DirectoryInfo currentDirectory = dirStack.Pop();

            foreach (FileInfo projFile in currentDirectory.GetFiles("*.csproj"))
            {
                //Do some stuff
                Console.WriteLine("Found file: {0}", projFile.FullName);
            }

            foreach (DirectoryInfo subDir in currentDirectory.GetDirectories())
            {
                dirStack.Push(subDir);
            }
        }
    }
}

Comparison

So which of the two methods is the best? None or both… Right tool for the right job and all that. Personally I think that if the scenario was a little more complex, which it usually is out there in the real world, the Stack approach has a higher level of readability and probably debugability. But that’s just my opinion. The takeaway from this post is that recursive problems often can be solved using the Stack data structure.

One thought on “Stack Data Structure Vs. Recursion

Comments are closed.