How to be Recursive
Wrapping up my last learning module at Flatiron School before tackling my final project, I’ve been reflecting on and being proud of how far I’ve come while simultaneously stressing out about what’s ahead. On one hand, I went from having absolutely 0 (zero! No lie!) experience with coding to writing full-stack applications. On the other, if you asked me what an algorithm is, I’d probably just smile and wave.
So, for the past couple of weeks, I’ve been doing some heavy-duty Googling. My search history includes, “what is an algorithm,” and “why do I need to know what an algorithm is,” and, of course, “which algorithms should I study for my technical interviews.” All of the results either briefly mentioned or were completely focused on this idea of a recursive function or algorithm.
Does the word “recursive” also scare you? Nice. The first step to understanding is to realize it’s just a word made up by some people (white men*) to intimidate others (non white men) and consequentially steer them away from entering the world of STEM. But, more about inclusion in tech in another article…
Now that we’ve gotten that phobia of big scary words out of the way (it’s actually called Hippopotomonstrosesquippedaliophobia LOL), let’s break down what “recursive” really alludes to. As GeeksforGeeks puts it, recursion is:
“The process in which a function calls itself directly or indirectly...”
But what does that really look like? In the following example, I’ll unpack this definition with everyone’s best friend: math.
Factorials are fun because they’re really easy to understand. Let’s say you are wandering around the neighborhood and someone approaches you with a clipboard that reads, “Solve this: 5!” (this is a very realistic example). The “5!” signifies a factorial; i.e., 5*4*3*2*1 (5 * (5–1) * (4–1 )* (3–1) * (2–1)); i.e., take the integer (a whole, or non-decimal, number) in front of the exclamation point, and multiply it by all the integers counting down to 1.
Let’s abstract away from hard-coded integers. Let’s take n, which represents any integer. To find n!, we would do: n * (n -1) … [more math depending on what integer you start with] … * 2 * 1. No matter where you start on the integer line, you’ll always end a factorial by multiplying by 2 (and then by 1, but that doesn’t really do anything). If you didn’t notice, were computing a bunch of factorials just to find n!. Going back to n = 5:
5! = 5 * 4 * 3 * 2 * 1
4! = 4 * 3 * 2 * 1
etc.
You could solve 5! by running 5 * 4! which you could solve by running 5 * 4 * 3!. What we’re doing here is recursive. The factorial is taking the first integer, n, and then multiplying it by the integer 1 less than n’s factorial, and so on and so forth. In a (JavaScript) function, it would look something like this:
The function factorial (which is being declared as an arrow function hence why the deprecated sandbox I was working with does not like it) is calling on itself, thus behaving recursively. The first part, with the n === 0 mumbo jumbo, is mathematically correct. 0! = 1. You can Google it if you have doubts. If n !== 0, then it says, “please call on yourself with the integer one less than n, do so until n === 0, and then get the product of all of these integers.”
To behave recursively is to return deeper and deeper into yourself until you are at your base and there is no deeper possible level you could access and perform your function on. Or, as the Geeks (see above) would put it, “to call on [yourself] directly or indirectly” until you are unable to do so. So the next time your interviewer asks, “How would we do so recursively?” just get really existential with them.
*Oh yeah, about the white guys. The most influential people in the world of recursion are Richard Dedekind, Edsger W. Dijkstra, Joseph McCarthy (for some reason), and Peter Naur, to name a few.