The Power of Recursion in JavaScript
Tags: node, javascript, react
Published: 2020-04-02 01:46:18

Find me on [medium](https://medium.com/@jsmanifest)

[Recursion](https://en.wikipedia.org/wiki/Recursion) is a powerful concept in computer programming where a function simply just calls itself. I cannot stress enough how important it is to learn how recursion works as soon as possible after learning the basics.

Understanding the concept of recursion and how to create one will help you think more like a programmer which can help you write more robust code.

## Benefits of Recursion

Generally when applying recursion in situations there's almost always these benefits you get from it:

1. You save lines of code
2. Your code can look cleaner (thus applying clean code practices even if it wasn't your intention)
3. It helps save time writing and debugging code
4. It reduces the amount of time to run an algorithm ([time complexity](https://en.wikipedia.org/wiki/Time_complexity))
5. Helps to easily solve problems when working with tree structures
6. Helps to _visualize_ algorithms ([Don't believe me?](https://algorithm-visualizer.org/))

## Disadvantages of Recursion

1. It _can_ be slower--in which it takes up more of the stack (overhead)
2. Uses more memory than a loop if [tail call optimization](https://en.wikipedia.org/wiki/Tail_call) isn't used

## Do we need it?

In practice, you can perform any algorithm using iteration. The thing is you have to know _when_ it's best to apply recursion--and only that way will make recursion the better choice rather than using iteration.

When applying recursion in situations that work best with it, you unlock the _power of recursion_ just as how powerful it is to apply recursion in the [Tower of Hanoi](https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/) problem.

## Examples

A good way to understand recursion is to look at a working code that applies recursion to solve a problem.

### Traverse Objects

As mentioned previously, recursions can help easily solve problems when working with tree structures. A deeply nested object is a tree structure, so we'll work with an object.

Pretend that we have an object representing HTML DOM elements, where each nested object object can have children of elements. Each children is another HTML DOM element and can also have children, so it can be a really huge object depending on how many offsprings are produced by their parents.

Our goal is to tap into every single object no matter how far nested it becomes. We'll look at their `style` property (that represents the attributes for that particular HTML element) and fix the `border`, `textColor` and `width` property to their style representations so that they can be read normally when working with JavaScript.

Here is an example of a style object that needs to be changed:

```json
{
  "border": {
    "color": "hotpink",
    "width": "2px"
  },
  "textColor": "violet",
  "width": "0.45"
}
```

In html, to color texts we need to use the `color` property so we would have to transform `textColor` to `color`. For `width`, let's pretend that these decimals represent the percentage of the user's device's viewport (which should be converted to `45vw`), and the `border` object needs to be transformed in a shape like `{ borderColor: 'hotpink', borderWidth: '2px' }`

Let's work with an object that represents that simlar structure so we can traverse it and fix all the style objects:

```json
{
  "type": "div",
  "style": {},
  "children": [
    {
      "type": "div",
      "style": {
        "backgroundColor": "black",
        "border": {
          "color": "hotpink",
          "width": "2px",
          "style": "dashed"
        },
        "fontStyle": "italic",
        "padding": "20px 25px",
        "textColor": "white"
      },
      "children": [
        {
          "type": "button",
          "style": {
            "backgroundColor": "#fda512",
            "border": {
              "color": "red"
            },
            "textColor": "#ffffff"
          }
        },
        {
          "type": "label",
          "style": {
            "height": "0.04",
            "width": "0.04"
          },
          "children": [
            {
              "type": "label",
              "style": {
                "border": {
                  "style": "solid",
                  "width": "5px"
                },
                "fontStyle": "italic"
              },
              "children": [
                {
                  "type": "span",
                  "style": {
                    "backgroundColor": "#039392",
                    "borderRadius": "10px",
                    "height": "0.03",
                    "outline": "none",
                    "width": "0.783"
                  }
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}
```

Okay, so we have a tree structure going on here where nested objects occur from the `children` property.

The first thing we're going to create is a `transformStyleObject` function that takes a style object to fix it, returning a new object that can be worked with normally in JavaScript and the DOM:

```js
function transformStyleObject(styleObj) {
  const result = {}
  const keys = Object.keys(styleObj)
  keys.forEach((key) => {
    if (key === 'border') {
      const { color, width, style } = styleObj.border
      if (color) result.borderColor = color
      if (width) result.borderWidth = width
      if (style) result.borderStyle = style
    } else if (key === 'textColor') {
      result['color'] = styleObj.textColor
    } else if (key === 'width') {
      result['width'] = `${Number(styleObj.width) * 100}vw`
    } else if (key === 'height') {
      result['height'] = `${Number(styleObj.height) * 100}vh`
    } else {
      result[key] = styleObj[key]
    }
  })
  return result
}

const result = transformStyleObject({
  border: {
    width: '2px',
    style: 'dashed',
  },
  height: '0.42',
})

console.log(result) // result: { borderWidth: '2px', borderStyle: 'dashed', height: '42vh' }
```

We can use regular iteration to traverse objects:

```js
function transformAll({ type = '', style = {}, children = [] }) {
  const result = { type, style: transformStyleObject(style), children }
  if (Array.isArray(result.children)) {
    for (let index = 0; index < result.children.length; index++) {
      const child = result.children[index]
      child.style = transformStyleObject(child.style)
      if (Array.isArray(child.children)) {
        for (
          let childIndex = 0;
          childIndex < child.children.length;
          childIndex++
        ) {
          const childsChildren = child.children[childIndex]
          childsChildren.style = transformStyleObject(childsChildren.style)
          if (Array.isArray(childsChildren.children)) {
            for (
              let childsChildsChildrenIndex = 0;
              childsChildsChildrenIndex < childsChildren.children.length;
              childsChildsChildrenIndex++
            ) {
              const childsChildsChild =
                childsChildren.children[childsChildsChildrenIndex]
              // ...etc
            }
          }
        }
      }
    }
  }
  return result
}
```

But it begins to get troublesome for these reasons:

1. It becomes longer
2. It becomes harder to read
3. It becomes harder to debug
4. It becomes more sensitive to changes
5. It becomes harder to test
6. It becomes tiresome because you're having to think of more variable names

Instead, a recursion can be used instead which solves all of the six problems listed above:

```js
function transformAll({ type = '', style = {}, children = [] }) {
  const result = { type, style: transformStyleObject(style), children }
  if (Array.isArray(result.children)) {
    result.children = result.children.map(transformAll)
  }
  return result
}
```

```json
{
  "type": "div",
  "style": {},
  "children": [
    {
      "type": "div",
      "style": {
        "backgroundColor": "black",
        "borderColor": "hotpink",
        "borderWidth": "2px",
        "borderStyle": "dashed",
        "fontStyle": "italic",
        "padding": "20px 25px",
        "color": "white"
      },
      "children": [
        {
          "type": "button",
          "style": {
            "backgroundColor": "#fda512",
            "borderColor": "red",
            "color": "#ffffff"
          },
          "children": []
        },
        {
          "type": "label",
          "style": {
            "height": "4vh",
            "width": "4vw"
          },
          "children": [
            {
              "type": "label",
              "style": {
                "borderWidth": "5px",
                "borderStyle": "solid",
                "fontStyle": "italic"
              },
              "children": [
                {
                  "type": "span",
                  "style": {
                    "backgroundColor": "#039392",
                    "borderRadius": "10px",
                    "height": "3vh",
                    "outline": "none",
                    "width": "78.3vw"
                  },
                  "children": []
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}
```

Our implementation now looks a lot more elegant, and easier to read! Here's how this recursion works:

1. `transformAll` takes a _single_ object that represents an HTML DOM element.
2. Transforms the style attributes of that element (which is our goal for every HTML DOM element in our case)
3. Checks if there are nested elements by checking the element's `children` property
4. If there is, this function will loop through each children and re-call itself `transformAll` on each child.
5. This starts the recursion and will loop through _every_ object it can find through `children` no matter how deep the tree goes.

### Working With Files and Folders

I personally find it an awesome experience to write more functional code. And when there's functional code, there's more elegance. Recursion fits nicely into this.

Let's build a program that will look into every directory under a _file path_, scan for folders named `__test__` and detect if there are any unit tests that were not implemented by looking for file names with `.test.js`. Each folder will be a _"module"_, and we'll assume it _doesn't_ have unit tests implemented for it if it either _does not_ have a `__test__` folder _or does not_ have any files _within their `__test__` folder_ that end with `.test.js`.

If it finds that there is a test for a module, it will return an object to us containing information about that whole directory like:

```json
{
  "../javascript-algorithms/src/algorithms/math/linked-list": {
    "name": "linked-list",
    "category": "algorithms",
    "subcategory": "math",
    "totalFiles": 0,
    "filesList": []
  }
}
```

The final result of this operation is an array of these objects, where each object represents a folder (which is a module in our case) that need our attention because they don't have unit tests yet.

Recursion can easily be used to make this happen.

I used the `https://github.com/trekhleb/javascript-algorithms` repo, extracted out everything inside the `src` directory and purposely removed a couple of unit tests in some of their examples so that our code can return those locations in our result.

The code snippets ahead imports native modules from [nodejs](https://nodejs.org/en/).

First, we're going to import `fs` and declare a root directory to start the traversing from:

```js
import fs from 'fs'

const rootDir = '../javascript-algorithms/src'
```

Next, we're going to use the `isDirectory` method from the `fs` module later to detect when to enter in directories. I personally prefer to wrap this into a function because I don't like writing the full method:

```js
function isDirectory(filePath) {
  return fs.statSync(filePath).isDirectory()
}
```

We're also going to create a function called `hasTest` that takes an array of strings, loop through them and if it finds that there is a test file then it will return `true`, or `false` otherwise:

```js
function hasTest(testDir) {
  for (let index = 0; index < testDir.length; index++) {
    const filename = testDir[index]
    if (filename.endsWith('.test.js')) {
      return true
    }
  }
  return false
}
```

Now for the main function, we'll call it `findEmptyTests` which is responsible for accumulating all the modules that don't have any tests implemented:

```js
function findEmptyTests(basepath) {
  let emptyTests = {}

  if (isDirectory(basepath)) {
    const dir = fs.readdirSync(basepath)

    for (let index = 0; index < dir.length; index++) {
      const filename = dir[index]
      const filepath = `${basepath}/${filename}`

      if (isDirectory(filepath)) {
        if (filename === '__test__') {
          const testDir = fs.readdirSync(filepath)
          if (!hasTest(testDir)) {
            emptyTests[filepath] = createMissingTestsObject(basepath, testDir)
          }
        } else {
          emptyTests = { ...emptyTests, ...findEmptyTests(filepath) }
        }
      }
    }
  }
  return emptyTests
}
```

We can see that this is a recursion because it calls _itself_ at this line:

```js
emptyTests = { ...emptyTests, ...findEmptyTests(filepath) }
```

Which is the most important part!

The way this function works is that we can call `findEmptyTests` by passing in a file path to start from.

If the file path we pass in _is a directory_, it will read all the files in the directory and store the file names into the `dir` array.

A loop is performated afterwards so that we can check which one is a directory. If it encounters a directory from the current iterating `filepath`, it will check two conditions:

1. Is the current iterating file path the `__test__` directory itself? If so, check that directory to see if there are any files ending with `.test.js`. If not, we grab information about that module's location in the repo.
2. Is the current iterating file path _not_ a `__test__` directory but is _still a directory_? If so, traverse inside that directory and start the whole function _inside that directory_, and the directory after that, etc.

Finally, the result is returned once it finished its operation.

You probably noticed the `createMissingTestsObject` function. It's just a function that collects information about a file path and its directory:

```js
function createMissingTestsObject(str, dir) {
  const indexToSrc = str.indexOf('src')
  let category = str.substring(indexToSrc + 4)
  let subcategory = category.substring(category.indexOf('/') + 1)
  subcategory = subcategory.substring(0, subcategory.indexOf('/'))
  category = category.substring(0, category.indexOf('/'))
  return {
    name: str.substring(str.lastIndexOf('/') + 1),
    category,
    subcategory,
    totalFiles: dir.length,
    filesList: dir,
  }
}
```

This should now return us a nice object of locations that are missing unit tests!

```json
{
  "../javascript-algorithms/src/algorithms/math/fourier-transform/__test__": {
    "name": "fourier-transform",
    "category": "algorithms",
    "subcategory": "math",
    "totalFiles": 1,
    "filesList": ["FourierTester.js"]
  },
  "../javascript-algorithms/src/algorithms/sets/cartesian-product/__test__": {
    "name": "cartesian-product",
    "category": "algorithms",
    "subcategory": "sets",
    "totalFiles": 0,
    "filesList": []
  },
  "../javascript-algorithms/src/algorithms/sets/combination-sum/__test__": {
    "name": "combination-sum",
    "category": "algorithms",
    "subcategory": "sets",
    "totalFiles": 0,
    "filesList": []
  }
}
```

Find me on [medium](https://medium.com/@jsmanifest)