DEV Community

Cover image for How to Write a Recursive Function in JavaScript for Beginners
Michael J. Larocca
Michael J. Larocca

Posted on • Originally published at selftaughttxg.com

 

How to Write a Recursive Function in JavaScript for Beginners

Whether you're preparing for a coding interview or would like to learn about recursion, in this article, Full Stack Developer Daniel Nagaoka teaches us how to write a recursive function in JavaScript!


TN-TXG-69


This article aims to break down and step through the recursive JavaScript function to learn and understand how it works.

The recursive JavaScript function featured in this article is only several lines of code.

When I first saw it, I didn't quite understand how it worked, so I reached out to Daniel, who was kind enough to elaborate.

Taking it a step further, I broke down all of the JavaScript used in the recursive function to make this article beginner friendly.

Depending on your JavaScript level, feel free to skip around this article. If you are new to JavaScript, I recommend reading the whole article, as the topics covered will lead to writing the recursive function (think of it as learning prerequisites).

Here is the completed recursive JavaScript function covered in this article:

function flattenRecursive(arr) {
    return arr.reduce(
        (consolidated, child) => {
            if (Array.isArray(child)) {
                consolidated.push(...flattenRecursive(child));
            } else {
                consolidated.push(child);
            }
            return consolidated;
        },
        [], 
    );
}

const yay = [1, 2, [3, [4, [5, [6, [[[[[7], [8, 9]]]]]]], 10]]];
  console.log(flattenRecursive(yay));
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Enter fullscreen mode Exit fullscreen mode

About Daniel Nagaoka

Dan has experience in both Frontend and Full Stack Development. He graduated from the Universidade Paulista in SΓ£o Paulo, Brazil, with a Bachelor's degree in Computer Science.


What is recursion

So, what is recursion? MDN web docs explains, "The act of a function calling itself recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (resumes recursion)."


When to use recursion

To quote Dan:

Recursion really shines when we need to iterate over a structure of interconnected elements (called nodes) which you need to process, sort or find something in it while having no previous knowledge about its size or depth - most often to perform complex operations that is likely to produce many branches during the execution.

We'll learn more on its applicability further ahead in the article.


How I found Dan's recursive function

I came across Dan's recursive function while participating in Scrimba's JavaScriptmas 24-day annual coding event.

The day 17 challenge, Pumpkin's Prizes, instructs us to write a function to flatten nested arrays of strings or numbers into a single array.

By the very nature of the challenge, my initial thought was to use recursion to solve this problem. However, although I understand the concept of recursion, I need to learn how to use it in practical application.

So I was excited when I came across Dan's message in the JavaScriptmas Discord, along with a link to his elegant solution:

Dan Discord

Initially, Dan only had a few lines of code without comments explaining what line of code does.

I reached out to Dan, complimenting his work, and I asked if he could please elaborate on his solution, as it will significantly benefit others learning to code, including myself!

Not only did he add comments to his solution, but Dan also took the time to write a whole article section in issue 3 of my JavaScriptmas 2023 article series.

The topic of recursion and the article section Dan wrote deserved a separate article, the one you are reading now.


Understanding the function

Before Dan shows us how to create a recursive function, let us first break down and understand all the moving parts.

As a self-taught developer, I know what it is like to rewrite someone else's code, get it working, and feel great about it. Until you realize you don't actually understand how it works and have difficulty writing the code yourself.

Dan's recursive function consists of the following:

  • Reduce method
  • Arrow Function
  • if and else statements
  • isArray method
  • Array push method
  • Spread operator
  • A JavaScript Array

So before we learn how to write a recursive function, let's understand each part needed to build it.


JavaScript Array reduce()

The MDN web docs explain that the reduce() method is an iterative method. It runs a "reducer" callback function over all elements in the array, in ascending-index order, and accumulates them into a single value.

const numbers = [1,2,3,4,5];

const numbersReduced = numbers.reduce((total, currentValue) => {
  return total += currentValue;
}, 0);

console.log(numbersReduced);
15
Enter fullscreen mode Exit fullscreen mode

In the example above, the numbers 1,2,3,4 and 5 in the numbers array reduce to the value of 15 as follows:

1+0 = 1
2+1 = 3
3+3 = 6
4+6 = 10
5+10 = 15
Enter fullscreen mode Exit fullscreen mode

In the reduce method, the initial value is optional. In the example above, we set the initial value to 0.

Understanding how to set the initial value in the reduce method is essential for Dan's recursive function; he sets the initial value to an empty array.


Arrow Function

MDN web docs explains that an arrow function expression is a compact alternative to a traditional function expression, with some semantic differences and deliberate limitations in usage:

  • Arrow functions don't have their own bindings to this, arguments, or super, and should not be used as methods.
  • Arrow functions cannot be used as constructors. Calling them with new throws a TypeError. They also don't have access to the new.target keyword.
  • Arrow functions cannot use yield within their body and cannot be created as generator functions.

