How to write a recursive lambda

Easy, isn’t it?

At first glance, this problem looks quite easy, isn’t it? Let’s try:

Func<int, int> factorial = x => x == 0 ? 1 : x * factorial(x - 1);

Unfortunately, the above code will fail to compile, because factorial is used when unassigned.

So, how about we assign it before doing this:

Func<int, int> factorial = null;
factorial = x => x == 0 ? 1 : x * factorial(x - 1);

Yay! This time the code compiles! Problem solved, isn’t it?

Well, sort of, unless we continue to write:

var f2 = factorial;
factorial = i => i;

Console.WriteLine(f2(5));

This will output 20 instead of 120, because f2 becomes the following when factorial = i => i

x => x == 0 ? 1 : x * (i => i)(x - 1)

So, what now?

Map from a function to another function

Consider the following map function:

Func<Func<int, int>, Func<int, int>> map = f => x => x == 0 ? 1 : x * f(x - 1);

It takes a function f, and returns a function that uses f as if it’s a factorial function.

If f is indeed a factorial function, then the resulting function will be a factorial function.

Fixed-points of a function

Generally, if x = g(x), then x is a fixed-point of g. Let’s say x = Fix(g).

In our case, because applying a factorial function f to map gives us a factorial function, a factorial function is actually a fixed-point of map, which is Fix(map). So f = Fix(map).

Now let’s find Fix(g):

static Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> g)
{
    // ...
}

By definition, we have x = g(x), because x = Fix(g), we have Fix(g) = g(Fix(g)). So we have:

static Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> g)
{
    return g(Fix(g));
}

Not quite yet, because we are here to work out a fixed-point definition of g, not executing it, we need one more step:

static Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> g)
{
    return x => g(Fix(g))(x);
}

Essentially this function is creating a function that gets the fixed-point function of g and then calls g.

Result

Now if we apply Fix(map) to map, which is map(Fix(map)), it will return our factorial function. But Fix(map) itself is aleady a factorial function!

Full source:

class Program
{
    static void Main( string[] args )
    {
        Func<Func<int, int>, Func<int, int>> map
            = fac => x => x == 0 ? 1 : x * fac(x - 1);

        var factorial = Fix(map);

        Console.WriteLine(factorial(5));
    }

    static Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> g)
    {
        return x => map(Fix(g))(x);
    }
}