Tail vs. Non-Tail Recursion | Baeldung on Computer Science

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:

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:

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:

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:

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$ :

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.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex