Recursion
Recursion is one of the classic topics of capital-C Computer Science. When you learn about recursion, you find articles that use the Fibonacci sequence as a first example and feature stock images of self-similarity and the sequence in nature, like the Romanesco broccoli. Fractals are cool, and teaching Fibonacci first reflects the conjoined CS & Math programs at many colleges.
But that technique never worked for me. I understood it well enough to pass tests, but when I needed to use recursion as a way of getting things done, I didn’t know where to start.
So, here’s how I stopped being afraid of recursion. If you hesitate before recursing, I hope this explanation is useful for you too.
Loops and recursion are both ways of running the same section of code more than once
If you’ve written code before, it’s likely that you’ve encountered a loop. Loops are usually written with a keyword like for, foreach, or while. Different languages and data structures have slightly different ways of saying “run this code more than once”, but all of them achieve the same goal.
for (var i = 0; i < 10; i = i + 1) {
console.log('I have been run ' + i + ' times');
}
for loops are the most formal kind, requiring three different statements:
for (initialization; condition; afterthought)
var i = 0: How to start, called the initialization. This runs once, just when the loop starts.i < 10: Whether to stop, called the condition. This is tested every time that the loop loops, and ifiis a number that’s greater than 10, the loop is done.i = i + 1: How to keep going, technically called the afterthought. ‘Afterthought’ is an especially bad name for this part, and it’s often enough an increment operation, like++, that many people call this the increment instead.
Okay: so as I said earlier, loops and recursion are both ways to run the same code more than once. They’ll share #2 and #3: both for loops and recursion need some way to tell whether they’ve finished their business, and how to continue running if they haven’t.
for is a keyword that tells the computer to repeat a section of code. Recursion uses functions to do the same thing.[1]
Recursion is when a function calls itself
function run(i) {
if (i < 10) {
console.log('I have been run ' + i + ' times');
run(i + 1);
}
}
run(0);
The example of a for loop didn’t use functions at all, while this example is very focused on them. Here are the function calls we see, in order:
function run(i): defining the functionrun, which prints the number of times, if that number is less than 10.run(i + 1): calling the functionrunwith the variableigiven a value 1 greater than its previous value.run(0): kick off the process by starting at 0.
Notice the similarity? Just like a for loop, a non-infinite recursive function has those three components:
run(0): How to startif (i < 10): Whether to stoprun(i + 1): How to keep going
The key to understanding recursion is that #2 and #3 are up to you: unlike a for loop, recursion doesn’t come with a preset system for beginning, continuing, and ending. But almost every recursive function follows the same pattern:
- One branch of an
ifstatement recurses deeper by calling the function again. - The other doesn’t.
So keep track of these essential parts of recursive functions: highlight them in your mind.
An example of how recursion is useful
Let’s say that you have a list of dogs in an array, and you want to check whether you have a specific dog.
var dogs = ['Vizsla', 'Hound', 'Mutt', 'Beagle'];
This is pretty simple with a for loop:
var lookingFor = 'Hound';
var found = false;
for (var i = 0; i < dogs.length; i++) {
if (dogs[i] === lookingFor) {
found = true;
}
}
What if you have groups of similar dogs in an array of arrays?
var dogs = [
['Hungarian Vizsla', 'Madyar Vizsla'],
['Blood Hound'],
['Pure Mutt', 'Half Mutt'],
['Mini Beagle', 'Mega Beagle']
];
Easy enough, nest the for loop:
var lookingFor = 'Blood Hound';
var found = false;
for (var i = 0; i < dogs.length; i++) {
for (var j = 0; j < dogs[i].length; j++) {
if (dogs[i][j] === lookingFor) {
found = true;
}
}
}
What about groups of groups?
var lookingFor = 'Blood Hound';
var found = false;
for (var i = 0; i < dogs.length; i++) {
for (var j = 0; j < dogs[i].length; j++) {
for (var k = 0; k < dogs[i][j].length; k++) {
if (dogs[i][j][k] === lookingFor) {
found = true;
}
}
}
}
You can see where this is going: the deeper the array’s nesting, the more for loops we need, and eventually we’ll run out of indentation of letters of the alphabet.
Another place for loops will break is if the nesting is uneven, like if some dogs are grouped and some aren’t:
var dogs = [
['Hungarian Vizsla', 'Madyar Vizsla'],
'Hound',
['Pure Mutt', 'Half Mutt'],
['Mini Beagle', 'Mega Beagle']
];
var lookingFor = 'Blood Hound';
var found = false;
for (var i = 0; i < dogs.length; i++) {
if (typeof dogs[i] === 'string') {
if (dogs[i] === lookingFor) {
found = true;
}
} else {
for (var j = 0; j < dogs[i].length; j++) {
if (dogs[i][j] === lookingFor) {
found = true;
}
}
}
}
Again, inelegant. Let’s solve this problem elegantly with recursion:
var dogs = [
['Hungarian Vizsla', 'Madyar Vizsla'],
'Hound',
['Pure Mutt', 'Half Mutt'],
['Mini Beagle', 'Mega Beagle']
];
function findDog(dogs, lookingFor) {
if (typeof dogs === 'string') {
return dogs === lookingFor;
}
for (var i = 0; i < dogs.length; i++) {
if (findDog(dogs[i], lookingFor)) {
return true;
}
}
}
var found = findDog(dogs, 'Blood Hound');
Getting fancy with the Array.some function makes this even nicer:
function findDog(dogs, lookingFor) {
return typeof dogs === 'string' ?
dogs === lookingFor :
dogs.some(function (dog) {
return findDog(dog, lookingFor);
});
}
In ES6 with the Array#some function, it can even be even shorter:
var findDog = (dogs, lookingFor) =>
typeof dogs === 'string' ? dogs === lookingFor : dogs.some(dog =>
findDog(dog, lookingFor));
The recursive version of this function is way more flexible than the for loop one. It can handle completely flat input, like a single name as a string, or deeply-nested groups.
What we’ve seen is that recursion is a natural solution for code that eats recursive data, like trees or nested lists.
Recursion as a full replacement for loops
That last example used both recursion and a loop in the recursive example: even when we abstract it away with the Array#some function, behind the scenes JavaScript is still using a loop. You can, in fact, use recursion anywhere you use a loop! Let’s see how, using sum as an example:
A typical loop-based sum technique:
var numbers = [2, 5, 10];
var sum = 0;
for (var i = 0; i < numbers.length; i++) {
sum += numbers[i];
}
Okay, so we’re going to need the three elements:
- How to start
- Whether to stop
- How to keep going
This might not be obvious at first, but if you’ve ever come across head and tail functions in other languages, they hold the key. head usually takes the ‘head’ of an array, the first element. And tail gives you the rest, which might be an empty list. Since JavaScript doesn’t have these functions built in, we’ll use functions that JavaScript does have: [0] and .slice. When given a single number as an argument, slice gives you a version of that list that excludes that number of items.
var numbers = [2, 5, 10];
function computeSum(numbers, tmp) {
if (numbers.length) {
return computeSum(numbers.slice(1), tmp + numbers[0]);
} else {
return tmp;
}
}
var sum = computeSum(numbers, 0);
So, if you look at how this function is called, it’d look like:
computeSum([2, 5, 10], 0); // recurse
computeSum([5, 10], 2); // recurse
computeSum([10], 7); // recurse
computeSum([], 17); // return tmp
This application of recursion to completely avoid loops is less common in JavaScript, but commonplace in languages like Elm and Clojure.
How recursion is different than your usual loop
Functional programming[1] and recursion come with their buzzwords and adherents and dissidents. Let’s cover a few:
Functions are kind of more of a ‘big deal’ than for loops. Using a function to do something means that you have scope: variables defined in the function stay in the function. It also means that the function is recorded in the call stack - basically a record of which function called which one, all the way down.
These are features, but they’re also costs.[2]
Because JavaScript keeps track of its call stack, it has a limit: the maximum call stack size. In Node.js, it’s around 11034. And since functions have scope and are included in the stack, using functions instead of writing code with for loops and other statements can make that code slightly slower. As you can read in the linked post, the new version of JavaScript, ES6, includes tail call optimization, an improvement that can completely avoid the maximum stack limit in some cases.
Infinite recursion and the curiosity of setTimeout
In computer languages that have a sleep() function that lets you pause their execution briefly, it’s common to use loops like while and for loops in order to run continuous loops. For instance, in pygame, a framework for games written in Python:
# Event loop
while 1:
for event in pygame.event.get():
if event.type == QUIT:
return
screen.blit(background, (0, 0))
pygame.display.flip()
Since 1 is always true, while 1 will keep the loop running forever.
JavaScript doesn’t have a sleep() function: there’s no way to pause execution. But it does have a setTimeout function that schedules another function to be called in the future.[3] So this is a great opportunity to use recursion!
var context = document.getElementById('canvas').getContext('2d');
function draw() {
var shade = Math.floor(15 + Math.random() * 200).toString(16);
context.fillStyle = '#' + shade + shade + shade;
context.fillRect(Math.random() * 640, 0, 1, 200);
setTimeout(draw, 100); // recurse in 100 milliseconds
}
draw();
This time we haven’t specified Whether to stop because we’ll never stop: this is an example of infinite recursion.
This style of recursion using setTimeout has one more big difference: it doesn’t run into the maximum call stack limit we discussed. When you call setTimeout, JavaScript creates a new call stack instead of adding the function call to the existing one. That means that this style of infinite recursive loop can keep going infinitely without any resource buildup. This doesn’t come free, though: setTimeout also means that you can’t get the return value from your function, and if that function throws an exception, you’ll get much less information in the error message.
Fin
I hope this has been a useful explanation of recursion. Recursion is a lot like reduce - a powerful and flexible tool that you can use in a wide range of situations and is essential for certain problems.
Footnotes
- Since recursion uses functions for repeating bits of code, it’s associated with functional programming, a vague category of programming that encourages usage of functions where otherwise you’d use statements like
forand sometimes replaces the idea of variables defined likevarwith function arguments. - I hesitate to ever mention performance in posts aimed at people starting out. Until they have a strong compass of when to prefer the fast way or the safe way, people tend to make bad choices and I don’t want to imply that something is slow-as-in-don’t-use-it - it’s extremely rare that language-level stuff like recursion slows down a typical web app or node module. It’s much more common that the fast/unsafe way introduces some kind of bug, or the performance is concentrated somewhere outside of so-called ‘algorithmic code’, like in wasteful DOM manipulations. Please don’t optimize for performance until you can identify a performance problem, profile it, and understand the tradeoffs.
- JavaScript also has a method called
setIntervalthat you might have heard of. And, yep, it calls a function repeatedly for you, but has three drawbacks that prevent me from using it:- If you ever do want to stop execution, it’s simple with setTimeout and a little hacky with setInterval
- If you want to upgrade to JavaScript’s fancy new function called requestAnimationFrame, you can follow the pattern from setTimeout. There’s no modern equivalent of setInterval.
- If your method actually does some work, using setTimeout ensures that it doesn’t fill up a queue and get weird.