Tail Recursion
Written by Min-Koo Seo

Tail recursion is a kind of recursion problem solving techinique. Although recursion gives us intuitive understanding about the mechanism of problem solving, storage requirements due to repetive method call are not negligible. If the performance bottleneck of a application or stack overflow occurred during program execution, you should regard move to iteration. Iteration approach does not need so much stack and its performance is appreciable. There are several articles which tells about moving from recursion to iteration, so I will not cover it here.

Tail recursion is related to this problem. This method reduces the overhead of stack although the method call overhead can not be evaded on which recursion is based.

Let’s start from factorial example.

int fact(int);

void main()
{

   printf(“1*2*…10 = %d\n”, fact(10));
}

int fact(int n)
{
   if (n == 1) return 1;
   return n * fact(n-1);
}

If we want change fact() to tail-recursion, we should need one more function as follows.

int fact(int);

void main()
{

   printf(“1*2*…10 = %d\n”, fact(10));
}

int fact(int n)
{
   if (n == 1) return 1;
   return fact_worker(n, 1);

}

int fact_worker(int n, int result)
{
   if (n == 2) return n*result;
   else return fact_worker(n-1,result*n);
}

The reason why we need one more function is to preserve the general fact() interface. Almost all developers guess their fact() function needs only 1 parameter, so to satisfy their intuition, we should supply this old fashioned appearance.

The difference between general recursion and tail-recursion is lied in the return statement. What will happen when the general recursion function fact() is called? General fact() can not know the result beforehand, i.e., n * fact(n-1) can not be calculated before fact(n-1) returns. As a result runtime environment should reserve the space for n and fact(n-1).

On the contrary, tail-recursion removed this pitfall. fact_worker() does not wait for the result, but pass the result to the next function. As you can see, fact_worker does return fact_worker(n-1, result*n). This means that we do not need any space for the stack variable n. Note that one more boundary condition was needed to ensure the end of recursion criteria of fact_worker : if (n == 2).

Someone may argue that saving only one instance variable does not help. Of course the storage requirements of just one variable is not so important, but you should know that variables are used under recursion. If we call fact(100) with tail-recursion, we can save lots of memory; sizeof(int)*100.

In sum, tail-recursion is not so tough to understand and easy to apply to your code. Although it does not solve all the problems related to storage requirements of recursion, it works anyway.