Skip to content

Practical Recursion

Introduction

Recursion is one of those programming concepts that I have found extremely difficult to find a practical use for. Often I've seen examples that focus on things like math problems. Here's how to calculate a factorial using recursion for instance -

const factorial = num => {
  if (num > 1) {
    return num * factorial(num - 1);
  } else {
    return 1;
  }
}

That's fine I guess... But I've never had to calculate factorials at work. So here's an article about a practical example of recursion! Excited!? Let's go!!!

Shameless plug

Before going any further, I'm basing this article on the work I've done on the a11y-menu open source project I've been working on for a while. If you're curious, please check out the npm package and github repo. Now... on with the article.

Trees

Recursion is helpful when it comes to navigating through tree-like structures. What's that you ask? Well... a file system is a tree-like structure. It has a root, branches, etc... Another example we see in web development all the time is -

Navigation Menus

Yep. That's right. Navigation menus are tree-like structures. Consider this outline of a nav menu for a hypothetical web development and design group.

  • Home
  • About

    • Our Team
    • Adam
    • Bob
    • Claire
    • Our Story
  • Portfolio

    • Web Development
    • Web Design
    • Consulting
  • Contact

Each of these parts of the site structure would have

  • a link
  • a display name
  • a heirarchy
  • etc...

I'm going to turn the outline above into data which I'll use to create a menu.

JSON

Here's the menu outline as a json object. See how it has the same "shape" as the menu above? That can be used to great advantage to get the output you want.

The way the data looks should mirror the way the markup will look.

{
  "menu": [
    {
      "name": "Home",
      "slug": "",
      "link": "/",
      "sub": false
    },
    {
      "name": "About",
      "slug": "about",
      "link": "/about",
      "sub": true,
      "menu": [
        {
          "name": "Our Team",
          "slug": "our-team",
          "link": "/our-team",
          "sub": true,
          "menu": [
            {
              "name": "Adam",
              "slug": "adam",
              "link": "our-team/adam",
              "sub": false
            },
            {
              "name": "Bob",
              "slug": "bob",
              "link": "our-team/bob",
              "sub": false
            },
            {
              "name": "Claire",
              "slug": "claire",
              "link": "our-team/claire",
              "sub": false
            }
          ]
        },
        {
          "name": "Our Story",
          "slug": "our-story",
          "link": "/our-story",
          "sub": false
        }
      ]
    },
  // etc...
  ]
}

From here, you can use these data just like you would the response from an API.

Making a Menu

What we want are two functions

  • One that will create the interior html of each menu item. For instance: links, buttons, spans, etc...
  • Another that will

    • create each list item with the innerHTML
    • aggregate all that markup
    • call itself again (recursively) if the item should have a submenu like for the "Our Team" or "Portfolio" items.

I'll start with that one first. Taking a cue from other javascript libraries, this next function will create an array map that will be used to attach the items to an unordered list.

// displayMenu requires a ul to attach the markup to and the menu data
const displayMenu = (ul, json) => {
  const menuMap = json.map((menuItem, index) => {
    // create each element
  })
  
  // append each item of the map to the list
  menuMap.forEach((item, index) => {
    ul.appendChild(menuMap[index])
  });
  
  // return the output
  return menuMap;
}

Creating list items

The next task is to create the <li> elements that will contain the links, text, and submenus. The array map method is the place to handle this!

const displayMenu = (ul, json) => {
  const menuMap = json.map((menuItem, index) => {
    // create each element in the menu
    const li = document.createElement('li');
  })
  
  // append each item of the map to the list
  menuMap.forEach((item, index) => {
    ul.appendChild(menuMap[index])
  });
  
  // return the output
  return menuMap;
}

At the moment, these are completely empty elements. So, the next thing to do is write a function that will supply the markup that goes inside them. This function will

  • check for the presence of links and/or submenus
  • create appropriate markup depending on the individual case
  • return the correct markup

Since it will run inside the map method, it can "know" about each menuItem and take it as an argument.

const generateMarkup = (menuItem) => {
  let hasSubmenu = false;
  let hasLink = false;
  
  // check for links or submenus
  if (menuItem.hasOwnProperty('sub') && menuItem.sub !== null && menuItem.sub.length) {
    hasSubmenu = true;
  }

  if (menuItem.hasOwnProperty('link') && menuItem.link.length && menuItem.link !== '#') {
    hasLink = true;
  }
  
  // respond to the different cases
  if (hasLink && hasSubmenu) {
    // create a link for the top level item and a button for the submenu
    return `<a href='${menuItem.link}'>${menuItem.name}</a><button aria-haspopup='true' aria-expanded='false'><span aria-hidden='true'>+</span></button>`
  } else if (!hasLink || !hasLink && hasSubmenu) {
    // create a button that will act as a toggle for the submenu
    return `<button aria-haspopup='true' aria-expanded='false'>${menuItem.name}<span aria-hidden='true'>+</span></button>`
  } else {
    // create a basic link 
    `<a href='${menuItem.link}'>${menuItem.name}</a>`
  }
}

In a future post, I'll get into the aria- attributes, why it's useful to use both links and buttons, and discuss web accessibility in the context of navigation. For now though I want to focus on the recursive parts of the post.

Creating top level markup

Now, you can create the interior markup of each item in the list.

const generateMarkup = (menuItem) => {
  // code from above...
}

const displayMenu = (ul, json) => {
  const menuMap = json.map((menuItem, index) => {
    // create each element
    const li = document.createElement('li');
    
    // create the interior markup for each one.
    li.innerHTML = generateMarkup(menuItem);
  })
  
  // append each item of the map to the list
  menuMap.forEach((item, index) => {
    ul.appendChild(menuMap[index])
  });
  
  // return the output
  return menuMap;
}

Recursion

Finally we get to the recursive part of the script. Right now, the displayMenu function only handles the top level of each item. In this case, that would be:

  • Home
  • About
  • Portfolio
  • Contact

What's needed is a way to know if the item has "children". Once you know that, it's time to handle them by calling the displayMenu function inside itself repeating the entire process over again.

const displayMenu = (ul, json) => {
  const menuMap = json.map((menuItem, index) => {
    // create each element
    const li = document.createElement('li');
    
    // create the interior markup for each one.
    li.innerHTML = generateMenuItemMarkup(menuItem);
    
    // find out if there are submenu items
    // - does the sub property exist for the menuItem?
    // - is it true?
    // - is there a menu property with a "truthy" length (1 or more items)
    if (menuItem.hasOwnProperty('sub') && menuItem.sub === true && menuItem.menu.length) {
      
      // get ready to recurse
      
      // create a new submenu 
      const subMenu = document.createElement('ul')
      
      // recurse!
      displayMenu(subMenu, menuItem.menu);
      
      // attach the completed submenu to the current <li> and return
      li.appendChild(subMenu)
      return li;
    }
    return li
  })
  
  // append each item of the map to the list
  menuMap.forEach((item, index) => {
    ul.appendChild(menuMap[index])
  });
  
  // return the output
  return menuMap;
}

Notice that the arguments for displayMenu become the sub-menu <ul> and the new menu property of the current item. This way the same function can be re-used

Conclusion

The nice part about this approach is that the shape of the data can be used in a predictable and repeatable way. The data and the menu will come out looking the "same". This has several advantages

  • The structures are predictable
  • The code is maintainable
  • The code can be applied to other languages (there's nothing here that's unique to javascript)

I hope that this has been more interesting than calculating number sequences and that you can use a similar approach on one of your projects.