CODEWITHSUNDEEP
c#c#-4.0recursiontail-recursion
Bennett Yeo
Bennett Yeo

Reputation: 829

C# compilation with tail recursive optimization?

Based on the rich wealth of stackoverflow, I've been getting on and off answers on whether the tail recursive optimization is done to specifically c# code. A few of the questions appeared to talk about

  1. Speculation of the optimization in newer versions of .net that were being released
  2. Building application as a x64bit application to achieve the optimization
  3. Switching from a debug build to a release build in Visual Studio to achieve the optimization
  4. No optimization at all and that the microsoft community had claimed that they wouldn't do tail recursive optimization for "security issues" (didn't really understand this one)
  5. It happens by random

So as of C# 4.0 (Visual Studio 2013/2015) how does one ensure the tail recursive optimization if one can ensure it at all?

Upvotes: 13

Views: 5245

Answers (1)

Mike Zboray
Mike Zboray

Reputation: 40788

There are different levels at which the tail call optimization can be supported. The JIT is really responsible for most of the optimizations in any .NET program. The C# compiler itself doesn't even do method inlining, that is the JIT compiler's responsibility. The C# compiler could use the Tailcall IL opcode designating a call as a tail call, however I believe no version of C# compiler does this. The JIT compiler is permitted to make tail call optimizations whenever it sees fit. In particular, I believe only the 64-bit JIT does this. This blog post outlines a number of scenarios in which JIT64 cannot use tail call optimization. I'm sure the criteria may be subject to change since they are working on a rewrite of the JIT compiler, codenamed RyuJIT.

If you want a short example of a program that can use TCO try this:

class Program
{
    static void Main(string[] args)
    {
        Test(1);
    }

    private static void Test(int i)
    {
        Console.WriteLine(i);
        Test(i + 1);
    }
}

Set the project to build Release/x64 (or AnyCPU w/o prefer 32-bit) and start without the debugger attached. The program will run forever. If I do not do all of those things, then I get a stackoverflow exception around 20947.

Upvotes: 23

Related Questions