Adopting Memory Safe Recursion

First of all: what is recursion?

Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself.
Wikipedia

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 tree traversals as an example).

How does it look?

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

function factorial(num) {
  let result = 1;

  for(let i = 1; i < num; i++) {
    result *= i;
  }

  return result;
}

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?

function factorial(num) {
  return num === 0 ? 1 : num * factorial(num - 1);
}

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:

function fibo(num) {
  const arr = [0, 1];

  for (let i = 2; i < num; i++) {
    arr.push(arr[i - 2] + arr[i - 1]);
  }

  return arr [num];
}

Wow, that is not so simple at first sight!
And what about recursion?

function fibo(num) {
  return num < 2 ? num : fibo(n - 1) + fibo(num - 2);
}

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.
Haskell uses 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:

fibo :: Num a => [a]
fibo = 1:1:zipWith (+) fibo (tail fibo)

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

fibo(N) -> fibo(N, 0, 0, 0).

fibo(N, N, _, F) -> F;
fibo(N, 0, _, _) -> fibo(N, 1, 0, 1);
fibo(N, 1, _, _) -> fibo(N, 2, 1, 1);
fibo(N, Current, X, Y) -> fibo(N, Current + 1, Y, Y + X).

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

let fibo (n:int) :int =
  let rec loop (i:int) (a:int) (b:int) :int =
    if i = n then a
    else loop (i+1) (b) (a+b) in
  loop 0 0 1;;

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:

JavaScript Recursion Stack

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:

function tceFactorial(num) {
  function tce(num, res) {
    return num === 0 ? res : tce(num - 1, num * res);
  }
  return tce(num, 1);
}

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?

const trampoline = fn => (...args) => {
  let result = fn(...args);

  while (typeof result === "function") {
    result = result();
  }

  return result;
}

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

function trampolinedFactorial(num) {

  function factorial(acc, num) {
    return num === 0 ? acc : () => factorial(acc * num, num - 1);
  }

  function trampoline = fn => (...args) => {
    let result = fn(...args);

    while (typeof result === "function") {
      result = result();
    }

    return result;
  }

  return trampoline(factorial(1, num));

}

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:

Execution time, lower is better (benchmark source)Execution time, lower is better (benchmark source)

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!

Did you like this article? Consider becoming a Patron!

This article is CC0 1.0 (Public Domain) licensed.