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

function calls itself in the return statement, this adds on to the stack one more function call to

increment

and this call will again add on to the stack one more function call to

increment

and this keeps going on until it reaches the base condition, when

initialValue

becomes greater than

, but that never happens.

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

, you can call it anything you want.

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

in this case

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

as output. The above code took around 20 sec on a Macbook Air.

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

function, we got the definition of

enclose

function in

trampolinedIncrement

with

being the

increment

function. So now, when we call the

trampolinedIncrement

function with initial arguments, it calls

and the output of that execution is an anonymous function which is stored in the

result

. Then we keep on calling

result

function until it returns a

typeof

function and at the end will return the result.

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

. I find it pretty cool!

Cheers!

Have a Happy Day!

@heypran