Getting started with recursion for tree traversal

const locations = [
  'New York', 
  [
    'Manhattan',
    [
      'Harlem', 'Upper East Side'
    ]
  ],
  [
    'Brooklyn'
  ]
];

function includes(item, list) {
  if (isEmpty(list)) {
    ...
  } else if(isNode(first(list))) {
    ...
  } else {
    ...
  }
}

This is the updated code:

function includes(item, list) {
  if (isEmpty(list)) {
    return false;
  } else if(isNode(first(list))) {
    if(first(list) == item) {
      return true;
    } else {
      return includes(item, rest(list));
    }
  } else {
    ...
  }
}

The rest function returns the list without the first element. This is how we are reducing the problem so that reach the base case, an empty list. The else if block of the conditional statement could have also been written as:

return first(list) == item || includes(item, rest(list));

It does the same job, but more succinctly. I prefer this line of code to the nested if statements.

Last, in the else block we need to recur on the first element because it is a list and recur on the rest of the list. This is the code for the else block:

return includes(item, first(list)) || includes(item, rest(list));

Putting it all together, you now have:

function includes(item, list) {
  if (isEmpty(list)) {
    return false;
  } else if(isNode(first(list))) {
    return first(list) == item || includes(item, rest(list));
  } else {
    return includes(item, first(list)) || includes(item, rest(list));
  }
}

Removing items from a tree

Next, we will implement a function remove that takes a string and a list as input and returns the list with all occurrences of the string removed. In a real tree, you might be interested in removing a node along with all of its children. For simplicity, we will only look at the case for removing an individual item.

Removing an item from a list is similar to finding its members, except we need to make sure we are keeping a reference to our list as we recur on its subparts.

The three cases will be the same:

function remove(item, list) {
  if (isEmpty(list)) {
    ...
  } else if (isNode(first(list))) {
    ...
  } else {
    ...
  }
}

Because this function returns a list, our base case will return an empty array. The new list will be built by copying all of the items from the list except the item to be removed.

If we were removing an item from a one-dimensional list using a for loop, the function might look like this:

function remove(item, list) {
  let result = [];
  for (let i = 0; i < list.length; i++) {
    if (list[i] != item){
      result.push(list[i]);
    }
  }
  return result;
}

For the recursive implementation, the test goes in the `else if` block. If the current element equals the item, we recur on the rest of the list. This has the effect of removing the item. However, if the current element is not the item, then we have to save that part to concatenate to the rest of the list we are recurring on. When the function reaches the base case, all of the concatenations that were deferred will be added to this list.

function remove(item, list) {
  if (isEmpty(list)) {
    return [];
  } else if (isNode(first(list))) {
    if (first(list) == item) {
      return remove(item, rest(list));
    } else {
      return concat(first(list), remove(item, rest(list)));
    }
  } else {
    ...
  }
}

The concat function here joins the two inputs into one list.

In the else block we define the case where the current element is a list. We need to recur on that part and recur on the rest of the list. Additionally, both parts will need to be concatenated into one list. This is what we end up with:

function remove(item, list) {
  if (isEmpty(list)) {
    return [];
    } else if (isNode(first(list))) {
    if (first(list) == item) {
      return remove(item, rest(list));
    } else {
      return concat(first(list), remove(item, rest(list)));
    }
  } else {
    return concat(remove(item, first(list)), remove(item, rest(list)));
  }
}

Exercise

Implement a function, occur, that takes a string and a list as input and returns the number of times the string appears in the list. First, set up your three cases. What should you return in your base case? What should you do when you have a node? What should you do when you have a list? Use the previous two examples as a guide.

Conclusion

The techniques used for finding and removing items can be extended to solving many other problems that require tree traversal. Trees can be used to model the moves in a game or for performing a binary search. When implementing a recursive function, keep these points in mind:

• Define the base case
• Define the case where the element is a node
• Define the case where the element is a list
• In the recursive call, change the arguments so that the function reaches the base case

Another point to consider is that recursion may not always be the most efficient way to solve the problem. That is why you should remember that any problem that can be solved using recursion can also be solved using `for` and `while` loops. You would choose recursion over a loop when the benefits of having a simpler solution outweigh the costs of efficiency.

Finally, the examples shown here are just one way to solve these kinds of problems. Use them as a starting point and read the resources listed below for a deeper understanding.

Further reading

• Understanding Recursion With JavaScript
• The Little Schemer
• Discrete Mathematics and Its Applications: Chapter 5 Induction and Recursion
• The Structure and Interpretation of Computer Programs: Chapter 1.2 Procedures and the Processes They Generate
• Gödel, Escher, Bach: An Eternal Golden Braid: Chapter 5 Recursive Structures and Processes

---

Plug: LogRocket, a DVR for web apps

LogRocket is a front-end logging tool that lets you replay problems as if they happened in your own browser. Instead of guessing why errors happen, or asking users for screenshots and log dumps, LogRocket lets you replay the session to quickly understand what went wrong. It works perfectly with any app, regardless of framework, and has plugins to log additional context from Redux, Vuex, and @ngrx/store.

In addition to logging Redux actions and state, LogRocket records console logs, JavaScript errors, stacktraces, network requests/responses with headers + bodies, browser metadata, and custom logs. It also instruments the DOM to record the HTML and CSS on the page, recreating pixel-perfect videos of even the most complex single page apps.

Try it for free.