Tail calls, tail-recursive functions, and tail call optimization

Learn what is a tail call, a tail-recursive function, and how the compiler can optimize them. I will start with something that wasn’t obvious for me: a function cannot be a tail call; it can be a tail function. An example of a tail function is a tail-recursive function; a function call can be a tail call.

Tail call

The first question is when a function call is a tail call. The technical explanation says that:

A function call is a tail call when it’s the last action of the caller function.

A different way to put this is the following:

A function call is a tail call when the called function returns the same thing as the function that called it.

I like the last explanation more because it hints a connection with the call-stack, as you’ll see shortly.

Examples of tail calls

• In the following example, the function call returnNumber(2) is a tail call because it’s the last thing the return2 function (caller function) does. Or, if you prefer the other explanation, the function call returnNumber(2) is a tail call because it returns the same thing as the return2 function.

function returnNumber(x) {
  return x;
}
function return2() {
  return returnNumber(2);
}
return2();Copy

You can implement the return2 function in a way that the function call returnNumber(x) is not a tail call:

function returnNumber(x) {
  return x;
}
function return2() {
  const spare1 = 1;
  return spare1 + returnNumber(1);
}
return2();Copy

In the example above, the return2 function gives the same result, but, now, the function call returnNumber(1), at line 6, is not a tail call because it returns 1 and the caller function return2 returns 2. Or, if you prefer the technical explanation, the function call returnNumber(1) is not a tail call because it’s not the last action of the caller function return2. The last action of the return2 function it to resolve the expression spare1 + returnNumber(1) and return it. As it seems, returning a value is not considered an action.

For recognizing tail calls in expressions and statements, and for some pitfalls, see checking whether a function call is in a tail position.

Tail functions

Let’s now assume that you can name as tail function a function that contains a tail call. In the first snippet, the function return2 is a tail function, but, in the second snippet, it’s not. As a result, whether a function is a tail function or not, depends on how you implement it. Let’s now see an example of that by using a tail-recursive function and regular recursive function.

The following example shows a tail-recursive function that returns the factorial of a number:

// acc = accumulator which is a fancy name for a variable
// that you use to store a temporary result.
function factorialTail(number, acc = 1) {
  if (number === 0) return acc;
  return factorial(number - 1, acc * number);
}Copy

And here you see a recursive function (without a tail call) that does the same thing:

function factorial(number) {
  if (number === 0) return 1;
  return number * factorial(number - 1);
}Copy

The tail-recursive function stores the result in an accumulator variable and passes it to the next function call. On the other hand, the plain recursive function performs the calculation in an expression, right before returning it.

Tail call optimization

You saw when a function call is tail call and when a function is a tail function. But why this is important? The answer has to do with the call-stack and a trick the compiler does that’s called tail call optimization (TCO).

Tail call optimization happens when the compiler recognizes that a function call is a tail call and reuses the current stack frame, instead of placing a new one on top that will increase the stack size.

Instead of getting technical with call-stacks, stack-frames, and local/global variables, I’ll show you a visualization that shows what happens in the call stack when you call factorialTail(4). In the first snippet, the compiler does not perform TCO and in the second it does. I got the idea from the Wikipedia page but changed it a bit.

No tail call optimization → 5 stack frames:

// factorialTail(number, acc = 1)
call factorialTail (4, 1)
  call factorialTail (3, 4)
    call factorialTail (2, 12)
      call factorialTail (1, 24)
        call factorialTail (0, 24)
        return 24
      return 24
    return 24
  return 24
return 24Copy

Tail call optimization → 1 stack frame:

// factorialTail(number, acc = 1)
call factorialTail (4, 1)
replace with factorialTail(3, 4)
replace with factorialTail(2, 12)
replace with factorialTail(1, 24)
replace with factorialTail(0, 24)
return 24Copy

The first snippet shows that new frames are being allocated—indicated by the indentation—when the compiler does not perform tail call optimization. The second snippet shows that when the compiler performs TCO, it reuses the current frame for the new function call, instead of adding a new frame to the call-stack.

Technical explanation problem

The following example is from Wikipedia’s page about tail call. The author says that the a(data) call is in the tail position. By the way, please, give descriptive names to your variables/functions! This makes sense with the second explanation because it returns the same thing as the foo2 function. It doesn’t make sense with the first explanation, though, because the a(data) call is not the last action of the foo2 function. After the a(data) call, the function stores that result in a variable and then returns it.

function foo2(data) {
  var ret = a(data);
  return ret;
}Copy

Links

Sources and some relevant links.

• Tail call optimization in ECMAScript 6
• Recursion
• Tail Recursion for Fibonacci. It’s a bit more complex than the factorial (and by a bit I mean a lot).
• Wikipedia page for Tail Call