C#: A Method for Tail Call Recursion

I’ve been reading on F# a bit, and came across its ability to do tail call recursion. Tail recursion as defined by Wikipedia:

In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function, the tail call, is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with iteration, manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique is commonly used with functional programming languages, where the declarative approach and explicit handling of state promote the use of recursive functions that would otherwise rapidly fill the call stack.

So, I decided to see if I could implement this in C#, and after a little bit of monkeying around I was able to get something working.

First off, I needed two helper classes, the first of which is the Ref<T> class. It makes it possible to keep track of a reference to an object across closures. There is also an implicit conversion back to the type it is referencing for convenience.

public class Ref<T>
{
    public T Value { get; set; }
    public static implicit operator T(Ref<T> obj)
    {
        return obj.Value;
    }
} 

Next was the LazyRef<T>, which is the same as Ref<T> but won’t actually compute the value until it is needed.

public class LazyRef<T>
{
    public T Value { get { return Factory(); } }
    public Func<T> Factory { get; set; }
    public LazyRef()
    {
    }

    public LazyRef(Func<T> factory)
    {
        this.Factory = factory;
    }

    public static implicit operator T(LazyRef<T> obj)
    {
        return obj.Value;
    }

    public static implicit operator LazyRef<T>(T obj)
    {
        return new LazyRef<T>(() => obj);
    }
} 

Alright, now all that remains is the method that does all of the magic, I’ll present it piecewise then all together at the end. First, let’s look at the method’s signature:

public static Func<T, R> ToTailCall<T, R>(
    this Func<Func<T, LazyRef<R>>, T, LazyRef<R>> target) 

It will return a delegate that represents the tail call optimized method, taking a T as the only parameter and returning an R. The only argument is the target method/delegate to be transformed. Note that the target takes a delegate as its first argument, this will be the recurse function that the method will call instead of itself when it wishes to proceed. It then takes a T, and returns a LazyRef to an R.

Now for the first part of the method, just some Ref and LazyRef variables, I’ll explain these as they are used.

var calledRef = new Ref<bool>();
var paramRef = new Ref<T>();
var currResult = new Ref<LazyRef<R>>();
var lazyResult = new LazyRef<R>(
    () => currResult.Value.Value); 

Next up is setRef, it’s the function that will be the recurse function that is passed in as the first argument when target is called.

Func<T, LazyRef<R>> setRef = t => {
    calledRef.Value = true;
    paramRef.Value = t;
    return lazyResult;
}; 

setRef first flips the calledRef flag, so that we know that target wants to do one more recursion, then we store off the value that target wanted to pass on, and we return the lazyResult. lazyResult will return currResult’s value when asked what its value is.

Next is the actual function that is returned:

return t => {
    paramRef.Value = t;
    do
    {
        calledRef.Value = false;
        currResult.Value = target(setRef, paramRef.Value);
    } while (calledRef.Value);

    return lazyResult.Value;
}; 

First off, it sets up the current parameter value as t, since it needs to be set for the first iteration. Then it enters the loop and flips the calledRef flag to false, so if target doesn’t call the recurse function, the loop will not continue. After that target is called, passing in setRef as the recurse function, and the current parameter value. It’s return is stored as the currentResult which will be lazyResult until target doesn’t call the recurse function, at which point it will return something else. This goes on until target doesn’t call the recurse function and the loop exits. After that, we return the value or lazyResult, which is the value or currentResult. Ok, so here is everything all together:

public static class Recursion
{
    public static Func<T, R> ToTailCall<T, R>(
        this Func<Func<T, LazyRef<R>>, T, LazyRef<R>> target)
    {
        var calledRef = new Ref<bool>();
        var paramRef = new Ref<T>();
        var currResult = new Ref<LazyRef<R>>();
        var lazyResult = new LazyRef<R>(
            () => currResult.Value.Value);
        Func<T, LazyRef<R>> setRef = t => {
            calledRef.Value = true;
            paramRef.Value = t;
            return lazyResult;
        };

        return t => {
            paramRef.Value = t;

            do
            {
                calledRef.Value = false;
                currResult.Value = target(setRef, paramRef.Value);
            } while (calledRef.Value);

            return lazyResult.Value;
        };
    }
} 

All of the refs end up in closures in either setRef or the return value, so the values they reference can be shared and changed. Having the current result be lazy in itself makes the whole thing possible. If we didn’t have LazyRef target would be expecting a computed value to be returned from recurse which would require actual recursion.

Time for a quick example, this will run until the x overflows:

static void Main(string[] args)
{
    var tailFoo = Recursion.ToTailCall<int, int>((recurse, x) => {
        try
        {
            Console.WriteLine(x);
            return recurse(x + 1);
        }
        catch (OverflowException)
        {
            return x;
        }
    });

    Console.WriteLine("Done, {0} was the result.", tailFoo(0));
    Console.ReadLine();            
} 

Feel free to post questions and comments.