Ultimate Beginners' Guide to JavaScript Recursion

Recursion in JavaScript is no different from recursion in other languages. It is a popular term used to describe a pattern/algorithm of a function that calls itself directly or indirectly. It describes a function that performs the same action with different criteria/properties up to a specified limit.

Recursion can be a bit tricky and sometimes beginners struggle with it. But it's ok if you're struggling with it, this article will help you understand the certain principles of recursion (how it works). But this article alone will not stop you from struggling with it, practicing with examples will help you get the hang of it.

A simple example to get started would be to get the sum of a range of two numbers

function sumOfRange(start, end, sum = 0) {
  if (start > end) {
    return sum;
  }

  let current = start; // for readability
  sum += current;
  return sumOfRange(current + 1, end, sum);
}

sumOfRange(10, 20);

The function above is recursive because it calls itself. So the aim of the function is, to sum up, all the numbers that go from 10 (inclusive) to 20 (inclusive). That means 10+11+12+13+14...

Initially, the function is called outside with the start and end parameters. Then in the function, we checked to see if the start param is greater than the end, if not we simply performed simple math and called the sumOfRange function again but with the new value(s).

From this recursive function, we can deduce two key factors of recursion

A base condition
A changing value

A recursive function should always have a base condition. For every recursion, there should be a limit/endpoint, and so we use base conditions to check - each time the function is called - if that limit has been reached.

This is done to avoid infinite looping, without the base condition the function is just going to keep calling itself. Clearly, you wouldn't want that in your app.

Coming up with a base condition is very simple, think of it like a while loop approach, for example, in our example above we could say "as long as the number I started with is still less than the target number then proceed otherwise stop".

So what this means is that for every time the function is called again, either we

increment the start param to become greater than the end param or
decrement the end param to become lesser than the start param.

One of the above needs to happen for the base condition to have effect eventually. In our example, the start param was incremented by 1 for every time the function is called. This is because we simply want the sum of all numbers within two numbers (with the first being the lesser one).

You could say

function sumOfRange(end, start, sum = 0) {
  if (start > end) {
    return sum;
  }

  let current = end; // for readability
  sum += current;
  return sumOfRange(current - 1, start, sum);
}

sumOfRange(20, 10);

In this case, we are simply decrementing the end param to meet up with the start param for the base condition to execute eventually. Think of it as a transaction between a buyer and seller, they both have to reach a point of agreement during negotiations for the goods to be purchased by the buyer.

If they don't reach an agreement, recursion is saying if you don't provide a way for them to reach an agreement or forget about buying/selling then they are just going to keep negotiating till the end of the world.

My point is there needs to be a changing value that the base condition(s) can continually check to wrap up everything. Here is a simple example that explains that

const possibleWords = ['same', 'fame', 'name', 'tame'];
function createWord(possibleLetters) {
  const word = produceFourRandomLetters(possibleLetters);

  if (possibleWords.includes(word)) {
    return word;
  }

  return createWord(possibleLetters);
}

function produceFourRandomLetters(possibleLetters, lettersProduced = '') {
  if (lettersProduced.length >= 4) {
    return lettersProduced;
  }

  const letter =
    possibleLetters[Math.floor(Math.random() * possibleLetters.length)];
  return produceFourRandomLetters(
    possibleLetters,
    lettersProduced.concat(letter)
  );
}

console.log(createWord('ameftsn'));

"Elijah, I thought you said it was gonna be a simple example? 😃". Well, it is, don't let the length overwhelm you, it is basic and simple.

What we intend to do is produce a word from a list of possible words. So we have a list of possible words, and we used the letters in it to reproduce one of those words. This is clearly not the most efficient way of doing it, but I think it will help you understand recursions a little better.

My aim with this example is to really explain base conditions and changing values better. So let's forget about all the other stuff in both functions and just pay attention to the base conditions and changing values only. Because when creating a recursive function, the questions that should always think are

what/where is my base condition?
based on my base condition which value is changing? Because it's not just about having a value that changes every time the function is called but does the base condition involve this value.

It is similar to a for loop. In a for loop, there is always a condition and a changing value, just as in every other JS traditional loop. We will talk about the difference between recursions and traditional loops in a while, but in the meantime let's talk more about the example above.

Firstly, both functions are recursive. And the base conditions in both functions are obvious enough, but let's talk about the createWord function first.

function createWord(possibleLetters) {
  const word = produceFourRandomLetters(possibleLetters);

  if (possibleWords.includes(word)) {
    return word;
  }

  return createWord(possibleLetters);
}

The createWord function calls a function that returns a word of 4 letters. The base condition here is to check if the word returned is a member of the possibleWords, if it is then we simply jump out of the function by returning the word. If it isn't then we call the function again, with the same params.

