Does "Anonymous Recursion" work in .NET? It does in Mono

Question

I surfed into this site a few days ago on "Anonymous Recursion in C#". The thrust of the article is that the following code will not work in C#:

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

The article then goes into some detail about how to use currying and the Y-combinator to get back to "Anonymous Recursion" in C#. This is pretty interesting but a tad complex for my everyday coding I am afraid. At this point at least...

I like to see stuff for myself so I opened the Mono CSharp REPL and entered that line. No errors. So, I entered fib(8);. Much to my great surprise, it worked! The REPL replied back with 21!

I thought maybe this was some magic with the REPL, so I fired-up 'vi', typed in the following program, and compiled it.

using System;

public class Program
{
    public static void Main(string[] args)
    {
        int x = int.Parse(args[0]);
        Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
        Console.WriteLine(fib(x));
    }
}

It built and ran perfectly too!

I am running Mono 2.10 on a Mac. I do not have access to a Windows machine right now so I cannot test this on .NET on Windows.

Has this been fixed on .NET as well or is this a silent feature of Mono? The article is a couple of years old.

If it is Mono only, I cannot wait for the next job interview where they ask me to write a Fibinocci function in the language of my choice (Mono C#) where I have to provide the caveat that .NET will not work. Well, actually I can wait since I love my job. Still, interesting...

Update:

Mono is not really doing "anonymous" recursion as it is using fib as a named delegate. My bad. The fact that the Mono C# compiler assumes a null value for fib before assignment is a bug as noted below. I say "compiler" because the .NET CLR would run the resulting assembly just fine even though the .NET C# compiler would not compile the code.

For all the interview Nazis out there:

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

can be replaced with an iterative version:

Func<int, int> fib = n => 
{
    int old = 1;
    int current = 1;
    int next;

    for (int i = 2; i < n; i++)
    {
        next = current + old;
        old = current;
        current = next;
    }
    return current;
};

You might want to do this because the recursive version is inefficient in a language like C#. Some might suggest using memoization but, since this is still slower than the iterative method, they may just be being wankers. :-)

At this point though, this becomes more of an ad for functional programming than anything else (since the recursive version is so much nicer). It really does not have anything to do with my original question, but some of the answers thought that it was important.

Answer 1

This is a bug in the Mono compiler. It violates section §12.3.3 of the specification. The variable fib cannot be used in the variable initializer, because it isn't definitely assigned.

Answer 2

As I noted in a comment above, if Mono does that then they have a bug. The spec is clear that this is supposed to be detected as an error. The bug is of course mostly harmless, and most of the time does what you want. We've considered changing the rules to make this sort of recursion legal; basically we'd have to add a special case to the spec that says that this narrowly-defined case is legal. It's never been a high enough priority though.

For more thoughts on this issue see my article on the subject:

http://blogs.msdn.com/b/ericlippert/archive/2006/08/18/706398.aspx

And by the way, I would not hire anyone who gave me a straight-up recursive implementation of fib in an interview. It is extremely inefficient; its running time is proportional to the size of its output, and fib grows exponentially. To make it efficient use recursion with memoization, or implement the obvious iterative solution.