Everything you need to know about tail recursion

Recursion is easier to write, more readable and does not require mutability. Iteration has better performance and consumes less memory. Tail recursion combines the best of both worlds. This article explains what it is, why it is more efficient than normal recursion and how to make a function tail-recursive.

This article is illustrated with code in a functional-style pseudocode.

Photo by Tom Wilson on Unsplash

What is tail recursion?

A recursive function is said to be tail recursive when the recursive call is the last operation it performs. For example, the following function is tail recursive:

but this one is not:

This is because we perform the recursive call (*) x (y — 1) and then add y to the result: the addition is the last call.

Why bother?

Recursive functions are often criticised for their performance and tail recursion enables to solve some of these problems. There are several reasons, but we will focus on one of them: the accumulation of stack frames.

Consider the following example:

Every call to bad-factorial creates a stack frame which stores all the local variables created during the evaluation of the function. The stack frame is erased once the function terminates.

If you call bad-factorial 5, a stack frame — we’ll call it bf5 — is created. Then bad-factorial 4 is called. A new stack frame bf4 is created but bf5 is still lying somewhere in memory, because bad-factorial 5 needs to know what value bad-factorial 4 will return before performing its last operation. Then bad-factorial 3, bad-factorial 2, bad-factorial 1 and bad-factorial 0 are all called, thus creating four new stack frames, bf3, bf2, bf1 and bf0. The latest call has no recursive call to perform, so it terminates and bf0 is erased from memory. This allows bad-factorial 1 to calculate its return value and bf1 to disappear as well, followed by bf2, bf3 ,bf4 and finally bf5.

To calculate bad-factorial N, we need to store all values of N separately and to remember them until the original call terminates, returning the final result. If our function needed to store an array, or any other heavier piece of data every time it is called, the amount of space required would become enormous.

And this would end up causing a dreaded stack overflow.

If a function is tail recursive, it terminates before the recursive calls start doing their work and therefore cannot cause stack overflows.

How to make a recursive function tail recursive?

There are two main techniques that enable to turn a normal recursive function into a tail-recursive function: the use of accumulator variables, and the continuation passing style. We’ll explore both of them in this section.

Accumulator variables

An accumulator variable is an additional parameter which corresponds to the final value of the computation when the last recursive call terminates.

Here is our updated factorial function, now tail-recursive:

Instead of directly changing the function, I have created an inner recursive function, loop. Thus, users won’t have to worry about the accumulator parameter and will be able to call the function normally, just providing the value of N.

The accumulator variable is result.

Instead of multiplying the result of factorial (N — 1) by N, we pass N to it so that it knows that the result will eventually have to be multiplied by N. Similarly, factorial (N — 1) multiplies the accumulator by N - 1—which takes value N(N - 1)— and sends it to factorial (N — 2), which updates the accumulator to N(N - 1)(N - 2), and so on.

With F# on my computer, the non-tail-recursive factorial function causes a stack overflow when called with 10^6, which the tail-recursive one does perfectly well.

Another, more complicated example is calculating the n-th Fibonacci number, for some natural number n. To write a tail-recursive Fibonacci calculator, we need to introduce two accumulator variables: one which corresponds to the final value and another corresponding to the previous term.

We update the result by adding previous to it and the current result will be the previous one in the following recursive call.

Continuation passing style

It is not always possible to use an accumulator variable to make a function tail recursive. Continuation passing style, or CPS for short, solves this issue: it is a more general technique which allows to turn any recursion into a tail recursion. It is slightly more complex and may be a bit confusing at first, but it’ll be all fine!

Instead of passing an accumulator variable to the recursive function f, we will pass another function which tells f what to do when it completes its computation. We’ll call this function a continuation function.

If the non-tail-recursive version of our function has signature f: T -> U, where T and U are types, the tail-recursive one has signature f: T -> (U -> U) -> U. Every call updates the continuation function and the base case passes its result to it, yielding the final computation.

For example, suppose we want to calculate the sum of the value of all nodes in a binary tree. A non tail-recursive function would look like this:

Instead of performing two recursive calls, we only recurse on one subtree (say the left one) and use a continuation function to tell the recursive call:

“Once you’re done, send me your result. I will calculate the sum of the right subtree and add them up.”

More precisely, the continuation function which we pass to the recursive call:

1. takes one parameter, leftSum;
2. calculates recursively the sum rightSum of the right subtree;
3. passes leftSum + rightSum to the original continuation function.

If the tree is empty, we simply send 0 to the continuation function. The initial continuation function is the identity function.

We implement the CPS version of the function sum as follows:

Okay, that’s a bit confusing. We’ll give a proof that it is correct, and hopefully this will allow us to develop some intuition on how this works.

Suppose we have a tree with one node, with value x. The initial continuation function is c0 = id.

To calculate the sum S of the tree, we first calculate the sum SL of the left subtree (line 11) and then call c1 (defined line 6). c1 computes the sum SR of the right subtree (line 9) and calls c0 (x + SL + SR) (lines 7 and 8).

Since SL is empty, we just call c1 0 (line 4). It computes SR, which is also empty, and returns c0 (0 + 0 + x), which is x.

We have successfully computed the sum of a tree with one node.

Suppose now that our function can calculate the sum of a tree with at most n nodes, for some natural number n. More precisely, loop tree c, where tree has at most n nodes, returns c ST, where ST is the actual sum of the tree.

Now consider a tree tree with n + 1 nodes. By the induction hypothesis, loop left continuation' returns continuation' SL, where SL is the actual sum of the left subtree. Similarly, loop right continuation'' returns continuation'' SR, where SR is the actual sum of the right subtree. The return value of loop tree id is therefore id SR + SL + value, where value is the value of the root node. This proves that we have successfully calculated the the sum of tree.

By induction, the function sum above is correct.

We finish with one last example: in-order traversal of a binary tree. Here is what a non-tail-recursive version would look like:

Instead of running lines 4 and 5 in the body of the function, we will create a continuation function which says “once you’ve traversed the left subtree, pass the current value to f and traverse the right subtree.”.

Here is how we translate this into code: