DEV Community

Cover image for Recursion: An Illustrated Play-By-Play
Monica Macomber
Monica Macomber

Posted on

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];
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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));
Enter fullscreen mode Exit fullscreen mode

Evaluates into:

return 1 + getSum([2,3,4]);
Enter fullscreen mode Exit fullscreen mode

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

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

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

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

if (arr.length <= 1 ) return arr[0];
Enter fullscreen mode Exit fullscreen mode

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

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

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

The third car disembarks

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

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.

Top comments (11)

Collapse
 
destro_mas profile image
Shahjada Talukdar

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

Collapse
 
monicat profile image
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.

Collapse
 
destro_mas profile image
Shahjada Talukdar

Cool, thanks đź‘‹

Collapse
 
tomarks profile image
Thomas Markwell

Great illustrations!

Collapse
 
vaibhavkhulbe profile image
Vaibhav Khulbe

Great writeup and good illustrations!

Collapse
 
aksarben profile image
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?

Collapse
 
monicat profile image
Monica Macomber • Edited

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 đź‘Ť

Collapse
 
aksarben profile image
Dick Adams

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

Thread Thread
 
monicat profile image
Monica Macomber

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

Collapse
 
dafahrni profile image
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 (-;

Collapse
 
monicat profile image
Monica Macomber

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