Recursion: An Illustrated Play-By-Play
Tags: javascript, recursion, algorithms
Published: 2019-12-03 16:50:02

Do you ever just need to see code in action? Reading about how it works is all well and good but do you like to see a breakdown of exactly what happens at step 1, 2, 3 and 4? Me too.

I'll show you an example of a recursive function in JavaScript and then walk you through how it works, featuring *colorful automobiles* and *a seafaring vessel*!

## What is Recursion

A function is recursive when it:

1. Call itself.
2. Has a base case, some code that defines when the function should stop calling itself. Otherwise the function will keep calling itself infinitely.

## Code Example

Let's say we have this array and we want the sum of its values.

```javascript
const array = [1,2,3,4];
```

To get the sum, we need to add the first item of the array to next item of the array and so on.

```javascript
function getSum(arr) { 
  return arr[0] + arr[1] + // etc.
}
// lol get some
```

But there are better ways to accomplish that besides manually listing each item of the array. One way is with recursion&mdash;having the function call itself. 

To make the function recursive, we'll add the first item of the array to the remaining array *after* it's processed by the getSum function. We'll cover that in detail in the next section. 

```javascript
function getSum(arr) {
  return arr[0] + getSum(arr.slice(1)); // recursion
}
```

And when do we want to stop adding? In other words, what should our base case be? When we get to the last item of the array.

```javascript
const array = [1,2,3,4];
function getSum(arr) {
  if (arr.length <= 1 ) return arr[0]; // base case
  return arr[0] + getSum(arr.slice(1)); // recursion
}
getSum(array);
```

So there's our recursive function. You can [try a demo here](https://codepen.io/mocasalter/pen/xxxNvjR?editors=1112).

It might seem like we don't need a base case since there is nothing to process after the end of the array, but you'll get a fun [maximum call stack exceeded](https://codeburst.io/uncaught-rangeerror-maximum-call-stack-in-javascript-f1817760c4bf#716d) error if it's not included.

Now what exactly happens when the getSum function calls itself? 

## Illustrated Play-By-Play

The first time `getSum` runs, this line:

```javascript
return arr[0] + getSum(arr.slice(1));
```

Evaluates into:

```javascript
return 1 + getSum([2,3,4]);
```

The first item of the array added to getSum with the remaining array. 

But we don't know the result of `getSum([2,3,4])` yet, so what happens? The very first getSum function call, `getSum([1,2,3,4])`, is saved for later on the browser's **Call Stack**. 

The Call stack is a data structure that keeps track of function calls that need to be run. Let's think of it as a ferry that will take cars, the functions, across a bay. It's a small ferry named HMS Call Stack that has a single, one way deck for cars.

![The HMS Call Stack and getSum Function Car](https://thepracticaldev.s3.amazonaws.com/i/0z11aqrabie0dfn0dss5.png)

So our first getSum function car backs into the ferry. It returns a value of `1 + getSum([2,3,4])` that will be processed later.

![The first car boards the ferry](https://thepracticaldev.s3.amazonaws.com/i/f8f13ljbtzrihpx2auns.png)

Then `getSum([2,3,4]` is called recursively. What will that function return? `2 + getSum([3,4])`. Another car backs into HMS Call Stack.

![The second car boards the ferry](https://thepracticaldev.s3.amazonaws.com/i/isrxu2irk5han0rsw29f.png)

This continues until we hit our base case, the last item of the array.

```javascript
if (arr.length <= 1 ) return arr[0];
```

It returns the first and only remaining item of the array. So a getSum function car that returns 4 backs into HMS Call Stack.

![The last car back boards ferry](https://thepracticaldev.s3.amazonaws.com/i/n5smehx27i2afjirni9n.png)

Now that we've hit our base case, no more function cars will board the HMS Call Stack. Time for the ferry to cross the bay.

When the ferry docks, the last car to arrive (blue) has to disembark first. Similarly, Call Stack data structures are **Last In, First Out** (LIFO). The last function added to the stack will be called first.

If that last function car to board disembarks from the HMS Call Stack, what do we have next?

![The fourth car disembarks](https://thepracticaldev.s3.amazonaws.com/i/lmja10mfbhkr8cmkw6pm.png)

It returns 4 to the function that called `getSum([4])`. And when the next function is called:

![The third car disembarks](https://thepracticaldev.s3.amazonaws.com/i/1flqcmp9fac065sicpin.png)

It returns 3 + 4 to the function that called it. Notice how we're back to where we started? We're adding each item of the the array one at a time but in a more elegant way.

Finally, when the first getSum function car to board disembarks from the HMS Call Stack we have our total value. Ten!

![The first car disembarks](https://thepracticaldev.s3.amazonaws.com/i/d86k4wlmh6w7sz0d7igo.png)

And there we go. That's how a recursive function works as demonstrated by *colorful automobiles* and *a seafaring vessel*!

### For Further Reading

Adding the values of an array together is a good introduction to recursion, but it isn't great for practical application. For more in-depth guides check out [Algorithms in JavaScript](https://egghead.io/courses/algorithms-in-javascript) or [Recursion is not hard](https://www.freecodecamp.org/news/recursion-is-not-hard-858a48830d83/).
<br />
*Cover photo by [Zhang Fengsheng](https://unsplash.com/@samyzfs) on Unsplash.*