Fun with recursive Lambda functions

I saw a couple of posts on recursive lambda expressions, and I thought it would be fun to write a class to encapsulate those two approaches.  BTW, I'm running this on Orcas Beta 1, so don't try this at home (VS 2005) kids.  Let's say I wanted to write a single Func variable that computed the factorial of a number:

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

When I try to compile this, I get a compiler error:

Use of unassigned local variable 'fac'

That's no good.  The C# compiler always evaluates the right hand expression first, and it can't use a variable before it is assigned.

Something of a solution

Well, the C# compiler couldn't automagically figure out my recursion, but I can see why.  So I have a couple of different solutions, one where I create an instance of a class that encapsulates my recursion, and another where a static factory method gives me a delegate to call.  I combined both approaches into one class:

public class RecursiveFunc<T>

{

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

    private readonly Func<Func<T, T>, Func<T, T>> f;



    public RecursiveFunc(Func<Func<T, T>, Func<T, T>> higherOrderFunction)

    {

        f = higherOrderFunction;

    }



    private Func<T, T> Fix(Func<Func<T, T>, Func<T, T>> f)

    {

        return t => f(Fix(f))(t);

    }



    public T Execute(T value)

    {

        return Fix(f)(value);

    }



    public static Func<T, T> CreateFixedPointCombinator(Func<Func<T, T>, Func<T, T>> f)

    {

        Recursive<T, T> rec = r => a => f(r(r))(a);

        return rec(rec);

    }

}

Using an instance of a class

The idea behind using a class is it might be more clear to the user to have an instance of a concrete type, and call methods on that type instead of calling a delegate directly.  Let's look at an example of this usage, with the Fibonacci and factorial recursive methods:

[TestMethod]

public void RecursiveFunc_WithFactorial_ComputesCorrectly()

{

    var factorial = new RecursiveFunc<int>(fac => x => x == 0 ? 1 : x * fac(x - 1));



    Assert.AreEqual(1, factorial.Execute(1));

    Assert.AreEqual(6, factorial.Execute(3));

    Assert.AreEqual(120, factorial.Execute(5));

}



[TestMethod]

public void RecursiveFunc_WithFibonacci_ComputesCorrectly()

{

    var fibonacci = new RecursiveFunc<int>(fib => x => 

        (x == 0) || (x == 1) ? x : fib(x - 1) + fib(x - 2)

    );



    Assert.AreEqual(0, fibonacci.Execute(0));

    Assert.AreEqual(1, fibonacci.Execute(1));

    Assert.AreEqual(1, fibonacci.Execute(2));

    Assert.AreEqual(2, fibonacci.Execute(3));

    Assert.AreEqual(5, fibonacci.Execute(5));

    Assert.AreEqual(55, fibonacci.Execute(10));

}

So in each case I can pass in the Func delegate I was trying to create (without success) in the compiler error example at the top of the post.  I instantiate the class with my recursive function, and call Execute to execute that function recursively.  Not too shabby.

Using a static factory method

With a static factory method, calling the recursive function looks a little prettier.  Again, here are two examples that use the Fibonacci sequence and factorials for recursive algorithms:

[TestMethod]

public void FixedPointCombinator_WithFactorial_ComputesCorrectly()

{

    var factorial = RecursiveFunc<int>.CreateFixedPointCombinator(fac => x => x == 0 ? 1 : x * fac(x - 1));



    Assert.AreEqual(1, factorial(1));

    Assert.AreEqual(6, factorial(3));

    Assert.AreEqual(120, factorial(5));

}



[TestMethod]

public void FixedPointCombinator_WithFibonacci_ComputesCorrectly()

{

    var fibonacci = RecursiveFunc<int>.CreateFixedPointCombinator(fib => x =>

        (x == 0) || (x == 1) ? x : fib(x - 1) + fib(x - 2)

    );



    Assert.AreEqual(0, fibonacci(0));

    Assert.AreEqual(1, fibonacci(1));

    Assert.AreEqual(1, fibonacci(2));

    Assert.AreEqual(2, fibonacci(3));

    Assert.AreEqual(5, fibonacci(5));

    Assert.AreEqual(55, fibonacci(10));

}

After some thought on both, I think I like the second way better.  Calling the Func delegate directly seems to look a little nicer, and it saves me from having to have some random Fibonacci or factorial helper class.  Of course, I could still have those helper methods somewhere, but where's the fun in that?  Now if only I had taken a lambda calculus class in college...