Tail recursion and memoization with C#

Question

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!

P.S. If you're wondering about my terminating condition, don't worry. I pre-seed the dictionary with the root directory.

Answer 1

You said you are curious, and so am I, let's see what you think about this approach. I'm generalizing your problem in order to explain my point. Let's assume you have a Record type like this:

class Record
{
    public int Id { get; private set; }
    public int ParentId { get; private set; }
    public string Name { get; private set; }

    public Record(int id, int parentId, string name)
    {
        Id = id;
        ParentId = parentId;
        Name = name;
    }
}

and a "database" represented by this function:

static Func<int, Record> Database()
{
    var database = new Dictionary<int, Record>()
     {
         { 1, new Record(1, 0, "a") },
         { 2, new Record(2, 1, "b") },
         { 3, new Record(3, 2, "c") },
         { 4, new Record(4, 3, "d") },
         { 5, new Record(5, 4, "e") },
     };
     return x => database[x];
 }

Let's introduce a way to "represent" recursion like this:

public static class Recursor
{
    public static IEnumerable<T> Do<T>(
        T seed, 
        Func<T, T> next, 
        Func<T, bool> exit)
    {
        return Do(seed, next, exit, x => x);
    }

    public static IEnumerable<TR> Do<T, TR>(
        T seed, 
        Func<T, T> next, 
        Func<T, bool> exit, 
        Func<T, TR> resultor)
    {
        var r = seed;
        while (true)
        {
            if (exit(r))
                yield break;
            yield return resultor(r);
            r = next(r);
        }
    }
}

This is not doing recursion at all, as you can see, but allows us to express an algorithm in terms of parts that "look like" recursive. Our path generation function would look like this:

static Func<int, string> PathGenerator(Func<int, Record> database)
{
    var finder = database;

    return id => string.Join("/",
        Recursor.Do(id,                       //seed
                    x => finder(x).ParentId,  //how do I find the next item?
                    x => x == 0,              //when do I stop?
                    x => finder(x).Name)      //what do I extract from next item?
                .Reverse());                  //reversing items
}

this function uses the Recursor to represent the algorithm, and collects all the yielded parts to compose the path. The idea is that the Recursor does not accumulate, it delegates the responsibility of accumulation to the caller. We will use it like this:

var f = PathGenerator(Database());
Console.WriteLine(f(3));           //output: a/b/c

You also wanted memoization, let's introduce this:

public static class Memoizer
{
    public static Func<T, TR> Do<T, TR>(Func<T, TR> gen)
    {
        var mem = new Dictionary<T, TR>();
        return (target) =>
        {
            if (mem.ContainsKey(target))
                return mem[target];
            mem.Add(target, gen(target));
            return mem[target];
        };
    }
}

With this, you can memoize all your accesses to your expensive resource (the database) simply changing one line in PathGenerator, from this:

var finder = database;

to this:

var finder = Memoizer.Do<int, Record>(x => database(x));

Answer 2

First major problem you will run into, even if you do get the layout of the code right, is that the C# compiler doesn't really support tail recursion well. Tail recursion in C#

Using the info there, you can probably make it work. But it will be inelegant at best.