The arrow function written in Dan's recursive function is simple, so don't worry. I just want you to understand the syntax if you are unfamiliar with arrow functions.

To demonstrate, I wrote two simple greet functions:

function greetOne(name) {
  return "Hello " + name;
}

  console.log(greetOne("Michael"));
"Hello Michael"  
Enter fullscreen mode Exit fullscreen mode

Here is the same function rewritten as an arrow function:

greetTwo = name => "Hello " + name;

  console.log(greetTwo("Michael"));
"Hello Michael"  
Enter fullscreen mode Exit fullscreen mode

By rewriting the greet function as an arrow function, we eliminated the following syntax:

  • function
  • parentheses
  • curly brackets
  • return

The if and else statements

The if statement specifies a code block to execute if the condition is true, and the else statement specifies a code block to execute if the condition is false.

In the greet function below, if you pass in a name as the parameter, the greeting variable incorporates the name. If you do not pass in a name as the parameter, the greeting variable equals "Hello."

function greet(name) {
  let greeting = "";

  if (name != null) {
    //  Condition is true
    greeting = "Hello, " + name;
  } else {
    //  Condition is false
    greeting = "Hello"
  }
  return greeting;
}  

console.log(greet("Michael"));
"Hello, Michael"

console.log(greet());
"Hello"
Enter fullscreen mode Exit fullscreen mode

IsArray

The JavaScript method IsArray checks if an object is an array. If it is an array, it returns true. If it is not an array, it returns false.

In this code block, isArray returns true:

const colors = ["Red", "Yellow", "Green", "Blue"];
let result = Array.isArray(colors);

  console.log(result);
true
Enter fullscreen mode Exit fullscreen mode

In this code block, isArray returns false:

const firstName = "Michael";

  console.log(Array.isArray(firstName));
false
Enter fullscreen mode Exit fullscreen mode

JavaScript Array push()

The push() method adds new items to the end of an array.

In the example below, we add the color "Orange" to the colors array using the push method.

const colors = ["Red", "Yellow", "Green", "Blue"];
colors.push("Orange");

console.log(colors);
["Red","Yellow","Green","Blue","Orange"]
Enter fullscreen mode Exit fullscreen mode

Spread operator

w3schools explains that the JavaScript spread operator (...) allows us to quickly copy all or part of an existing array or object into another array or object.

The example below combines two number arrays into one new number array.

const numberSetOne = [1,2,3,4,5];
const numberSetTwo = [6,7,8,9,10];

const numberSetsCombined = [...numberSetOne, ...numberSetTwo];

console.log(numberSetsCombined);
[1,2,3,4,5,6,7,8,9,10]
Enter fullscreen mode Exit fullscreen mode

Combining both number arrays without the spread operator, we end up with a nested array (two arrays inside of the outer array), as demonstrated in the example below.

const numberSetOne = [1,2,3,4,5];
const numberSetTwo = [6,7,8,9,10];

const numberSetOneAndNumberSetTwo = [numberSetOne, numberSetTwo];

console.log(numberSetOneAndNumberSetTwo);
[[1,2,3,4,5],[6,7,8,9,10]]
Enter fullscreen mode Exit fullscreen mode

JavaScript Arrays

MDN web docs tell us the Array object, as with arrays in other programming languages, enables storing a collection of multiple items under a single variable name, and has members for performing common array operations.

As demonstrated below, we can create an array in JavaScript by declaring a variable using const and assigning it to square brackets.

const myArray = [];
Enter fullscreen mode Exit fullscreen mode

Note: Arrays are Not Constants. w3schools explains the keyword const is a little misleading.It does NOT define a constant array. It defines a constant reference to an array. Because of this, we can still change the elements of a constant array.


Dan's article section

Now that we've covered all of the JavaScript used in Dan's recursive function, it's time for Dan to teach us how to create one.

Below is Dan's article section previously featured in JavaScriptmas 2022 - Issue 3 on the topic of recursion ⬇


First, a few notes on the Array.prototype.reduce() method. It's not the main feature of the solution, but it can be quite a handful for beginners, so I'd rather address it, albeit briefly.

In short, the reduce method consolidates the original array into a single value - which can be virtually anything, from a string or number to a completely new array or an object. To do that, it iterates through its children and processes each of them with a custom function - the reducer callback function. The reducer will always receive data about the current iteration as arguments, the most important being:

  1. The consolidated (or "accumulated") value that will be expanded upon, then passed on to the next iteration;
  2. The current child being processed in this iteration.

