Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.


1. Introduction

In this tutorial, we’ll explain what tail recursion is. We’ll also talk about the advantages tail-recursive functions have over non-tail recursion.

2. Recursion

In brief, a recursive function is any function that calls an instance of itself. Let’s take a look at a function for summing arrays:

Rendered by QuickLaTeX.com

We see that SUM([x_1, x_2, \ldots, x_n) makes a recursive call to SUM([x_1, x_2, \ldots, x_{n-1}]), which in turn calls SUM([x_1, x_2, \ldots, x_{n-2}]), and so on until the base case of SUM([\ ]). This presents three issues: two pertaining to recursively processing the input, and one related to memory.

2.1. The Traversal Issues

The first issue is that we risk a stack overflow. If the recursion is too deep, it will eventually run out of the stack space and be unable to add a new frame. This scenario plays out in the case of inputs that are too large.

The second is that calculation starts from the base case, and we traverse the whole array to reach it. During that pass, we don’t do any calculations. Only after hitting the base case can we start adding the array’s elements to one another. We do so by going back to the first call. So, we pass the input array twice instead of once, as illustrated on the example of SUM([1,3,5]):

    \[\begin{aligned} SUM([1,3,5])  & = 5 + SUM([1,3]) \\ & =5 + \left(3 + SUM([1])\right) \\ & = 5 + \left(3 + \left(1 + SUM([\ ])\right)\right) \\ & = 5 + \left(3 + \left(1 + 0\right)\right) \\ & = 5 + \left(3 + 1\right)  \\ & = 5 + 4\\ & = 9 \end{aligned}\]

2.2. Memory

The third issue is that each recursive call adds a new frame to the call stack, and each frame reserves additional memory for local variables and input arguments. That’s not a problem in our previous example but is in the next one. For example, let’s imagine that we don’t have in memory the array [x_1, x_2, \ldots, x_n] we want to sum. Instead, we can get x_i by downloading a gigabyte of raw data from url_{i} and processing it to get a single number:

Rendered by QuickLaTeX.com

Now, each stack frame takes a gigabyte of memory even though we don’t need to hold the raw data after processing them.

3. Tail vs. Non-Tail Recursion

Both problems stem from the fact that SUM and DOWNLOAD{-}AND{-}SUM are non-tail recursive functions. A function is tail-recursive if it ends by returning the value of the recursive call. Keeping the caller’s frame on stack is a waste of memory because there’s nothing left to do once the recursive call returns its value. So, instead of allocating a new frame for the call, we can reuse the existing one. As a result, compilers can recognize a tail-recursive function and optimize frame allocation.

To benefit from tail-call optimization, a function need not be recursive. It can call any function, as long as the only thing to do after the call is to return the called function’s value. However, we’ll focus only on recursions in this article.

3.1. Tail-Recursive SUM

SUM isn’t tail-recursive because, after the recursive call, it adds x_n to the returned value. To make it tail-recursive, we should adjust it a bit. More specifically, we should move addition into an argument so that the last line is return SUM(\ldots). The idea is to sum the numbers as we pass through the array the first time and pass the current partial sum as an argument to SUM. That way, there’s no need to go back once we reach the base case, and the same frame can be reused:

Rendered by QuickLaTeX.com

We call it with 0 as the initial value for s, and here’s how its execution would look like for x=[1, 3, 5]:

    \[\begin{aligned} SUM([1,3,5], 0)  & = SUM([1,3], 5) \\ & = SUM([1], 8)) \\ & = SUM([\ ], 9) \\ & = 9 \\ \end{aligned}\]

The same strategy would work with DOWNLOAD{-}AND{-}SUM and other non-tail recursions. However, not all functions can be tail-optimized. If we have to process the recursive call’s return value in any way, then tail-call optimization is impossible.

4. Deriving Iterative Algorithms from Tail-Recursive Functions

Writing tail-recursive functions is equivalent to using a GOTO command in place of the recursive call:

Rendered by QuickLaTeX.com

We made two other changes. First, the partial sum s became a local variable that we initialize at the beginning of SUM. The second change is that now we treat n as a variable that points to the end of the unprocessed part of the array. So, we decrease it by 1 step by step, right before each GOTO.

4.1. From GOTO to WHILE

The above GOTO function translates to an iterative algorithm with a while-loop. The negation of the base case condition becomes the while-loop’s condition. The else-branch, except for the GOTO command, becomes the body of the while-loop, and the initialization of the partial result comes before the loop. Finally, we move the base case after the loop and get an iterative function. We iterate over the size of the input. In our example, that will be n, so the while loop’s condition is n > 0:

Rendered by QuickLaTeX.com

5. Conclusion

In this article, we explained the difference between the tail and non-tail recursion. The functions of the former type can reuse the existing stack frame, so they save memory and avoid the stack overflow error. Also, they finish the calculation after processing the base case, so they don’t traverse the call stack back to the original frame. However, to be tail-recursive and enjoy these benefits, a function has to end by returning the return value of the recursive call. 

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!