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, { { (test > ) test; increment(++test);
  } { .log( , test);
  }
} ( ) function increment test try if 1000000 return return catch console "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 function calls itself in the return statement, this adds on to the stack one more function call to and this call will again add on to the stack one more function call to and this keeps going on until it reaches the base condition, when becomes greater than , but that never happens. 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, { { result = f(...args); ( result === ) {
      result = result();
    } result;
  };
} ( ) function trampoline f return ( ) function enclose ...args let while typeof "function" return The above trampoline function, takes a function as an argument and returns a function called , you can call it anything you want. enclose In order to use the above wrapper, we need to modify our recursive function a little bit. { { (test > ) test; increment(++test);
  } { .log( , test);
  }
} ( ) function increment test try if 1000000000 return return => () catch console "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 in this case increment Now, if we pass in the above function to our trampoline wrapper, our code will look like this. trampolinedIncrement = trampoline( { { (test > ) test; increment(++test);
  } { .log( , test);
  }
}); .log(trampolinedIncrement( )); const ( ) function increment test try if 1000000000 return return => () catch console "test===>" console 1 When you run the above code, there will be no range error, and you will get as output. The above code took around on a Macbook Air. 1000000001 20 sec But what just happened? Our code just got on a trampoline, LOL! Here is the whole code, { { result = f(...args); ( result === ) {
      result = result();
    } result;
  };
} trampolinedIncrement = trampoline( { { (test > ) test; increment(++test);
  } { .log( , test);
  }
}); .log(trampolinedIncrement( )); ( ) function trampoline f return ( ) function enclose ...args let while typeof "function" return const ( ) function increment test try if 1000000000 return return => () catch console "test===>" console 1 When we trampolined the function, we got the definition of function in with being the function. So now, when we call the function with initial arguments, it calls and the output of that execution is an anonymous function which is stored in the . Then we keep on calling function until it returns a function and at the end will return the result. 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 . I find it pretty cool! trampoline Cheers! Have a Happy Day! @heypran

Twitter

4 Must-Have Crypto Browser Extensions 

Typescript 3.9: What got changed?

Try new EVM Toolkit

On Recursion and Trampolining

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

4 Must-Have Crypto Browser Extensions

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

4 Must-Have Crypto Browser Extensions

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps