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 Done Syme et al. F# does tail call optimization. I seem to remember reading ón Eric Lipperts blog that the C# compiler (any version) does not. Correct me if Im wrong Eric. In all cases tall Call optimizations Can be done when the last instruction is to call a method. This will often be a recirsive Call of the method it self but do not need to be. The optimization can be done since it's guaranteed that the current stack frame is ni 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);
}

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

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

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