Why doesn't .NET/C# optimize for tail-call recursion?

I found this question about which languages optimize tail recursion. Why C# doesn't optimize tail recursion, whenever possible?

For a concrete case, why isn't this method optimized into a loop (Visual Studio 2008 32-bit, if that matters)?:

private static void Foo(int i)
{
    if (i == 1000000)
        return;

    if (i % 100 == 0)
        Console.WriteLine(i);

    Foo(i+1);
}

Solution 1:

JIT compilation is a tricky balancing act between not spending too much time doing the compilation phase (thus slowing down short lived applications considerably) vs. not doing enough analysis to keep the application competitive in the long term with a standard ahead-of-time compilation.

Interestingly the NGen compilation steps are not targeted to being more aggressive in their optimizations. I suspect this is because they simply don't want to have bugs where the behaviour is dependent on whether the JIT or NGen was responsible for the machine code.

The CLR itself does support tail call optimization, but the language-specific compiler must know how to generate the relevant opcode and the JIT must be willing to respect it. F#'s fsc will generate the relevant opcodes (though for a simple recursion it may just convert the whole thing into a while loop directly). C#'s csc does not.

See this blog post for some details (quite possibly now out of date given recent JIT changes). Note that the CLR changes for 4.0 the x86, x64 and ia64 will respect it.

Solution 2:

This Microsoft Connect feedback submission should answer your question. It contains an official response from Microsoft, so I'd recommend going by that.

Thanks for the suggestion. We've considered emiting tail call instructions at a number of points in the development of the C# compiler. However, there are some subtle issues which have pushed us to avoid this so far: 1) There is actually a non-trivial overhead cost to using the .tail instruction in the CLR (it is not just a jump instruction as tail calls ultimately become in many less strict environments such as functional language runtime environments where tail calls are heavily optimized). 2) There are few real C# methods where it would be legal to emit tail calls (other languages encourage coding patterns which have more tail recursion, and many that rely heavily on tail call optimization actually do global re-writing (such as Continuation Passing transformations) to increase the amount of tail recursion). 3) Partly because of 2), cases where C# methods stack overflow due to deep recursion that should have succeeded are fairly rare.

All that said, we continue to look at this, and we may in a future release of the compiler find some patterns where it makes sense to emit .tail instructions.

By the way, as it has been pointed out, it is worth noting that tail recursion is optimised on x64.

Solution 3:

C# does not optimize for tail-call recursion because that's what F# is for!

For some depth on the conditions that prevent the C# compiler from performing tail-call optimizations, see this article: JIT CLR tail-call conditions.

Interoperability between C# and F#

C# and F# interoperate very well, and because the .NET Common Language Runtime (CLR) is designed with this interoperability in mind, each language is designed with optimizations that are specific to its intent and purposes. For an example that shows how easy it is to call F# code from C# code, see Calling F# code from C# code; for an example of calling C# functions from F# code, see Calling C# functions from F#.

For delegate interoperability, see this article: Delegate interoperability between F#, C# and Visual Basic.

Theoretical and practical differences between C# and F#

Here is an article that covers some of the differences and explains the design differences of tail-call recursion between C# and F#: Generating Tail-Call Opcode in C# and F#.

Here is an article with some examples in C#, F#, and C++\CLI: Adventures in Tail Recursion in C#, F#, and C++\CLI

The main theoretical difference is that C# is designed with loops whereas F# is designed upon principles of Lambda calculus. For a very good book on the principles of Lambda calculus, see this free book: Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman.

For a very good introductory article on tail calls in F#, see this article: Detailed Introduction to Tail Calls in F#. Finally, here is an article that covers the difference between non-tail recursion and tail-call recursion (in F#): Tail-recursion vs. non-tail recursion in F sharp.

Solution 4:

I was recently told that the C# compiler for 64 bit does optimize tail recursion.

C# also implements this. The reason why it is not always applied, is that the rules used to apply tail recursion are very strict.

Solution 5:

You can use the trampoline technique for tail-recursive functions in C# (or Java). However, the better solution (if you just care about stack utilization) is to use this small helper method to wrap parts of the same recursive function and make it iterative while keeping the function readable.