Adopting Memory Safe Recursion in JavaScript

First of all: what is recursion?

Thank you Wikipedia! But why is it useful?

• Sometimes, recursive code may be more readable than the iterative one.
• Even if not as efficient as imperative iterations, sometimes recursion is worth it. Code is more testable, easy to debug and to extend.
• In some programming languages, there are no loops , so recursion is all you have! (Haskell, Elixir, Elm, I’m talking to you!)
• There are certain things that are harder to implement using loops (binary traversals as an example).

How does it look?

Ok so let’s implement a simple factorial in JavaScript using for loops (iteration):

Iterative solution

Ok great! Even if we don’t know what a factorial is, we can understand it by reading this simple code. It’s the product of all the numbers between 1 and a a given number N .

But how does it look adopting a recursive solution?

Recursive solution

Wow, one-line solution! Please note how the factorial function invokes itself in its function body.

Of course, at first it may seems a little harder to understand, but you’ll get used to.

Let’s see another great example: the Fibonacci Sequence :

Iterative Solution

Wow, that is not so simple at first sight!

And what about recursion?

Recursive Solution

Soooo easy to read! Recursive solution is written in a declarative way, so it describes its output instead of how to obtain it. This helps a lot when a new colleague needs to read your code!

The problem with recursion

This article actually is not meant to teach you what recursion is.

Instead, it should provide you a simple way to handle the biggest problem of recursion: memory usage .

There are some languages who were born with recursion in mind.

Haskelluses lazy evaluation to treat a given value only when is needed, so it will not affect application’s memory usage until it’s strictly required:

Using lazy evaluation and tail call optimization with recursion in Haskell

Elixirand Erlang provides tail call optimization ( TCO ) to optimize once again memory usage:

Using tail call optimization in Erlang

OCamlprovides TCO using the rec keyword when you need to implement a recursive method:

Using tail call optimization in OCaml

All the examples above will allow you to spawn the fibo function against incredibly big numbers without having loss of performances or stack overflows.

In JavaScript, you’ll just get the following error:

Uncaught RangeError: Maximum call stack size exceeded

Everytime the fibo function is recursively called, the JavaScript interpreter creates and stacks an execution context.

So, let’s take the recursive factorial we discussed above (simpler example), and let’s see how does the execution context look when calculating the factorial of 3 :

So as you can see, all the magenta zones in the graph above won’t be garbage collected until we reach our exit condition .

Of course, not a big deal while calculating the factorial of 3 … but what if we want to calculate the factorial of 100000 ? How many contexts will be stacked? How far can we go before getting a stack overflow error?

Tail Call Elimination

Implementing Tail Call Elimination in our factorial function, will ensure that we won’t add a new stack frame to the call stack everytime we adopt recursion:

So as you can see, it only wraps the factorial function body inside a tce method, then uses it to calculate recursively the resulting value.

This shrewdness will allow you to adopt large recursive methods!

Trampolines

Another way to adopt memory safe recursion in JavaScript are trampolines .

As used in some Lisp implementations, a trampoline is a loop that iteratively invokes thunk-returning functions (continuation-passing style). A single trampoline suffices 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.

( Wikipedia )

Thank you again Wikipedia, but how does it really look like?

So let’s rewrite our factorial function using a trampoline:

Et voilà! Memory safe recursion in JavaScript!

About performances

As written before, recursion is not as efficient as loops.

So, here you are some benchmarks:

Trampoline: 871ms

Tail Call Elimination: 343ms

Unsafe Recursion: 230ms

Iteration: 43ms

Benchmark source

So as you can see, recursion is not the most efficient solution, but it can really help while working on complex data structures such as graphs or binary trees.

Sometimes, its worth to sacrifice a bit of performance for a better developer experience (dear old Assembly, you know what I mean)!

Recursion also helps you to eliminate side-effects, so code flow will be clearer and more testable. It’s absolutely not about performances!

See you next week with a new episode of Js Monday!