The reduce method itself, therefore, requires:

  1. The reducer callback function, as described above;
  2. An initial state for the consolidated value.

For a hands-on explanation, you can refer to this really good video by Mosh.

Now for the actual usage of recursion.

Simply put, recursion is just a function that calls itself. That may summarize it, but its applicability can be a little more elusive to beginners.

Let's start by getting something out of the way: recursion !== looping. It isn't, and if you're using it for this purpose, then you're just building confusing code.

Recursion really shines when we need to iterate over a structure of interconnected elements (called nodes) which you need to process, sort or find something in it while having no previous knowledge about its size or depth. Stuff such as tree traversal, path finding and sorting algorithms are common scenarios where recursion is required.

So why does it apply in our current scenario? Let's say you were to flatten an array using a for loop:

function flatten(arr) {
  const newArray = [];
  for (const item of array) {
    if (Array.isArray(item)) newArray.push(...item);
    else newArray.push(item);
  }
  return newArray;
}

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

// [1, 2, 3, 4];
console.log(flatten(array));
Enter fullscreen mode Exit fullscreen mode

Sure, that works, but try a different, more elaborate array structure. Let's say:

const ohnoes = [1, 2, [3, [4, 5]]];
// [1, 2, 3, [4, 5]]
console.log(flatten(ohnoes));
Enter fullscreen mode Exit fullscreen mode

You probably realized that it is utterly unsustainable to nest n for loops in your code to account for n possible layers.

Thinking recursively, though, is often a daunting task. Let's look at the problem a little closer:

  • We want to flatten an array that is likely to have arrays as children;
  • The child arrays, though, are not guaranteed to be flattened themselves.

You probably guessed that we now need to call the same function to micromanage each of the array's children as well. Considering that:

  • The function should only ever reach its return expression with a flattened array;
  • The recursion path will eventually hit the bottom node of the structure - an array without child arrays - and then return it.

All of these stacking function calls are appropriately referred to as the call stack. When our current stack finally resolves itself, we must expect the resulting array to be - ta-dah! Flat as 1 week old soda.

Now all that's left is putting together our recursive function:

function flattenRecursive(arr) {
    // loop through the children to see which requires flattening
    return arr.reduce(
        (consolidated, child) => {
            // check if the child is an array itself
            if (Array.isArray(child)) {
                // we need to flatten the array before including its elements in
                // our consolidated array, so we call flattenRecursive recursively
                consolidated.push(...flattenRecursive(child));
            } else {
                // not an array, so just include it in the final array
                consolidated.push(child);
            }

            // return the consolidated array
            return consolidated;
        },
        [], // the initial, empty array
    );
}
Enter fullscreen mode Exit fullscreen mode

And now we get:

const yay = [1, 2, [3, [4, [5, [6, [[[[[7], [8, 9]]]]]]], 10]]];
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(flattenRecursive(yay));
Enter fullscreen mode Exit fullscreen mode

And that's about it!

Recursion is a bit too hefty a subject to tackle casually in an article like this and admittedly not something we really use often in our everyday lives as programmers. It is, however, a powerful technique when it comes into play, and definitely a must-have skill for every computer scientist.

- Dan


Dan’ links

πŸ”— LinkedIn: Daniel Nagaoka

πŸ”— Link to Dan's challenge scrim: Pumpkin's Prizes


Conclusion

Learning how to write a recursive function helps us to think recursively. Recursive thinking helps us break down complex problems into smaller ones, and gaining this skill will be essential for coding interviews. In addition, Dan tells us that recursion is a powerful technique and a must-have skill for every computer scientist.

When learning how to program, we spend a lot of time coding along with tutorials. Even though our copied code works, it is sometimes difficult to understand how it works and even more difficult to recreate on our own.

While following these coding tutorials, taking the extra time to break down each line of code to comprehend how it works will ultimately make us better programmers.


Let's connect! I'm active on LinkedIn and Twitter.


Do you now have a better understanding of recursion? Have you been asked to solve a problem recursively during a coding interview? Please share the article and comment!

Top comments (3)

Collapse
 
nubuck profile image
Barry Buck

Recursion is my favorite technique by far.
It's a bummer JS doesn't natively support tail call optimization.
Does calling the flattenRecursive function inside reduce mitigate the need to trampoline flattenRecursive?

Collapse
 
john4650hub profile image
JohnDelvin

I recently hard a challenging situation which i solved using recursion. I was building a cordova app for android and it came to reading the android file system and all the subfolders which also had subfolders. With recursions i was able to though it took sometime. I think using recursions to solve problems makes the code shorter, clear and more readable.

Collapse
 
dragin profile image
dragin96

arr.flat(Infinity)

Image description

Visualizing Promises and Async/Await 🀯

async await

☝️ Check out this all-time classic DEV post