Why doesn't .net/C# eliminate tail recursion?

Question

I found this question about which languages optimize tail recursion. What I want to know is why C# doesn't optimize tail recursion, whenever possible?

For a concrete case, why isn't this method optimized into a loop (VS2008 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);
}

Answer 1

This Microsoft Connect feedback submission should answer your question. It contains an official response from Microsoft, so I'd recommend going by that. By the way, as it has been pointed out, it is worth noting that tail recursion is optimised on x64.

Answer 2

I was recently told that C# compile 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.

Answer 3

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). I believe the current csc will too.

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

Answer 4

Problaby because recursion is harder than iteration for many problems, in others it's trivial to convert recursion into iteration and many others probably will not cause a stackoverflow anyway, so probably it was not a must-have optimization and they left it to the JIT (64-bits JIT does, but 32-bit JIT not)
C# compiler doesn't have as many optimizations as most C++ compilers.
For example divide a variable between 3 using division and binary shift and multiplication, the division will be slower in C# but the C++ compiler probably will optimize it better than you.