Overview
A guide to recursion for those who want to know in what cases recursion might be useful & how it could be applied IRL.
No Big O, algorithms, Fibonacci, word reversing, exponents, or other arbitrary CS topics. I promise.
Sorry, no TL;DR.
Unless you did a computer science course in university, recursion might be one of those concepts that you heard of but never had time to finally find out how that could be useful to you.
It also just happens so, that in modern day-to-day web development, there seem to be quite a few cases where recursion is the only possible solution to a particular problem.
Nevertheless, recursion is an exciting topic that might provide you with several important insights & even change the way you think about programming problems.
So, yes! That's a brilliant idea to finally understand the recursion.
Intro
Recursion is 1 of just 2 ways to repeat a process in computer programs.
The second way is called "iteration" & you are most probably already pretty familiar with this one. For instance, for & while loops, Array.prototype.map and Array.prototype.forEach are great examples of how iteration works.
The idea of iteration is simple - go a step at a time and repeat whatever procedure you are provided with on each step.
Let's see an example:
// A magical structure that repeats whatever
// we need to repeat an arbitrary number of times
// ⬇️
for (let i = 0; i <= 10; i++) {
console.log(i); // ⬅️ procedure to repeat
}
However, how does the for loop works under the hood?
What if for whatever reason we would be about to write our own forLoop function without using for, do...while, while or any other built-in loop?
As for now, we don't have any tools to do this, hence, this task would only result in a mental block & might seem to be impossible, but hold on! It is possible since we've got 2 ways to repeat a process.
The mental model I find very helpful is the following:
Recursion is no more than an alternative, more flexible way to repeat a process without writing a loop.
Recursion
One of the primary mental blocks I had in understanding recursion was that it doesn't have any available APIs/special language constructs/built-in functions.
In the case of iteration, we have loops of all flavours but in the case of recursion, we aren't provided with any built-in solutions. We have to implement it from scratch.
That might be a blocker for learning, but ultimately this is exactly what makes recursion useful because it gives us total control over when, why & how repetition is performed.
Let's see some examples! First off, let's console.log numbers from 0 to 10, exactly the same as we did above with for loop but recursively this time:
const printNumbersUpTo10 = (num = 0) => { // #1 for (let i = 0;
if (num <= 10) { // #2 i <= 10;
console.log(num); // ⬅️ procedure to repeat
printNumbersUpTo10(num + 1); // #3 i++)
}
};
printNumbersUpTo10();
There might be some surprising parts (we'll get to them later) but let's first concentrate on similarities between recursive & iterative approaches.
Similarities with iteration
I mapped lines of recursive printNumbersUpTo10 function to equivalent parts of for loop, let's see them step by step:
- On line
#1we declare a variable that we will increment on eachiterationstep. So, this line is equivalent to:
for (
let i = 0; // ⬅️
i <= 10;
i++
) { console.log(i); }
- On line
#2we set a condition that will check on eachiterationstep whether we are already done or there are more steps to perform. In recursive functions this condition has a special name, it's called "base case". So, this line is equivalent to:
for (
let i = 0;
i <= 10; // ⬅️
i++
) { console.log(i); }
- On line
#3we increment our counter variable. So, this line is equivalent to:
for (
let i = 0;
i <= 10;
i++ // ⬅️
) { console.log(i); }
In spite of having a lot in common, recursion & iteration differ in several important aspects. To understand those differences, let's discuss in detail how recursion works.
How does recursion work?
From any JavaScript engine's point of view, recursion is simply a situation when a function calls itself.
To see what this means, let's refactor our printNumbersUpTo10 function from the previous example. Let's say we decided that printNumbersUpTo10 is too specific, so, we want a more generic printNumbersUpTo function that will accept 1 argument - the highest number it should print.
So, when we will call printNumbersUpTo(5) it should console.log numbers from 0 to 5.
Our first attempt to implement this could look something like this:
const printNumbersUpTo = (num) => {
if (num >= 0) {
console.log(num);
printNumbersUpTo(num - 1); // ⬅️ this line makes it tick
}
};
printNumbersUpTo(5); // ➡️ logs 5, 4, 3, 2, 1, 0
However, we've got a couple of problems here:
- Numbers are printed 5 to 0 instead of 0 to 5.
- We have to make an additional unnecessary step just to print 0 because our
console.logstatement is placed next toprintNumbersUpTocall which makesprintNumbersUpTocall itself one additional time whennumis 0 (-1 is not logged because it fails the check inside theifstatement).
Let's try to get rid of both problems. A better solution could be something like this:
const printNumbersUpTo = (num) => {
if (num > 0) {
printNumbersUpTo(num - 1);
}
console.log(num);
};
printNumbersUpTo(5); // ➡️ logs 0, 1, 2, 3, 4, 5
Did you notice how moving console.log below the printNumbersUpTo(num - 1) call changed the logging sequence from 5 ➡️ 0 to 0 ➡️ 5?
It worked this way because when a JS compiler gets to printNumbersUpTo(num - 1) it starts executing it straight away, then it sees printNumbersUpTo(num - 1) again and starts executing it, and so on.
As a result, the compiler first goes all the way in to the call where num finally equals 0. When num is 0, the condition inside of the if statement is false, so, the if statement is skipped & the console.log is executed.
There's nothing after console.log, so the compiler finishes with the innermost function & then starts to get back out to the outermost scope.
You can see a visualization of this process using a wonderful tool called "Loupe" built by Philip Roberts. Here is the preview:
To make it even clearer, let's replace each recursive printNumbersUpTo(num - 1) call with the content of the printNumbersUpTo function in order to visualize how a JS compiler sees & executes it.
This is what recursion looks like:
const printNumbersUpToVisualized = (num) => {
if (num > 0) {
if ((num - 1) > 0) {
if ((num - 1 - 1) > 0) {
if ((num - 1 - 1 - 1) > 0) {
if ((num - 1 - 1 - 1 - 1) > 0) {
if ((num - 1 - 1 - 1 - 1 - 1) > 0) {
// this is never executed since
// num is already 0 here and the
// condition is false
}
console.log(num - 1 - 1 - 1 - 1 - 1);
}
console.log(num - 1 - 1 - 1 - 1);
}
console.log(num - 1 - 1 - 1);
}
console.log(num - 1 - 1);
}
console.log(num - 1);
}
console.log(num);
};
printNumbersUpToVisualized(5);
The 2 most important ideas here are:
- Recursion is about stacking up function calls on top of each other until the desired condition is met.
- The order of execution is important and with recursion, we have complete control over it.
How recursion is different from iteration?
Due to the fact that we completely control the order of execution (since we can place recursive calls anywhere), the recursive approach allows more flexibility & let us do things that are hard to achieve using loops.
For instance, let's take a quick look at this example:
const mirrorNumbersUpTo = (num) => {
console.log(num);
if (num > 0) {
mirrorNumbersUpTo(num - 1);
console.log(num);
}
};
mirrorNumbersUpTo(5); // ➡️ logs 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5
We modified printNumbersUpTo just a slight bit in order to make it mirror numbers. Even in this simple case, it'd be more problematic to implement this same functionality inside a for loop.
In fact, mirrorNumbersUpTo is equivalent to a loop that first decrements the number down to 0 (for (let i = 5; 0 <= i; i--)) and then increments a variable from 1 until it equals the initially provided value (for (let i = 1; i <= 5; i++)).
At this point, one could say:
Ok, wonderful, but is there a single real-world scenario in which a programmer is not satisfied with the way a
forloop runs?
Let's see!
Practical use cases
1. Normalizing arbitrary data structures
In modern JS we have something called Array.prototype.flat which is a function that can flatten nested arrays given how deep a nested array structure should be flattened.
While it's valid to call it like this:
nestedArrays.flat(Infinity);
in order to flatten an array completely (so, it contains no nested arrays), it is considered a bad practice to do so.
So, a possible workaround might look like this tiny recursive function adapted from one of the examples on MDN site:
const flatToBase = array => array.reduce(
(accumulator, value) => accumulator.concat(
Array.isArray(value) ? flatToBase(value) : value
),
[],
);
flatToBase([[[[[[[ 42 ]]]], 36]]]); // -> [ 42, 36 ]
2. Traversing arbitrary data structures
Let's say we're building a browser extension that collects & shows some general statistics about the current HTML page.
For instance, we want to show our users how many HTML tags of each type we have on the current page, how deep the average tag is located, what is the most deeply located tag and so on.
In order to achieve this, we will obviously need to traverse the entire DOM structure element by element. If we try to use iteration to achieve this task, things get hard from the start. As the first step we could get all children of an element, for instance with something like this:
const bodyChildren = [...document.body.children];
for (let i = 0; i < bodyChildren.length; i++) {
// So... how do we get children of each body child?
analyseElement(bodyChildren[i]);
}
But what do we do after we have iterated over each direct child of body? Each direct child might have children as well, its children might have children and so on. We will not be able to write enough loops.
In situations like this, when the data structure we're working on is not known beforehand or is simply too nested, recursion is frequently the only approach we can use. So, let's do a quick prototype of the function that will recursively traverse all HTML elements on the page.
In this example, we are not going to analyse elements in any way, just traverse all of them & stringify the DOM structure in order to see that our function works fine.
const traverseHtmlElement = (rootElement, _level = 0) => {
// Get all element's children stringified if any
let rootChildren = '';
if (rootElement.childElementCount) {
rootChildren = traverseHtmlElement(rootElement.firstElementChild, _level + 1);
}
// Get all element's siblings stringified if any
let rootSiblings = '';
const nextSibling = rootElement.nextElementSibling;
if (nextSibling) {
rootSiblings = traverseHtmlElement(nextSibling, _level);
}
// The recursive part is already done above. All code
// below is just to print HTML structure in a pretty way.
const ident = ' '.repeat(_level);
const tagName = rootElement.tagName.toLowerCase();
const id = rootElement.getAttribute('id');
const classList = rootElement.classList.toString();
const rootId = id ? ` id="${id}"` : '';
const rootClasses = classList ? ` class="${classList}"` : '';
// Assemble tags with no children
if (!rootChildren) {
return ''.concat(
ident,
'<',
tagName,
rootId,
rootClasses,
' />',
'\n',
rootSiblings,
);
}
// Assemble tags with children
return ''.concat(
ident,
'<',
tagName,
rootId,
rootClasses,
'>',
'\n',
rootChildren,
ident,
`</${tagName}>`,
'\n',
rootSiblings,
);
};
const stringifiedHTML = traverseHtmlElement(document.body);
console.log(stringifiedHTML);
3. Processing data structures of arbitrary depth
Let's say we are building a web forum where people could discuss things, post images & leave comments about nearly anything they wish.
Frequently forums don't put any restrictions on conversations' depth, which basically means that any comment might have a sub-comment that might have a sub-comment that might have yet another sub-comment & so on. The simplified data structure that we receive from BE would look something like this:
const comments = [
{
text: 'comment 1',
comments: [
{
text: 'comment 2',
comments: [],
},
],
},
{
text: 'comment 3',
comments: [
{
text: 'comment 4',
comments: [],
},
{
text: 'comment 5',
comments: [{
text: 'comment 6',
comments: [{
text: 'comment 7',
comments: [
{
text: 'comment 8',
comments: [],
},
{
text: 'comment 9',
comments: [],
}
],
}],
}]
},
{
text: 'comment 10',
comments: [],
},
],
},
];
Let's prove we can print it prettily using recursion:
printComment function from the example above is fairly similar to traverseHtmlElement, you could notice that all the children/sibling wording already sounds pretty familiar. That's no surprise since those 2 functions do almost the same thing.
Did you notice that small getArrayIterator generator function that we used as a helper?
I used it because unlike DOM elements that have the nextElementSibling property, arrays don't provide a way to go to the next element from the current one.
In order to avoid reinventing the wheel, we can use generators that provide a very handy way to go to the next step & define whether the iteration is already done or not within a recursive function.
4. Arbitrary depth currying
This example is heavily inspired by an awesome article on amazing javascript.info. If you've never heard of it, I'd strongly recommend you to check it out.
For the sake of simplicity, we will write a pretty simple sum function. I must admit that, unlike other examples, this example can barely be useful IRL even theoretically, however, the concept it demonstrates is too interesting to omit.
Let's consider that we want to create a function called sum that sums up all numbers we feed it. Sounds trivial, however, we want our function to work with pretty much any call signature, so, all these signatures must be valid:
sum();
sum(1, 1)();
sum(1)(5)(12)();
sum(1)(132, 4)();
sum(1, 2, 3)(7, 8, 9)(5)();
sum(1, 1)(4)(6, 13, 7)(2)(3)(2)(2, 1)();
It turns out that we can solve this puzzle with recursion quite easily. The trick is to apply it a little bit differently this time.
The implementation could look something like this:
The most interesting part here is that sumOnce returns itself without invoking itself as long as any argument is supplied.
This makes sumOnce a recursive function despite the fact that the invocation part is now delegated to users of this function.
5. Creating a higher-level abstraction
Sometimes, the iterative approach might help to abstract things out making code cleaner, more organized & easier to use.
For instance, let's say that we are building a colour wheel, just like this one that I have found on canva.com.
In order to make our colour wheel work, we'll need to calculate what colours do we have in order to render them. Since we know that on the Web we use the RGB colour scheme, we are able to say that we have 256 * 256 * 256 colours available (which is about 17 million colours!), so it looks like our colour wheel is going to be really huge.
However, today, the design is not our primary concern. The main question now is:
How do we calculate all possible combinations of three numbers in the range from 0 to 255?
Thanks to this brilliant answer on math.stackexchange.com we now know that it's relatively easy to calculate all possible combinations using nested for loops.
Let's do a quick test to make sure it really works. We are going to calculate all combinations that can give us 2 numbers in the 0 - 1 range.
out = [];
for (let i = 0; i < 2; i++) {
for (let j = 0; j < 2; j++) {
out.push([ i, j ]);
}
}
console.log(out); // -> [[ 0, 0 ], [ 0, 1 ], [ 1, 0 ], [ 1, 1 ]]
It works! So, in our case, luckily, we'll need just 3 nested loops.
However, what if we would like to have a more generic function that could calculate all possible combinations for any set of numbers?
Well, one option would be to create for loops recursively.
Let's create such a function & see it in action!
If you inspect the screen above, you'll find out that it's made up of 10x10 divs and each div on the screen has a unique colour.
Those colours are calculated automatically by findAllNumericCombinations that generates exactly the needed number of nested loops to calculate all possible combinations of a given set of ranges.
As you can see, only a few (particularly, 2304) colours are printed out. That's because printing out all 17 million would probably make your browser strongly dislike particular shades of orange :)
Iteration + Recursion = ❤️
Now when you feel more comfortable with recursion, it's time to clarify that you don't necessarily need to stick to one or another.
Iteration & recursion are not contradicting programming paradigms, not red & blue Matrix pills. Their light swords are of different colours but both are true Jedis!
Jokes apart, sometimes it's quite convenient to mix both in order to get the desired result.
You might already notice in previous examples that recursion & iteration might work quite well together.
Let's see yet another example of such a synergy. Let's say we have an array that has a very misfortune structure and looks like this:
const nestedNumbers = [
[[0], [[[[[[[1, 2]]]]]]], [3]],
[[[4], [[5]]], [[[6, 7, 8]]]],
[9]
];
The bad news is that it can only come in this form from the server, so, we must deal with it.
The good news is that it always strictly follows the following rule:
Any array contains either other array(/s) or number(/s).
Let's say we want to increment each number in this array by 1 leaving the structure in exactly the same state as it came from the server.
We'll have to use recursion since arrays that contain numbers might be nested at an arbitrary depth, so, we don't know beforehand how many iterations it will take to get to them.
However, once we found an array that contains several numbers, how do we make our recursive function go through each number in the array?
While we could implement this logic using recursion, it's not that fun to keep track of pointers position inside arrays.
Shall we re-invent the wheel at all? Recursion is great at processing repetitive data structures while iteration is great at looping through arrays. So, there's no good reason to limit our toolbox to just one thing or another.
Let's try to get the best out of the two worlds:
// Fetched from server
const nestedNumbers = [
[[0], [[[[[[[1, 2]]]]]]], [3]],
[[[4], [[5]]], [[[6, 7, 8]]]],
[9]
];
const incrementNestedNumbers = (arrayWithNums) => {
for (let i = 0; i < arrayWithNums.length; i++) {
if (Array.isArray(arrayWithNums[i])) { // if array
incrementNestedNumbers(arrayWithNums[i]);
} else { // if number
arrayWithNums[i] = arrayWithNums[i] + 1;
}
}
};
incrementNestedNumbers(nestedNumbers);
/* nestedNumbers now look like this:
[[1], [[[[[[[2, 3]]]]]]], [4]],
[[[5], [[6]]], [[[7, 8, 9]]]],
[10]
*/
Wonderful, isn't it? We use recursion to find all nested arrays & iteration to actually loop through them while both of our tools seem to enjoy working shoulder to shoulder.
Some people will surely argue that this type of code can easily cause memory leaks & performance problems, however, from the practical point of view, if you understand what you are doing & test it well before using it in production, it will unlikely produce any undesired effects.
Conclusion
- Recursion is not that difficult to understand.
- Recursion can be very useful for certain tasks, sometimes, it is the only way to achieve the desired result.
- Recursion might give you the power to abstract things that could not be abstracted without it.
- Recursion has its cons, most famous being that it can lead to an infinite loop or memory leaks too easily in some cases.
- There's no good reason why one should avoid learning about recursion or using it when it fits.
- Recursion is unlikely a tool that you will use every single day, however, it is a very valuable tool because it helps you think about programming problems in a broader & more structured way.
- Recursion pops-up in tech interviews quite frequently.
- Recursion & iteration might work well together, don't limit your toolbox by forcing yourself to choose just 1 of 2 available tools.
I hope this article helped you to understand recursion a little better & you enjoyed it!
Oldest comments (0)