Tail recursion and memoization with C#
- by Jay
I'm writing a function that finds the full path of a directory based on a database table of entries. Each record contains a key, the directory's name, and the key of the parent directory (it's the Directory table in an MSI if you're familiar). I had an iterative solution, but it started looking a little nasty. I thought I could write an elegant tail recursive solution, but I'm not sure anymore.
I'll show you my code and then explain the issues I'm facing.
Dictionary<string, string> m_directoryKeyToFullPathDictionary = new Dictionary<string, string>();
...
private string ExpandDirectoryKey(Database database, string directoryKey)
{
// check for terminating condition
string fullPath;
if (m_directoryKeyToFullPathDictionary.TryGetValue(directoryKey, out fullPath))
{
return fullPath;
}
// inductive step
Record record = ExecuteQuery(database, "SELECT DefaultDir, Directory_Parent FROM Directory where Directory.Directory='{0}'", directoryKey);
// null check
string directoryName = record.GetString("DefaultDir");
string parentDirectoryKey = record.GetString("Directory_Parent");
return Path.Combine(ExpandDirectoryKey(database, parentDirectoryKey), directoryName);
}
This is how the code looked when I realized I had a problem (with some minor validation/massaging removed). I want to use memoization to short circuit whenever possible, but that requires me to make a function call to the dictionary to store the output of the recursive ExpandDirectoryKey call. I realize that I also have a Path.Combine call there, but I think that can be circumvented with a ... + Path.DirectorySeparatorChar + ....
I thought about using a helper method that would memoize the directory and return the value so that I could call it like this at the end of the function above:
return MemoizeHelper(
m_directoryKeyToFullPathDictionary,
Path.Combine(ExpandDirectoryKey(database, parentDirectoryKey)),
directoryName);
But I feel like that's cheating and not going to be optimized as tail recursion.
Any ideas? Should I be using a completely different strategy? This doesn't need to be a super efficient algorithm at all, I'm just really curious. I'm using .NET 4.0, btw.
Thanks!
