Getting started with recursion for tree traversal

Have you ever encountered a problem you felt could be solved with recursion, except you didn’t know where to start? Or did it seem like you had to hack your way to a solution?

The first part of tackling recursion is understanding when a problem calls for it. Recursion can be used when the problem can be modeled as a recurrence relation. A recurrence relation is a rule for finding future values from previous values. The Fibonacci sequence is an example of a recurrence relation. Recursion can also be used when the data is defined recursively. A filesystem can be defined recursively because each directory is made up of other directories.

The second part is understanding how to implement a recursive function. In this post, I will show you techniques for using recursion to traverse recursive data structures.

Finding items in a tree

A recursive data structure is similar to a tree. In code, this translates to an array of arrays or an object whose keys are other objects. Our case study will be a tree that models the neighborhoods in the city of New York. The root of the tree is New York. It has two children, Manhattan and Brooklyn. And Manhattan has two children, Harlem and Upper East Side.

This is the list representation of our tree:

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

We will implement a function, includes, to test if our list contains the specified item. The function will return true if it finds a match, otherwise false.

There are three parts to this function. First, the base case. Our function will be reducing the list at each step until we have a list with no elements. Next, is the case when we are looking at an individual node. A node would be the string 'Manhattan'. Last, is the case when the element is another list or subtree. The list ['Harlem', 'Upper East Side'] is a subtree.

This is the skeleton for these three cases:

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

The isEmpty function returns true if the list has no elements. If all the elements in the list have been traversed and no match has been found, the function returns false. The first function returns the first element in the list. The isNode function returns false if the element is a list.

In the else if you want to test if the current element matches the item you are searching for. If it is, you can return true. If it isn’t, you need to recur on the rest of the list.

<

div class=”section-inner sectionLayout–insetColumn”>

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