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

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.

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.

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.

I had a happy surprise today :-)

I am reviewing my teaching material for my upcoming course on recursion with C#. And it seems that finally tail call optimization has made its way into C#.

I am using NET5 with LINQPad 6 (optimization activated).

Here is the Tail call optimizable Factorial function I used:

long Factorial(int n, long acc = 1)
{
    if (n <= 1)
        return acc;
    return Factorial(n - 1, n * acc);
}

And here is the X64 assembly code generated for this function:

See, there is no call, only a jmp. The function is agressively optimized as well (no stack frame setup/teardown). Oh Yes!

As other answers mentioned, CLR does support tail call optimization and it seems it was under progressive improvements historically. But supporting it in C# has an open Proposal issue in the git repository for the design of the C# programming language Support tail recursion #2544.

You can find some useful details and info there. For example @jaykrell mentioned

Let me give what I know.

Sometimes tailcall is a performance win-win. It can save CPU. jmp is cheaper than call/ret It can save stack. Touching less stack makes for better locality.

Sometimes tailcall is a performance loss, stack win. The CLR has a complex mechanism in which to pass more parameters to the callee than the caller recieved. I mean specifically more stack space for parameters. This is slow. But it conserves stack. It will only do this with the tail. prefix.

If the caller parameters are stack-larger than callee parameters, it usually a pretty easy win-win transform. There might be factors like parameter-position changing from managed to integer/float, and generating precise StackMaps and such.

Now, there is another angle, that of algorithms that demand tailcall elimination, for purposes of being able to process arbitrarily large data with fixed/small stack. This is not about performance, but about ability to run at all.

Also let me mention (as extra info), When we are generating a compiled lambda using expression classes in System.Linq.Expressions namespace, there is an argument named 'tailCall' that as explained in its comment it is

A bool that indicates if tail call optimization will be applied when compiling the created expression.

I was not tried it yet, and I am not sure how it can help related to your question, but Probably someone can try it and may be useful in some scenarios:

var myFuncExpression = System.Linq.Expressions.Expression.Lambda<Func< … >>(body: … , tailCall: true, parameters: … );

var myFunc =  myFuncExpression.Compile();