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!
