## Tom MacWright

tom@macwright.org

# 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)
``````
1. `var i = 0`: How to start, called the initialization. This runs once, just when the loop starts.
2. `i < 10`: Whether to stop, called the condition. This is tested every time that the loop loops, and if `i` is a number that’s greater than 10, the loop is done.
3. `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.

### 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 function `run`, which prints the number of times, if that number is less than 10.
• `run(i + 1)`: calling the function `run` with the variable `i` given 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:

1. `run(0)`: How to start
2. `if (i < 10)`: Whether to stop
3. `run(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 `if` statement 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 = [
['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;
}
}
}
``````

``````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 = [
'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 = [
'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: `` 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);
} 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(, 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 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.

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. 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.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 `for` and sometimes replaces the idea of variables defined like `var` with 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 `setInterval` that you might have heard of. And, yep, it calls a function repeatedly for you, but has three drawbacks that prevent me from using it:
1. If you ever do want to stop execution, it’s simple with setTimeout and a little hacky with setInterval
2. 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.
3. If your method actually does some work, using setTimeout ensures that it doesn’t fill up a queue and get weird.

July 03, 2016   @tmcw