With nights taken up learning and writing React, Angular JS, and Backbone, my morning toy problems have been a welcome distraction this past week. And from once, not so long ago, being fearful of recursion - I've gotten to really enjoy these challenges. Here's the most interesting recursion toy problem I was presented with this week - Deep Equality.
Here are the rules:
---Write a function deepEquals that takes in two objects and returns whether
---or not the two are deeply equivalent. This means the structure of the two
---objects is the same, and so is the structure of each of their corresponding
---descendants.
Easy enough right? Let's get some IOCE out there to help us out:
Input: two objects
Output: boolean
Constraints: there's a test that says not to use JSON.stringify
Edge Cases:
What to do now? We are going to have to go into an object and check for equality - then we're going to have to go into any nested objects and check for equality, and if that object has another nested object... and so on. Smells like our old friend recursion. So let's get this set up:
The boolean is going to be returned as true unless we have any reason to change it to false. We've also got the bones of our recursion and the call to it on line 12. Now it's time to build out our recursion. The first thing we should check is to see if the first layer of the objects have the same number of keys. If the second object had more keys than the first, it could trigger a false positive (and there is definitely a test for that!). Change the boolean to false if they aren't the same length.
So now that we know the lengths are the same, let's compare actual key/value pairs. We can run a forEach loop on one of our objects. If that key does not exist in the other object or the value is not the same, we need to change the boolean to false.
Else - if we've made it this far... let's check the typeof on the value of the key to see if we're still dealing with an object. If we are, we need to keep going... let's call the recursion on this object.
So once our recursion is finished, our boolean is either changed to false or it has not been - let's return the boolean to complete this exercise.
What a difference a few weeks makes. Recursion has gone from being my sworn enemy to an arrow in my JavaScript quiver. If you're not there already, with a little patience and diligent work you soon can be.
Top comments (0)