A Basic Recursion Example in ES6

First of all, what is recursion? Recursion is basically a programming concept, and a different way of thinking problem. More precisely, it is a function that repeating calling itself until it reaches exit condition. Most loops can be rewritten into a recursive style in JavaScript, and all recursive function can be rewritten into a iterative version.


Example in JS:
Lets say we want to write a function that reverse a input string without using .split( ).reverse().join( ). In an iterative version, we can:

var reverse = (input) => {
let result = "";
for (let i = input.length - 1; i >= 0; i--) {
result += input[i];
}
return result;
}

so we want to start at the last position of the string, and counting backwards such that we combine them from last to first. Now in recursion version:

let reverse = (input) => {
if (input === "") {
return "";
} //base case
return reverse(input.slice(1)) + input[0];
}

Do you found it more readable? Recursion is good at making complex loops shorter and easily to understand.

There are two rules in recursion

1. In every recursion, there will always be if statement that looks like example above, which we call it a base case (there can be more than one base case). In base case, we normally checks a condition where the simplest answer is known, in order for us to terminate the recursion to prevent infinite loop. In this case we checking if the input is empty or not, and reverse empty string gives us back “empty result”.

2. We always want to work our way towards the base case when we recalling the function. In this case, we slice the first letter of the input string and then add it at back, so we eventually wants to reduce the input string to empty — which will enters the base case.

Recursion performance

Let try to reverse the string “friday” using the recursive reverse(). This is what happening behind the scene:

The problem is that each state of reverse() are pushed into call-stack, which takes memory, and also more run-time when resuming them one by one with each contact operations after the exit condition, this would be a bad implementation when the input string is extremely long comparing to the iterative version.

Tail Call Optimization in ES6

TCO is basically a technique for optimize the call-stack without all the unnecessary stack frames when using recursion. It has not been fully supported to JavaScript prior to ES6. To use TCO, we have to modify our recursive reverse() function like this:

let reverse = (input, acc) => {
if (input === "") {
return (acc||"");
}
return reverse(input.slice(1), input[0] + (acc||""));
}

we now pass a second parameter as an accumulator, what happens now when we reverse “friday”:

Notice that we don’t have to perform any concatenations anymore but only save the result! (in other words, resuming only takes O(1) constant time); This is more feasible than previous example when it comes with extremely long input string, since we are now only saving the results without any operations for concatenate them one by one. By using constant stack space, we can prevent the“maximum call stack size exceeded” error in ES6 with TCO.

Another great example with factorial numbers using TCO :


Summary

Recursion makes function easier to read, but usually cost more to perform. Tail Call Optimization helps us to make recursion more efficient. In conclusion, recursion is best applied in traversing data structures (e.g. tree), recursion doesn’t play an important role in front-end comparing to back-end. However, it is an important concept worth knowing as it deepens our understanding of every single steps inside function.

Reference:
http://pages.cs.wisc.edu/~vernon/cs367/notes/6.RECURSION.html#iter
https://en.wikipedia.org/wiki/Tail_call