What Is Tail Call Optimization?

Question

Very simply, what is tail-call optimization? More specifically, Can anyone show some small code snippets where it could be applied, and where not, with an explanation of why?

Answer 1

A "tail call" is a function that returns the result of another function. My examples are in JavaScript:

function square(num) {

return Math.pow(num, 2);

}

The square() function returns the result of the Math.pow() function as a tail call.

Optimization is important when the tail call involves recursion, or when the function returns a call to itself. Specifically, the recursive function should not hold on to values while waiting for the result of the tail call, or it'll risk using up all available memory and ultimately crashing. In other words, there's no foreknowledge of how deep the recursion will go, and if each function call takes a portion of the finite memory pool, eventually memory will run out. Let me give you a common example using factorials:

//naive implementation

function factorial(num) {

if (num <= 1) return 1;

else return num * factorial(num - 1);

}

Each call to factorial() saves the value of num in memory, and (if num is positive) there will be num-1 unoptimized recursive calls. For example, factorial(3) will recursively call itself twice, saving 3 the first time, then saving 2 the second time. Then there is a third call, when num equals one, but the tail call is optimized because it stores nothing in memory. The nested functions are then able to release memory space one by one (the 2 is released, then the 3) as the recursion backs up to the original call and returns the final result.

Now imagine calling factorial(1000). There will be 999 unoptimized tail calls because the numbers 2-1000 must be saved in memory until that last call of factorial(1) is complete. At some point, a high enough num will crash the system when memory runs out.

The solution is to write your recursive function so that every tail call is optimized. In JavasScript, it would look like this:

//with tail-call optimization

function factorial(num, product = 1) {

if (num <= 1) return product;

else return factorial(num - 1, num * product);

}

Here nothing is saved in memory because all needed values are passed as arguments into the tail call. The recursion isn't a function within a function within a function, etc., but rather a sequence of function calls, one after the other, each with no knowledge or memory of the previous call. With this optimized version, any value of num can be evaluated without crashing due to memory consumption.

Let me know if you need more help on this issue.

Ian