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 dirStack = new Stack();
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.
Tags: .NET Development