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.
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)); } }
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))); } }
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.
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:
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.
Deploying a Node-based web app or website is the easy part. Making sure your Node instance continues to serve resources to your app is where things get tougher. If you’re interested in ensuring requests to the backend or third-party services are successful, try LogRocket.
LogRocket is like a DVR for web and mobile apps, recording literally everything that happens while a user interacts with your app. Instead of guessing why problems happen, you can aggregate and report on problematic network requests to quickly understand the root cause.
LogRocket instruments your app to record baseline performance timings such as page load time, time to first byte, slow network requests, and also logs Redux, NgRx, and Vuex actions/state. Start monitoring for free.
Hey there, want to help make our blog better?
Join LogRocket’s Content Advisory Board. You’ll help inform the type of content we create and get access to exclusive meetups, social accreditation, and swag.
Sign up nowJavaScript’s Date API has many limitations. Explore alternative libraries like Moment.js, date-fns, and the new Temporal API.
Explore use cases for using npm vs. npx such as long-term dependency management or temporary tasks and running packages on the fly.
Validating and auditing AI-generated code reduces code errors and ensures that code is compliant.
Build a real-time image background remover in Vue using Transformers.js and WebGPU for client-side processing with privacy and efficiency.