Using trampolines to manage large recursive loops in JavaScript

I vividly remember my entrance into the world of functional programming. Ironically, I was learning about class-based JavaScript in ES5. I was assigned some homework meant to reinforce the OOP concepts taught. However, a full-blown class-based OOP implementation was overkill for the type of problem that was assigned as homework, so I decided to do the whole thing in pure functions.

I’m so thankful that I had good teachers while learning to program — rather than killing the spark that inspired me to do that assignment in a functional style, they encouraged me to dive deeper into functional programming (FP).

Since those first baby steps into the FP world, I’ve directly seen the benefits of adopting a functional style for JavaScript. Especially after diving into things like React, Redux, & RxJS — each of these make FP more and more common as they’re used in numerous applications across the web. However, it’s difficult to wade very far into the FP waters before you come up against this thing called recursion.

Recursion

First off, let’s do a quick review of what recursion looks like. For the purposes of this article, we’ll use a simple function called sumBelow — which takes a number and returns the sum of the number plus all numbers below it. For example, if I were to call sumBelow(5), I’d get 15 (5 + 4 + 3 + 2 + 1 = 15).

If we were to write this function in a classic iterative fashion it would look something like this:

// iterative way
const sumBelow = number => {
  let result = 0
for(let i = 0; i <= number; i++) {
    result += i
  }
  return result
}

And in recursive fashion, the function would look like this:

// the recursive way
const sumBelow = (number, sum = 0) => (
  number === 0 
    ? sum
    : sumBelow(number - 1, sum + number)
)

The “secret sauce” to recursion lies at the end of our sumBelow function, where we call sumBelow from within sumBelow. When we do this, the function continues to call itself until it produces a value. Then it trickles that value all the way back up to the first function call.

In many cases, recursion can lead to more declarative, self-descriptive code — you’re not explaining how you get the value as with iterative code, you’re describing what the final result of the function should be. In addition, recursion allows you to maintain immutability inside of your functions (after all, mutable state is the source of many bugs), and often results in less code.

Of course, our example is tiny, but as your programs grow in size and scope using recursion wisely can help with keeping things simple.

Disclaimer: this is not an article about recursive vs. iterative styles. Both have their merits, and sometimes a recursive solution will not be as clean as its iterative counterpart.

The problem with recursion

In functional languages (like Elm, Elixir, Haskell, etc), it is impossible to do imperative loops, so the only option is recursion. Since recursion is built into the language, the compiler will often make optimizations to guarantee that the call stack isn’t exceeded when processing large datasets.

However, in JavaScript we don’t get those optimizations by default. This means that when we have a recursive function we could actually crash the JavaScript engine!

For example, let’s take out sumBelow function above. If we were to call it with a really big number, what do you think will happen?

sumBelow(100000);
// Uncaught RangeError: Maximum call stack size exceeded

The recursive function keeps adding entries to the JavaScript engines call stack until there’s no more room, and then we get an error (if you want to read a bit more about how the call stack works, feel free to check out this article).

Not exactly a reliable solution if you want your programs to scale. This might be enough to convince people that iterative loops are the only way to go. However, there are some alternative ways to get the readability benefits of recursion without the performance costs.

---

Optimizing with proper tail calls

One way to avoid blowing up the call stack is to use proper tail calls — these were added in the ES2015 spec. In order to use proper tail calls (PTC), a function satisfy the following conditions:

1. You must be in use strict mode.
2. The recursive function call must be in tail position — that is, it is the very last thing to be evaluated before the return statement. For a detailed overview of what constitutes tail position, there’s a really nice dive into that in in this post.

The cool thing with PTC is that if you’re writing your recursive functions already with proper tail calls, you don’t have to change any code! For instance, our sumBelow function is already written with a proper tail call, so all we would have to do is run it in an environment that supports proper tail calls.

The catch is proper tail calls has spotty support at best. Look at the support chart from kangax.github.io.

At the time of writing, Safari is the only browser to have shipped PTC. Node implemented tail calls in version 6.5, but it was hidden behind a flag (later they removed support for PTC altogether in Node 8).

With browser support like that we can hardly hedge our bets on PTC if we want to use recursion for the time being.

A simple, non-disruptive option: Trampolines

I recently just finished reading Functional Light JavaScript by Kyle Simpson. It’s a wonderful, pragmatic dive into functional programming in JavaScript. It was Kyle’s chapter on recursion that introduced me to using trampolines to manage large recursive loops.

A trampoline function basically wraps our recursive function in a loop. Under the hood, it calls the recursive function piece by piece until it no longer produces recursive calls.

const trampoline = fn => (...args) => {
  let result = fn(...args)
  while (typeof result === 'function') {
    result = result()
  }
  return result
}

What’s happening under the hood of this trampoline function? It takes a function (fn) as its argument—this is the recursive function it is going to wrap—and returns a new function. Within this new function, the recursive function is called. We keep the loop running as long as fn returns another function. Once fn resolves into a value, we stop running the loop and return the value.

We have to slightly modify our recursive function in order to be used by the trampoline function. All we have to do is add an anonymous function to the recursive portion. That way it returns a function and can be managed by the while loop of the trampoline function. (I’ve bolded it in the code snippet).

const sumBelowRec = (number, sum = 0) => (
  number === 0
    ? sum
    : () => sumBelowRec(number - 1, sum + number)
)

Since our recursive function now returns a new function without actually calling itself yet, we get to control when the next call to sumBelowRecursive happens inside our trampoline function. This allows us to continue calling sumBelowRec without blowing up the call stack.

The last step is to wrap sumBelowRec inside of our trampoline function.

const sumBelow = trampoline(sumBelowRec)
sumBelow(100000)
// returns 5000050000 🎉🎉🎉

As one of my side projects I’ve been working through Project Euler in JavaScript. I’ve greatly enjoyed trampolines to handle some of the large number-crunching problems — it’s helped me come up far more declarative solutions than relying on iterative loops.

While some have warned that trampolines can incur a performance overhead and impact readability negatively, I think that the benefits outweigh the costs.

In my own performance profiling I found that the overhead from using the trampoline wasn’t nearly as large as I thought it would be. There’s no question about it — the trampoline is slower than an iterative loop. However, in many cases where a recursive solution can be cleaner and less error-prone, the performance overhead may be worth the readability benefits.

In addition, while we do need to modify our function to work in the trampoline context, the change is fairly non-intrusive. Like any new concept, readability is a little harder at first until you get used to writing and reading code that uses trampolines.

If you’re trying to adopt a functional style in JavaScript, having trampolines is a must for managing those difficult edge cases where you’re working on large datasets.