Tail calls - tail recursive functions - tail call optimization

I explain here what is a tail call, a tail recursive function, and how the compiler can optimize them. I will start with something that might be obvious to you but wasn’t 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.

* Although I use here the term tail function, you should avoid using it for functions that are not recursive because no one else does.

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.

But that explanation didn’t help me much. 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), at line 5, 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 (caller function).
function returnNumber(x) {
  return x;
}
function return2() {
  return returnNumber(2);
}
return2();

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();

In this example, the return2 function does the same thing as before, 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. Other than calling the returnNumber(1) function, it also resolves the expression spare1 + returnNumber(1) (final action) and returns it. I guess 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

You can say that in the first snippet the function return2 is a tail function, but you can’t say the same for the function in the second snippet. As a result, whether a function is a tail function or not, depends on how you implement it. A more practical example of a tail function is a tail recursive function. The following example shows a tail recursive function that returns the factorial of a number:

function factorialTail(number, acc = 1) {
  if (number === 0) return acc;
  return factorial(number - 1, acc * number);
}

And the following example shows a regular recursive function that does the same thing:

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

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 calculations in an expression, right before returning it.

Tail call optimization

Ok, you saw when a function call is tail call and when a function is a tail function. The question now is why you should care about that. The answer has to do with the call-stack and a trick the compiler can do 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.

* If you use JavaScript, it turns out you shouldn’t care much because TCO is supported only by Safari—it’s deprecated in Chrome.

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 I 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 24

With 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 24

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.

Other

Technical explanation problem

Wikipedia says that, in the following example, the a(data) call is in the tail position which makes sense with the second explanation; 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, it stores the result in a variable before returning it.

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

Sources and some relevant links.

Other things to read

Popular posts

Other notes