Anonymous Recursion in C#

Recursion is beautiful and lambdas are the ultimate abstraction.  But how can they be used together?  Lambdas are anonymous functions and recursion requires names.  Let's try to define a lambda that computes the nth fibonacci number.

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

But this doesn't work.  The compiler will complain about the use of fib in the lambda.

Use of unassigned local variable 'fib'

Eric Lippert has a great blog post on this issue.  The problem is that the right hand side is evaluated before fib is definitely assigned.  In this case, the compiler could potentially deduce (if the language spec allowed it) that fib is not used before it is definitely assigned, but in other cases it might need to be used before fib is assigned.

A quick workaround is to assign the value null to fib and then assign the lambda to fib.  This causes fib to be definitely assigned before it is used.

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Console.WriteLine(fib(6)); // displays 8

In fact, letrec in Scheme does something very similar.

But our C# workaround doesn't really use recursion.  Recursion requires that a function calls itself.  The fib function really just invokes the delegate that the local variable fib references.  It may seem that this is just nit picking about words, but there is a difference.  For example, consider the following code:

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Func<int, int> fibCopy = fib;
Console.WriteLine(fib(6)); // displays 8
Console.WriteLine(fibCopy(6)); // displays 8
fib = n => n * 2;
Console.WriteLine(fib(6)); // displays 12
Console.WriteLine(fibCopy(6)); // displays 18

Huh!?  Notice how the result of calling fib changes and that the result of calling fibCopy differs even from the result of calling fib!  (See if you can figure out why)

We can stop this kind of craziness by passing in the function that will be used for the recursive call.  So the lambda looks the same except that it takes an extra parameter f that is called instead of fib.  When a call to f is made, we need to pass f to itself as the first argument.

(f, n) => n > 1 ? f(f,n - 1) + f(f,n - 2) : n

Unfortunately, not all is done yet.  In order to convert the lambda to a delegate, we need a delegate type.  Although it is clear what type fib should be, it may not be apparent what should be the type of our new delegate.  So let's start with the type of fib, Func<int,int>.  We do know that the return type of the delegate should be the same, so it must be int.  We also know that the second argument's type should be the same which is also int.  As for the type of the first argument, we will be passing in a delegate which will then be called with the same arguments as the delegate we are defining.  But wait!  That is recursion.  We are defining the delegate type in terms of itself.  Therefore, the first parameter will be of the same type that the delegate we are defining is.

delegate int Recursive(Recursive r, int n);

The delegate can be generalized by parameterizing the type of the first argument and the return type.

delegate R Recursive<A,R>(Recursive<A,R> r, A a);

Now we can use the lambda that we defined.

Recursive<int, int> fib = (f, n) => n > 1 ? f(f,n - 1) + f(f,n - 2) : n;
Console.WriteLine(fib(fib,6)); // displays 8

While this is an improvement, neither the lambda nor its application look as nice as the original code.  The fact that the first argument should be the delegate itself seems a little strange.  The lambda can be curried in order to separate the passing of f to f from the mechanics of the fib function.  The innermost lambda will have the same signature as the original fib function.

f => n => n > 1 ? f(f)(n - 1) + f(f)(n - 2) : n

Now that the lambda has been curried, a new definition for the Recursive delegate is required.  It now only takes one argument which is the first argument of the previous definition, but the return type changes.  Recursive returns a function (the effect of currying it) which takes the second parameter of the original definition and returns the original return type.

delegate Func<A,R> Recursive<A,R>(Recursive<A,R> r);

Once the lambda is assigned to a Recursive delegate then we can apply the delegate to itself to get the underlying function.  Furthermore, if we made a copy of the delegate and then changed the original then none of the strange effects that happened early would occur.

Recursive<int, int> fibRec = f => n => n > 1 ? f(f)(n - 1) + f(f)(n - 2) : n;
Func<int, int> fib = fibRec(fibRec);
Console.WriteLine(fib(6)); // displays 8

It is now possible to clean-up the duplicated self-application of f.  We can get rid of it by creating a lambda inside of the fibRec lambda which contains the essential fibonacci definition but which takes an argument that references what function should be called for recursion.  Then, inside of fibRec, we can do the self-application of f.

Recursive<int, int> fibRec = f => n =>
{
Func<Func<int, int>, int, int> g = (h, m) => m > 1 ? h(m - 1) + h(m - 2) : m;
return g(f(f), n);
};
Func<int, int> fib = fibRec(fibRec);
Console.WriteLine(fib(6)); // displays 8

This inner lambda looks very similar to our original lambda which took two parameters.  In fact, it appears that the whole process of construction and self-application that initially happened at the top level is now happening inside of the lambda.  The only difference is that the inner lambda does not pass a reference to itself around.  This has now be abstracted out in the call to g.

We can simplify the fibRec definition by currying the inner lambda.

Recursive<int, int> fibRec = f => n =>
{
Func<Func<int, int>, Func<int, int>> g = h => m => m > 1 ? h(m - 1) + h(m - 2) : m;
return g(f(f))(n);
};
Func<int, int> fib = fibRec(fibRec);
Console.WriteLine(fib(6)); // displays 8

Note that the definition of g does not depend on f or n at all.  Therefore, we can move it outside of the outer lambda.

Func<Func<int, int>, Func<int, int>> g = h => m => m > 1 ? h(m - 1) + h(m - 2) : m;
Recursive<int, int> fibRec = f => n => g(f(f))(n);
Func<int, int> fib = fibRec(fibRec);
Console.WriteLine(fib(6)); // displays 8

Notice in the above code that g now represents our original concept of the fibonacci function while fibRec does all of the handy work to enable anonymous recursion.  The whole process of building of fibRec and then applying it to itself only requires a reference to g.  So let's move the definition of fibRec and fib to a different function named CreateFib.

static Func<int, int> CreateFib(Func<Func<int, int>, Func<int, int>> g)
{
Recursive<A, R> fibRec = f => n => g(f(f))(n);
return fibRec(fibRec);
}

We can now call CreateFib instead of creating fibRec.

Func<Func<int, int>, Func<int, int>> g = h => m => m > 1 ? h(m - 1) + h(m - 2) : m;
Func<int, int> fib =CreateFib(g);
Console.WriteLine(fib(6)); // displays 8

But really our CreateFib function is useful for more than just creating fibonacci functions.  It can create any recursive function which takes one argument.  Parameterizing the types used by CreateFib leads to what is known as the Y fixed-point combinator.

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
Recursive<A, R> rec = r => a => f(r(r))(a);
return rec(rec);
}

We can now create any recursive lambda of one parameter that we want.

Func<int,int> fib = Y<int,int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
Func<int, int> fact = Y<int, int>(f => n => n > 1 ? n * f(n - 1) : 1);
Console.WriteLine(fib(6)); // displays 8
Console.WriteLine(fact(6)); // displays 720

Finally, the goal of anonymous recursion has been reached.