Recursion Inside JavaScript

Christopher T.

September 27th, 2019

Share This Post

If you're new to recursion, this article will hopefully help you understand the concept a little more clearly. There are many techniques that JavaScript developers use that allow them to build powerful applications, and today we will go over recursion--a function that simply calls itself until a condition is met.

For example, lets say we have a list of frogs where we want to calculate the total sum of the widths of their tongues.

While there are several ways to achieve our goal, for the sake of this post we will use recursion to explain how it works.

const data = [
  {
    id: 1,
    name: 'Olly',
    widthOfTongue: 2.09,
    gender: 'Male',
    bodyColor: 'Mauv',
  },
  {
    id: 2,
    name: 'Odo',
    widthOfTongue: 16.54,
    gender: 'Male',
    bodyColor: 'Aquamarine',
  },
  {
    id: 3,
    name: 'Christal',
    widthOfTongue: 19.35,
    gender: 'Female',
    bodyColor: 'Turquoise',
  },
  {
    id: 4,
    name: 'Aube',
    widthOfTongue: 23.39,
    gender: 'Male',
    bodyColor: 'Violet',
  },
  {
    id: 5,
    name: 'Toiboid',
    widthOfTongue: 4.79,
    gender: 'Male',
    bodyColor: 'Fuscia',
  },
]

function findTotalFrogWidths(totalWidth, frogs) {
  if (!Array.isArray(frogs) || frogs.length < 0) {
    console.warn(
      'Could not evaluate the sum of the widths of the frogs tongues. Please check your "frogs" argument because the data type was incorrect',
    )
    return totalWidth
  }

  if (frogs.length === 0) {
    return totalWidth
  }

  if (frogs.length > 0) {
    return findTotalFrogWidths(
      (totalWidth += frogs.shift().widthOfTongue),
      frogs,
    )
  }
}

const result = findTotalFrogWidths(0, data)

console.log(result) // result: 66.16000000000001

This example code effectively calls itself until it reaches their goal--the total sum of all of the widths of the frog's tongues.

Here is what's happening inside the function:

First it checks if for some reason we had an invalid argument of frogs passed in. This is used to prevent the app from crashing and instead return the initial number. We also used a console.error to notify the dev that he messed up and to go make it better.

Just as with curry functions, there are rules to follow that make a function a recursion function. Otherwise, a function won't become a recursion function. There are three most important key features to consider when making a recursion function:

Three Important Rules For Recursions

three important key rules for recursions in javascript

1. The function should have a condition that self destructs itself

The first of three important rules that all recursion functions should follow is to have a condition in which the function can use to terminate (or self destruct) itself.

Without a condition to terminate itself, your code has a very good chance that it will be introduced with unexpected bugs. Usually, these bugs are the ones you want to avoid because it's usually calamitous like infinite loops or incorrect data types, which cause your app to crash.

However, there will always be a terminating condition at the end of the day but you want to be the one calling the shots. That's one of your main jobs for recursions.

Otherwise, your function has a good chance that it ends up running infinitely because the only thing it knows without a terminating condition is to just call itself until something stops it---and that something is our worst nightmare: the infinite loop.

In our example code earlier, our first condition was the terminating condition:

if (!Array.isArray(frogs) || frogs.length < 0) {
  console.warn(
    'Could not evaluate the sum of the widths of the frogs tongues. Please check your "frogs" argument because the data type was incorrect',
  )
  return totalWidth
}

If the frogs argument was an invalid data type, our app may have crashed without this condition because the code after that was using methods that only arrays can use:

if (frogs.length === 0) {
  return totalWidth
}

So if we invoked the function using the wrong data type like null for example:

const result = findTotalFrogWidths(0, null)

Then we get an error that causes the program to crash:

"TypeError: Cannot read property 'length' of null
    at findTotalFrogWidths (tewoyod.js:40:13)
    at tewoyod.js:52:16
    at https://static.jsbin.com/js/prod/runner-4.1.7.min.js:1:13924
    at https://static.jsbin.com/js/prod/runner-4.1.7.min.js:1:10866"

2. The function must have a base case condition

The second of three key features is having a base condition. A base condition's role to a recursive function is very similar to the terminating condition except that it represents your target goal--a happy ending!

Base cases are usually declared with an if statement. Our second condition in the code snippet was the base case:

// We have reached the end. Return the total sum
if (frogs.length === 0) {
  return totalWidth
}

The reason why it is the base condition is because when the frogs array is empty, there is no more items to iterate over so we can't do anymore, so we just return the sum.

3. Calls itself

And finally, the last one of the three defines a last condition in which the function must call itself if its condition is still in effect (this means that the terminating and base condition was not met).

This part of the recursion makes up the "re" in recursion. In order for the base or terminating condition to be met the function must redo (call) itelf to continue until one of them are satisfied.


Lets take a look at a different example taken from a stackoverflow link:

function test(x) {
  for (var i = 0; i < 10; i++) {
    console.log(x + ' - ' + i)
  }
  if (x < 3) {
    test(x + 1)
  }
}

test(0)

In this snippet, test is a function that takes an argument x (which should be a number type) and calls itself over and over while incrementing the value of x until it is no longer less than 3.

Conclusion

And that concludes the end of this article! I hope you found this to be valuable and look out for more in the future!


Tags

javascript
react
pattern
composition
recursion

© jsmanifest 2019