This post originally appeared on my personal blog
If you're a self-taught programmer like me, there's a good chance you're terrified of the idea of recursion. I wasn't a Computer Science major, so I always avoided recursion like the plague. I knew it had something to do with repeating something and maybe it involved a function calling itself? But how would you do that? Why would you do that?!
Put simply, recursion is a function that calls itself over and over, until the desired result is reached. That definition may or may not clear things up for you too much. Let's look at the example that helped the concept click for me. Don't worry, it's not the same old factorial example you're used to.
The first time I actually understood recursion, I actually stumbled across it by accident. It just so happened to be the best way I could think of to solve the problem I had. The basic premise of what I was doing was pulling down primary keys from a database and turning them into variable declarations for a code generator. So if the database returned client xyz id as 2483954, I needed to output const CLIENT_XYZ_ID = 2483954. Simple enough, right?
Of course, variable names can't have spaces in them, so I needed to replace the spaces in the value with underscores. That's easy. I could have a function that does something like
function formatVariableName(databaseValue) {
return databaseValue.toUpperCase().replace(/ /g, '_')
}
(If you're unfamiliar with RegEx, this basically just says replace every space in the string with an underscore.)
However, I ran into an issue. The database fields were filled in by account managers, who had little concern for my weak RegEx skills. As such, they often had multiple spaces in a row, but I didn't want my script outputting variable names with multiple underscores in a row. So now what?
Well, I could do something like
function removeDuplicateUnderscores(variableName) {
return variableName.replace(/__/g, '_')
}
where we replace instances of 2 underscores with 1 underscore.
That works great if there's only two underscores in a row. What kind of programmer would I be if I assumed that? However, knowing that this function would work if we knew there were only two underscores in a row happens to be a very important fact to know in order to write a good recursive solution here. That's because recursive functions have base cases. A base case is simply a test that determines if the function needs to run again, or if its job is done.
So what if we told our function to keep running until there were no instances of more than 1 underscore in a row? (This snippet will use RegExp.prototype.test)
function removeDuplicateUnderscores(variableName) {
if (!/__/.test(variableName)) return variableName
return removeDuplicateUnderscores(variableName.replace(/__/g, '_'))
}
Let's step through what this is doing...
First is the base case. How do we know when this function has done its job? When there's no more instances of two underscores in a row. So this line merely tests for the existence of two consecutive underscores. If there aren't any, we're done! Return that value.
The next bit is the actual recursion. The value we pass to the function is the variableName, but with every set of two consecutive underscores replaced with one underscore. Just like we did earlier. But that value is then passed into removeDuplicateUnderscores again, just in case there are still cases of __ in there. That will be repeated until we have reached our desired outcome, AKA our base case.
I hope this example helps you as much as it did me. Even if it only helps a little, I hope it shows you that recursion really isn't anything crazy. I encourage you to open your browser console and play around with these functions. Test them out, see if you can break them, see if you can improve them.
Disclosure
In case you were wondering if there's a better way to do this, there is. It can be done solely by improving upon my RegEx, rather than using recursion. Luckily, this has no impact on the teachability of this example.
Top comments (0)