Tail Recursion

A tail-recursive call can be replaced with a goto, which avoids the overhead of the call and return and can also reduce stack space usage.

Example:

In the code fragment below, the tail-recursive call to f() can be replaced with a goto.

int f (int i)
{
  if (i > 0)
    {
      g (i);
      return f (i - 1);
    }
  else
    return 0;
}
  

Below is the code fragment after tail recursion.

int f (int i)
{

 entry:

  if (i > 0)
    {
      g (i);
      i--;
      goto entry;
    }
  else
    return 0;
}
  

Notes:

Tail recursion can significantly improve the performance of small recursive benchmarks such as Hanoi.

Although more difficult than simple tail recursion, it is also possible to optimize a() calls b() calls a() tail recursion.