# Recursion in JavaScript

I’m just gonna get this out of the way right up front, because people get really angry otherwise:

Consider this post as a series of learning exercises. These examples are designed to make you think — and, if I’m doing it right, maybe expand your understanding of functional programming a little bit.

#### Hey, dawg. I heard you like recursion, so I put a “Hey, dawg. I heard you like recursion, so I put a “Hey, dawg…

Loosely defined, recursion is the process of taking a big problem and sub-dividing it into multiple, smaller instances of the same problem.

Put into practice, that generally means writing a function that calls itself. Probably the most classic example of this concept is the factorial function.

You may remember from math class that the factorial of a number `n`

is the product of all positive integers less than or equal to `n`

. In other words, the factorial of `5`

is `5 x 4 x 3 x 2 x 1`

. The mathematical notation for this is `5!`

.

Something interesting you might have noticed about that pattern: `5!`

is actually just `5 x 4!`

. And `4!`

is just `4 x 3!`

. So on and so forth until you get down to 1.

Here’s how we’d write that in JavaScript:

If this seems confusing, I’d encourage you to mentally walk through the code using the example of `factorial( 3 )`

.

Here’s a bit of help, in case you need it:

`factorial( 3 )`

is`3 x factorial( 2 )`

.`factorial( 2 )`

is`2 x factorial( 1 )`

.`factorial( 1 )`

meets our`if`

condition, so it’s just`1`

.

So what’s really happening here is that you’re winding up the call stack, getting down to `1`

, and then unwinding the stack. As you unwind the call stack, you multiply each result. `1 x 2 x 3`

is `6`

, and that’s your return value.

#### Reversing A String

One of my co-workers recently told me about a whiteboard question that he’d been asked in an interview, and I thought it was kind of a fun problem.

Write a function that accepts a string a reverses it. Recursively.

If you’re the ambitious type, I’d encourage you to take a few minutes and try to solve this one on your own. Keep in mind the core principle of recursion, which is to take a big problem and break it down into smaller instances of itself.

If you got stuck (or you’re the decidedly *unambitious* type), here’s my solution:

Again, I’ll give a quick walk-through example in case you got stuck. We’ll use `reverse('bar')`

as a starting point.

`reverse('bar')`

is`reverse('ar') + 'b'`

`reverse('ar')`

is`reverse('r') + 'a'`

`reverse('r')`

meets our`if`

condition, so it’s just`'r'`

When the call stack unwinds, we end up with `'r' + 'a' + 'b'`

.

#### Writing a Recursive Map Function

For our final example, we’re going to write a `map()`

function. We want to be able to use it like this:

Again, I’d strongly encourage you to take a few minutes and try this one on your own. Here are a few hints and reminders:

`map()`

should always return a new array.- Break the problem down into smaller chunks.
- Remember the
`reverse()`

example.

Oh, good. You’re back. How did it go?

j/k, this is a blog and I can’t hear you. lol.

Anyway, here’s how I did it:

So let’s go through this using the example I gave earlier:

- Call
`map()`

using the array`[ 'a', 'b', 'c' ]`

- Create a new array that holds the result of calling
`fn('a')`

- Return
`[ 'A' ].concat( map([ 'b', 'c' ]) )`

- Repeat steps 1 through 3 with
`[ 'b', 'c' ]`

- Repeat steps 1 through 3 for
`[ 'c' ]`

- Eventually, we call
`map()`

with an empty array, which ends the recursion.

**NOTE:**

You should never, ever, ever do this in a real application. You’ll blow out the stack on large arrays, and more importantly, you create a huge amount of garbage by instantiating so many new objects. Use `Array#map`

in production code.

#### Wrap Up

Hopefully I did a decent job in explaining this stuff. If you’re still struggling a bit to wrap your head around recursion, the best advice I can give is to start with small examples and mentally trace the call stack. Try something like `reverse('abc')`

and walk through it, step-by-step. Eventually it’ll click.

— -

Follow me on Twitter or Medium for more posts. I’m trying to write once a day for the next 30 days.

And if you’re in the Boston area and want to come work on crazy, top-secret things with me at Project Decibel, shoot me an email. I’m hiring.