Ian Marshall logo

Ian Marshall

What is "tail-call optimization"?

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



    

The square() function above 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 the 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.



    

Each call to the factorial() function above 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 1, but that tail call is optimized because it stores nothing in memory. The nested functions are then able to release memory space one by one in reverse (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 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 value will crash the system when memory runs out.

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



    

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 series 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