Now the question is, is there a changing value? Yes, there is! The changing value, in this case, is the word variable from the function (produceFourRandomLetters) that randomly generates a word of 4 letters within the range of the possible letters given (possibleLetters).

So technically, we are relying on the produceFourRandomLetters to produce different values each time it is called to meet an expected end (which is to return one of the possible words).

Now let's look at the last function to make sure it would always produce different values.

function produceFourRandomLetters(possibleLetters, lettersProduced = '') {
  if (lettersProduced.length >= 4) {
    return lettersProduced;
  }

  const letter =
    possibleLetters[Math.floor(Math.random() * possibleLetters.length)];
  return produceFourRandomLetters(
    possibleLetters,
    lettersProduced.concat(letter)
  );
}

Producing different values is the primary aim of this function, rather than producing an actual understandable word. It is the createWord function that checks if each of the different values provided by this function is an actual word in the list of possible words.

As mentioned before, the produceFourRandomLetters is a recursive function, and the question of "what/where is the base condition", and "where/what is the changing value" comes to mind.

For the base condition, we are checking to see if the length of the lettersProduced is equivalent to 4. If this is the base condition then it means the changing value has to involve the lettersProduced right? Yeah. In this case, we are appending a random letter to the lettersProduced.

The lettersProduced starts with an empty string, then keeps adding a random letter to the string until it gets to 4 and then we exit the function. So for the first function call, the lettersProduced param passed to the function is '', but for the second time maybe 'a' is passed in, and then maybe 'at' follows, and so on.

Now the algorithm of this example is not done in a way that values already checked for won't repeat themselves, but it is impossible to keep repeating itself to cause an infinite loop. That is why there will always be an indefinite number of attempts/trials before we finally get a word from the list of possible words.

Sometimes it could produce just 40 words (a combination of 4 letters) before it gets a real word, or more than 1000 words, it is never definite. Here is a little twist to the example to check the number of times it takes to get to a real word

const possibleWords = ['same', 'fame', 'name', 'tame'];
function createWord(possibleLetters, trial = 0) {
  const word = produceFourRandomLetters(possibleLetters);
  console.log(word);

  if (possibleWords.includes(word)) {
    console.log(trial);
    return word;
  }

  return createWord(possibleLetters, trial + 1);
}

function produceFourRandomLetters(possibleLetters, lettersProduced = '') {
  if (lettersProduced.length >= 4) {
    return lettersProduced;
  }

  const letter =
    possibleLetters[Math.floor(Math.random() * possibleLetters.length)];
  return produceFourRandomLetters(
    possibleLetters,
    lettersProduced.concat(letter)
  );
}

console.log(createWord('ameftsn'));

Personally, when it comes to recursion there is a way I like writing recursive functions. If you've noticed, there is one common thing among the examples, and that is, there is always a param that is not needed outside the function. For example, we had

function sumOfRange(start, end, sum = 0) {
  if (start > end) {
    return sum;
  }

  let current = start; // for readability
  sum += current;
  return sumOfRange(current + 1, end, sum);
}

sumOfRange(10, 20);

We clearly do not need the sum param outside the sumOfRange function. So I always like refactoring to this

function sumOfRange(start, end) {
  function iterate(current, sum) {
    if (current > end) {
      return sum;
    }

    sum += current;
    return iterate(current + 1, sum);
  }

  return iterate(start, 0);
}

console.log(sumOfRange(10, 20));

This isn't just for the sum param, but it also helps to put things in perspective. When you have a very technical issue to solve with recursion, this can come in handy.

Note: The examples we've seen can all be done with a for loop, while, and do while. While this is possible with loops it is also like 3 times faster with loops than with recursion. Yeah, that's right. It is way faster to go through traditional loops than calling functions.

One major reason developers pick recursion over loops is because of the readability. You'd want to write a readable program that works just as its alternatives only slower. This is very useful when dealing with complex coding issues.

One good thing you can do to improve performance in recursion is to make sure the recursive call is the last statement like in the examples we've given. This helps the compiler optimize the recursive function.

Conclusion

Choosing between recursion and loops shouldn't become a problem for you. Most times, I just like writing a simple loop for simple problems, but then when it gets tougher and more complex I just switch to recursions. Easy enough.

It doesn't really matter if the code is about 3 times slower with recursion, that alone will not significantly affect performance as you might think, other than that what really matters is that it's a good readable code.

Alright, that's it for this article. Thanks for reading guys. Please like, share, and leave a comment below to let me know what you think about recursions. If you're on Twitter, give me a follow @elijahtrillionz.

If you like this article and you'd like to encourage/support me to do more, then you can kindly buymeacoffee

Ultimate Beginners' Guide to JavaScript Recursion

Recursion can be a bit tricky and sometimes beginners struggle with it. But this will help you get started.

Conclusion