Tail call: Optimizing recursion

Recursive functions are recommended to solve some problems, or imposed by languages like pure functional programming languages which don’t have for and while loops. But recursion may comes at a price.

Let’s use recursion to sum the elements of an array and understand how to optimize it with tail call optimization.

Note that I use JavaScript and although tail call optimization appeared in ES 6 specifications, most engines don’t implement it, including V8. Apple WebKit is one of the only ones where it is available. Other languages implementing tail call optimization are listed in the Wikipedia article about tail call.

Naive implementation

function sum(x) {
	// Base case. The sum of no elements is 0
	if (x.length === 0) {
		return 0;
	}

	// Add the first element to the sum of all the other elements
	return x[0] + sum(x.slice(1));
}

It runs like this:

Comes the call stack. The call stack keeps track of where the interpreter is in a program that calls multiple functions. When the program calls a function, the interpreter adds that function on the top of the call stack. When the function is finished, the interpreter takes it off the stack.

Basically that’s how it computes sum([1, 2, 3]):

[] is the base case. It returns 0. The interpreter has stacked 4 frames. Now it can start unstacking. With bigger arrays (about 10 000 elements depending on configuration), the call stack could reach its maximum size, crashing the program.

Tail call to the rescue

Tail call means that the final action of a function is a function call.

In the previous implementation, the final action of the function was an addition.

Let’s apply tail call. To do that, you have to add an accumulator argument to the function to save the partial sum. Using an accumulator is often required to apply tail call.

function sum(x, acc = 0) {
	// Base case: no more elements, returns the accumulator
	if (x.length === 0) {
		return acc;
	}

	// Call sum() without the first element
	// Add the first element to the accumulator
	// The recursive call to sum() is now the final action of the function
	return sum(x.slice(1), acc + x[0]);
}

It runs like this:

The interpreter doesn’t have to go back to the previous sum() call. It only has to go back to the original caller sumCaller(). Thereby, the call stack doesn’t need to keep track of all calls to sum(). That allows an optimization called tail call optimization. Interpreters that implement tail call optimization will only use one frame to keep track of the current call to sum().

With tail call optimization, the call stack is like this: