### Introduction

The JavaScript Memoization series introduced a recursive Fibonacci sequence generator. Memoization, a method of caching results, was used to enhance performance. Performance can also be enhanced by tail call optimization.

### Tail Call Optimization

Tail call optimization is a compiler feature that replaces recursive function invocations with a loop. Eliminating function invocations eliminates both the stack size and the time needed to setup the function stack frames. Both time and space are saved.

The developer must write methods in a manner facilitating tail call optimization. This means the last function invoked must be the invocation of the recursive function. Let’s take a look at the traditional recursive implementation of the factorial function to see what this means.

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

The *factorial* function invokes *** last, not *factorial*. This implementation cannot be optimized.

function factorial(n) { function recur(n, acc) { if (n == 0) { return acc; } else { return recur(n-1, n*acc); } } return recur(n, 1); }

This *factorial* implementation features an inner function, *recur*, providing a delegate for *factorial*. The *recur* function is implemented for tail call optimization. The last function invoked is *recur*. The compiler is thus able to produce code invoking *recur* in a loop until a result other than *recur* is returned.

An extra parameter has been added to *recur*—** acc**. This is the accumulator, the function value accumulated to this point. Let’s trace through the

*recur*method to see how the factorial result is accumulated:

**factorial(5)** → recur(5,1)

recur(5,1) → recur(4,5)

recur(4,5) → recur(3,20)

recur(3,20) → recur(2,60)

recur(2,60) → recur(1,120)

recur(1,120) → recur(0,120)

recur(0,120) → **120**

All recursive functions must have a **base case** terminating the recursion. The base case for the factorial function is when **n=0** in which case 1 is returned. Likewise the base case of *recur* is also when **n=0**, but instead of returning 1 the accumulated value is returned.

### A Tail Call Optimization Strategy Emerges

Use this strategy for creating optimized recursive functions:

- Create an inner recursive function having an additional
*accumulator*parameter - The base case of the inner recursive function is to return the
*accumulator* - The recursive invocation provides an updated value for the
*accumulator* - Outer function delegates to the inner recursive function using appropriate initial values

Follow this strategy and your recursive functions can be optimized—providing significant performance improvements. That is as long as your system provides tail call optimizations. Which JavaScript doesn’t.

### Bouncing on Trampolines

How can we optimize recursive JavaScript functions without tail call optimization? One option is to re-write your recursive function in loop form.

function factorial(n) { var acc = 1; for (var i=n; i > 0; i--) { acc *= i; } return acc; }

Thus implementing the tail call optimization by hand. The downside being the loss of the elegance and expressiveness of the recursive implementation.

Another option is to use a *trampoline*.

Wikipedia defines a *trampoline* as *“a loop that iteratively invokes thunk-returning functions (continuation-passing style). A single trampoline is sufficient to express all control transfers of a program; a program so expressed is trampolined, or in trampolined style; converting a program to trampolined style is trampolining. Trampolined functions can be used to implement tail-recursive function calls in stack-oriented programming languages.”*

That’s a mouthful! Trampolines are actually very easy to understand.

### A Simple Trampoline

Here’s a simple implementation of a trampoline:

function trampoline(f) { while (f && f instanceof Function) { f = f.apply(f.context, f.args); } return f; }

The trampoline takes a function and repeatedly executes the return value until a result other than a function is returned. One is tempted to use the trampoline like so:

function factorial(n) { function recur(n, acc) { if (n == 0) { return acc; } else { return recur(n-1, n*acc); } } return trampoline(recur(n, 1)); }

But this doesn’t produce the desired optimization. Why? Suppose *factorial* is invoked with **n=5**. What value is passed to the trampoline? It’s not what you expect.

`recur(5, 1)`

Is a function *expression* returning the value 120. The trampoline is invoked with the value 120—not at all what we intended! This is essentially the same tail call optimized implementation of factorial, except tail call optimization is unavailable in the JavaScript environment. What went wrong?

We intended to invoke trampoline with a function reference, not a function result. While the following would work

`return trampoline(Function() { recur(n, 1); });`

it’s unwieldy. We need a means for obtaining a reference to a function invocation, complete with all the parameters, so we can invoke the function at a later point in time. Though it wasn’t intended for this purpose the **Function.bind** function fits the bill nicely and thus improve our Factorial implementation:

function factorial(n) { function recur(n, acc) { if (n == 0) { return acc; } else { return recur(n-1, n*acc); } } return trampoline(recur.bind(null, n, 1)); }

Now we call trampoline with the expression

`recur.`

**bind**(**null**, n, 1))

The *bind* function is a function that when invoked returns the value of the calling function, in this case *recur*, using the specified calling context (the *this* pointer, which in this case is *null* since we’re not calling our function within an object instance), and the list of parameters. The result of recur(n, 1) is returned when this *bind* function is invoked. This is exactly what we intended to pass to the trampoline—a function!

This implementation is still not yet optimized, however. To see this suppose we invoke *factorial* with the value **n=5**. When the trampoline invokes the *bind* function returning the invocation of recur(5, 1) what result is returned? It’s not a function—instead it’s the result of recur(4, 5) which is 120. We only got one bounce.

This is easily fixed:

function factorial(n) { function recur(n, acc) { if (n == 0) { return acc; } else { return recur.bind(null, n-1, n*acc); } } return trampoline(recur.bind(null, n, 1)); }

Now the trampoline will provide the desired effect and will continue looping until recur returns the accumulated value.

### Mutual Recursion

Can mutually recursive functions be optimized? Consider the mutually recursive functions even/odd:

function even(n) { if (n == 0) { return true; } else { return odd(n-1); } } function odd(n) { if (n == 0) { return false; } else { return even(n-1); } }

Here’s a quick look at the execution of *even*:

**even(5)** → odd(4)

odd(4) → even(3)

even(3) → odd(2)

odd(2) → even(1)

even(1) → odd(0)

odd(0) → **false**

And another:

**even(6)** → odd(5)

odd(5) → even(4)

even(4) → odd(3)

odd(3) → even(2)

even(2) → odd(1)

odd(1) → even(0)

even(0) → **true**

One is tempted to write the following to benefit from the trampoline:

function even(n) { if (n == 0) { return true; } else { return trampoline(odd.bind(null, n-1)); } } function odd(n) { if (n == 0) { return false; } else { return trampoline(even.bind(null, n-1)); } }

Remember the intent of the trampoline was to replace recursive function invocations with a loop. This implementation does not achieve this. Instead the trampoline is recursively invoked. Use the following implementation instead:

function _even(n) { if (n == 0) { return true; } else { return _odd.bind(null, n-1); } } function _odd(n) { if (n == 0) { return false; } else { return _even.bind(null, n-1); } } function even(n) { return trampoline(_even.bind(null, n)); } function odd(n) { return trampoline(_odd.bind(null, n)); }

Now the implementation is appropriately optimized.

### Performance

The simplicity of the implementation of *even*/*odd* allow us to directly measure the performance of the trampoline and compare that performance to the recursive invocation.

This graph clearly shows trampolines are not an optimization—tail call optimization is still badly needed in the JavaScript environment. What this graph doesn’t show is that after 30,000 recursive invocations the browser hung; to the point it had to be forcibly shut down. Meanwhile the trampoline continued bouncing through hundreds of thousands of invocations. There are no practical limits to the number of bounces a trampoline can make.

Why does a trampoline not improve performance? A couple of observations should be made about this trampoline implementation:

- The number of function invocations is not reduced. The trampoline implementation has essentially the same number of function invocations as the traditional recursive implementation. A tail call optimization would eliminate these function invocations.
- We’ve traded the work of creating stack frames with creating function bindings. Both operations consume time and memory. Tail call optimization doesn’t create function references due to its modifying the function implementation in place to transform the recursive implementation to a loop.

### Conclusion

What can we conclude from this? Be skeptical of claims that trampolines improve performance. Demand proof.

Trampolines are still useful even without performance improvement. Your application will run correctly in all operating environments and you’ll encounter fewer hard-to-diagnose errors. Your code is also written to take advantage of tail call optimization when (if?) it’s provided by the JavaScript environment.

Happy hacking!

#### More to Explore

Functional JavaScript — Memoization, Part I

Functional JavaScript — Memoization, Part II

Functional JavaScript — Currying

Functional JavaScript — Tail Call Optimization and Babel

I’ve been using tail calls out of necessity in my projects for a while. In addition to `bind`, there are other approaches to save calls, so I created a jsperf looking at the relative performance of a few: http://jsperf.com/external-tail-calls/2

Good evidence for tail call not being an optimization in JavaScript, but a means for implementing recursive functions without exhausting the stack. Thanks for the analysis!

Matt, at the moment jsperf is down. Any chance that you can post your examples somewhere else, for example https://hyperdev.com ? Thank you.

Yeah JSPerf has been going somewhat downhill. Here’s the original post in which I discuss a few approaches to implement tail calls: http://blog.mattbierner.com/tail-call-implementation-and-defunctionalization-in-javascript/

Looking back at that post, there are certainly some other micro-optimizations that could be made to benefit various JS runtimes.

I would love to see an example using this on multi-dementional arrays or hashes. Pretty tough to find an example that’s not a factorial function.

here’s a more compact version which doesn’t use an ‘accumulation’ var, but still uses TCO:

function factorial(fn){

console.trace();

return function TC(n){

return n && (n * TC(n – 1)) || 1;

}

}

factorial(factorial)(10)

Hope this is helpful!

What do you have in mind?

Thanks for your analysis.

Here are two fast implementations, without trampolines.

Using standard JavaScript: http://glat.info/jscheck/tomrec_prod.html

Or introducing two new keywords: http://glat.info/js.metaret/

Pingback: Understanding Tail Recursion | CodeKraft

Pingback: Recursion in Functional JavaScript