Recursion: An Illustrated Play-By-Play

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.

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.

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—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.

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.

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.

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 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:

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

Evaluates into:

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.

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.

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

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

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.

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?

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

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!

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 or Recursion is not hard.


Cover photo by Zhang Fengsheng on Unsplash.

Comments

[Shahjada Talukdar]

Pictures are nice.
Which tool did you use?
(I am not good at illustrations)

[Monica Macomber]

Thank you! I used Adobe XD with icons from Noun Project and iconmonstr. But if I were on a Mac I'd use Sketch.

[Shahjada Talukdar]

Cool, thanks 👋

[Thomas Markwell]

Great illustrations!

[Vaibhav Khulbe]

Great writeup and good illustrations!

[Dick Adams]

I tried looking at your demo at codepen.io/mocasalter/pen/xxxNvjR?... (I'm not familiar with codepen), but couldn't figure how to run it. What am I missing?

[Monica Macomber]

I'm printing the total sum to the console and Codepen has a console button on the bottom left of the screen where you can view it 👍

[Dick Adams]

I found & clicked the console button, but aside from the pane going white, nothing happens. What should happen?

[Monica Macomber]

You should see sum: 10 printing. You could try opening codepen in a different browser, that might help.

[Daniel Fahrni]

I have rarely encountered such a clear explanation of recursion. Thank you for this inspirational article full of passion and joy for programming (-;

[Monica Macomber]

I had a hard time finding clear explanations too, I'm so glad to hear it's filling that gap. Thank you!