On Recursion and Trampolining

Did you know that recursion can be optimized using a concept which works similar to the way how we jump on a trampoline.

Let me elaborate, in recursion a function calls itself without finishing its own execution. As execution cannot be finished until the next function call returns (or finished execution) and this goes on for further function calls. This creates a stack of unfinished function calls and due to memory constraints there can only be a certain limit of function calls allowed in a stack. But situations with a large number of recursion calls in javascript does not lead to stack overflow, javascript prevents from reaching that limit by throwing a range error.

Consider this example,

function increment(test) {
  try {
    if (test > 1000000) return test;

    return increment(++test);
  } catch {
    console.log("test===>", test);
  }
}

If you run the above code, it will go into the catch block pretty soon. On a macbook air 2k19, it maxed out around 10K. That means there was a stack overflow.

Well in the above example the

increment 

increment

increment

initialValue

1000000

But here if you notice that recursion call is a tail call. A tail call is when a recursion call only happens at the end of the function in a return statement.

Why do we need to concern ourselves with the tail call and how does it matter?

The trampoline technique that we are about to learn only works when we have recursion defined as a tail call. This will become more clear once we look at the trampoline, let's hop on to it.

'Tramploine of recursion' is given by Kyle Simpson. A trampoline is nothing but a wrapper around our recursive function. In recursion, we call a function from within a function. In a trampolined recursion, we call a function that in turn returns a function ( not a function call & therefore completing the current function execution) and this returned function again calls our recursive function.

That is a bit confusing, I know but read it again I am sure you will get it. Here's how the trampoline wrapper looks like,

function trampoline(f) {
  return function enclose(...args) {
    let result = f(...args);
    while (typeof result === "function") {
      result = result();
    }
    return result;
  };
}

The above trampoline function, takes a function as an argument and returns a function called

enclose

In order to use the above wrapper, we need to modify our recursive function a little bit.

function increment(test) {
  try {
    if (test > 1000000000) return test;

    return () => increment(++test);
  } catch {
    console.log("test===>", test);
  }
}

Did you notice the difference, we modified our tail call by returning an anonymous function instead. So that its not a function call anymore, but it returns a function that calls our recursive function which is

increment

Now, if we pass in the above function to our trampoline wrapper, our code will look like this.

const trampolinedIncrement = trampoline(function increment(test) {
  try {
    if (test > 1000000000) return test;

    return () => increment(++test);
  } catch {
    console.log("test===>", test);
  }
});

console.log(trampolinedIncrement(1));

When you run the above code, there will be no range error, and you will get

1000000001

But what just happened?

Our code just got on a trampoline, LOL! Here is the whole code,

function trampoline(f) {
  return function enclose(...args) {
    let result = f(...args);
    while (typeof result === "function") {
      result = result();
    }
    return result;
  };
}

const trampolinedIncrement = trampoline(function increment(test) {
  try {
    if (test > 1000000000) return test;

    return () => increment(++test);
  } catch {
    console.log("test===>", test);
  }
});

console.log(trampolinedIncrement(1));

When we trampolined the

increment

enclose

trampolinedIncrement

f

increment

trampolinedIncrement

f

result

result

typeof

If you are still confused just ask in the comments, I will clarify. You can reach out to me on twitter on @heypran

Just to wrap it up, in a normal recursion the stack size keeps on increasing because the current function call has not finished its execution and yet it calls another function. This function again calls another function and this keeps on repeating. This leads to stack overflow.

In a trampolined scenario, we are not calling the recursive function directly, instead we are finishing the current function call by returning a function, that in turn calls our recursive function. This makes our stack size always increase only by one and when it finishes it again reduces by one. This jumping between the functions is referred as

trampoline

Cheers!

Have a Happy Day!

@heypran