The Definitive Tail-Call Recursion Question

Question

After participating in the debate in this fiascoquestion, I would like to posit the question before the entire community.

In what scenarios will tail-call optimization be applied to .Net-based code?

Please support your answers with reliable, up-to-date sources or reproducible experiments.

Answer 1

According to "Expert F#" written by Don Syme et al., F# does tail call optimization. I seem to remember reading on Eric Lippert's blog that the C# compiler (any version) does not. Correct me if I'm wrong, Eric. In all cases tail-call optimizations can be done when the last instruction is to call a method. This will often be a recursive call of the method itself but does not need to be. The optimization can be done since it's guaranteed that the current stack frame is no longer needed. However if just a simple operation has to be performed afterwards the optimization cannot be performed.

int Fib(int n)
{
  if(n < 2)
     return 1;

  return Fib(n-1) + Fib(n-2);
}

This cannot be tail call optimized because + cannot be evaluated before the last call to Fib returns. (Actually I think this is the example used in Expert F# as well but not sure on that one.)

int Fib(int n, int a, int b)
{
  if(n == 0)
    return a+b;
  return Fib(n-1,a+b,a);
}

This version can be tail call optimized since all the arguments are evaluated before the last call to Fib and no operations exist to be performed after the call so the current stack frame can be discarded.