How to Use Recursion in Javascript: A Practical Application
Disclaimer:
I got involved in some new-feature development on my good ‘ol Capstone App for Austin Coding Academy this weekend. This left me inspirationally drained and intellectually worn out enough that I almost completely forgot I had a blog post to write as well.
I’m losin’ it, here…
I usually cover something I learned in class this week, but since we’re very near the end of the course our classes have been a lot of tying up concepts that we’ve already been familiarized with.
Some important concepts have been introduced and then left behind as we move on to other things. That’s why I’m going to bring the focus back real quick to a method that is very powerful, but often gets avoided or worked-around because it’s “too hard” or “complicated.”
That method is recursion.
Definition:
Here’s what wikipedia has to say about recursion:
In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.[1] Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. At the opposite, recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.[2]
Which is a fine way of saying that we want to keep calling the same function over and over again expecting different results.
That’s a little egregious, because we’re not actually calling the same function over and over. The function calls itself again to repeat the same steps but with a different starting value, which, coincidentally is the ending value of the previous time we called it.
The reason I’m making this post is because after years (decades) of having recursion just explained over and over again with the same rudimentary examples every time (Towers of Hanoi? Factorials? Curse you, Fibonacci!), I finally thought of an algorithm that totally makes the concept make sense.
And here it is
The Perfect Example Doesn’t exis —
Without further ado, let’s dive into the best example of recursion you’ll ever need!
const bottlesOfBeer = (bottles)=> {if (bottles===0) {return "no more bottles of beer on the wall. You don't have to go home, but you can't stay here. You're drunk!"}console.log(bottles + " bottles of beer on the wall\n" + bottles + " bottles of beer!\nTake 1 down, pass it around\n" + (bottles-1) + " bottles of beer on the wall!\n\n");return (bottlesOfBeer(bottles-1));}console.log(bottlesOfBeer(99));
Yessir, that’s the whole thing. It’s the old drinking song that nobody has ever made it all the way to the end of. And it uses recursion! Here’s the repl.it so you can mess around with it.
Let’s break it down.
We’ve got our function, bottlesOfBeer that starts off with 99.
The first thing we do is check to see if it’s 0, because if it is, then we’re done already. If it is 0, then we return a message that says you’re out of beer. One of the most heartbreaking conditions of the human experience.
If it’s not zero, then we have to take another beer down and pass it around, as we’ve so eloquently explained in the next line.
console.log(bottles + " bottles of beer on the wall\n" + bottles + " bottles of beer!\nTake 1 down, pass it around\n" + (bottles-1) + " bottles of beer on the wall!\n\n");SO now we’re left with 98 bottles of beer. So we want to start off just like that was the only number we ever cared about. Now we call the function again like this:
return (bottlesOfBeer(bottles-1));Notice how we use the “return” statement here. That’s telling the browser that the value we’re trying to get from calling this function is the value we’re going to be sending back to the line that originally called the function.
What’s happening?!
Each time the number changes, it’s still not zero (until it is), so we keep calling this same function over and over, sending an ever smaller start parameter.
Then once it hits 0, we send back a message telling the original caller we’re done (from the first line).
There in the middle where we’re doing our console log of the song lyrics you could actually be doing anything; pushing objects onto an array, nesting comment components in React, or counting beers.
So what?
I hope now it makes more sense, because it’s not something you should be familiarized with, but something you should be intimate with. Even though the occasions where you might need recursion seem rare, in reality, they’re very useful if you just know these two things:
- How to recognize the need for them
- How to implement them
One area coming up that you can expect to need at least a working relationship with recursion will be in API management. As standardization and structure evolve you get nested objects that you don’t know how far they go. Somebody has to retrieve them and somebody has to nest them. And I’m not talking about the bad APIs, either. I mean the really good ones.
And probably something something machine learning.
Quantum!
Pro-Tip: pay zero attention to code snobs who would try to tell you this example is too trivial. It’s literally the foundation of this:
Go ahead and follow a little array called ‘children’ in this great Hacker News API to see what I mean. Here’s a working demo of it using recursively nested components. And here’s where I tell you how to do it!
I’ll leave you off with another real-world example…
