Recursive Methods in Expression Trees

Writing a recursive method in C# is easy, but it’s not immediately obvious how to do the same in a LINQ expression tree.

Here’s the usual factorial example:

public uint Factorial( uint n )
{
    return ( n <= 1 ) ? 1 : n * Factorial( n - 1 );
}

To represent this in an expression tree, just assign the method to a local variable and call it.  Here’s the equivalent C#:

Func<uint, uint> factorial;
factorial = n => ( n <= 1 ) ? 1 : n * factorial( n - 1 );

Here’s how you might build it:

public Expression<Func<T, T>> MakeFactorialExpression<T>()
{
    var nParam = Expression.Parameter( typeof( T ), "n" );
    var methodVar = Expression.Variable( typeof( Func<T, T> ), "factorial" );
    var one = Expression.Convert( Expression.Constant( 1 ), typeof( T ) );

    return Expression.Lambda<Func<T, T>>(
        Expression.Block(
            // Func<uint, uint> method;
            new[] { methodVar },
            // method = n => ( n <= 1 ) ? 1 : n * method( n - 1 );
            Expression.Assign(
                methodVar,
                Expression.Lambda<Func<T, T>>(
                    Expression.Condition(
                        // ( n <= 1 )
                        Expression.LessThanOrEqual( nParam, one ),
                        // 1
                        one,
                        // n * method( n - 1 )
                        Expression.Multiply(
                            // n
                            nParam,
                            // method( n - 1 )
                            Expression.Invoke(
                                methodVar,
                                Expression.Subtract( nParam, one ) ) ) ),
                    nParam ) ),
            // return method( n );
            Expression.Invoke( methodVar, nParam ) ),
        nParam );            
}

This just returns an Expression<Func<T, T>>, which you could compile and call like this:

var factorial = MakeFactorialExpression<uint>().Compile();
var result = factorial( 5 );