An Intro Guide To Recursion

I recently completed a software engineering bootcamp with Flatiron School. Now that I’ve completed the bootcamp I’m working on preparing for technical interviews. Software engineering interviews famously consist of being able to solve code challenges on the spot, that often consist of being able to come up with some algorithmic function to solve some type of problem.

There are many different possibilities of things you may want to know in this type of situation. Here I’m going to dig into one concept I’ve been working on recently, and that’s recursion.

What Is Recursion?

Recursion can be a confusing concept to grasp at first. At its simplest what recursion is, is just calling a function within itself. This may make your head spin, but you’ve probably seen it before even if you weren’t focused on the fact that it was recursion.

Often times in programming we need to loop through sets of data. Typically the initial way we learn to do this is to iterate through the data using some type of looping method. And when we talk about looping we’re talking about iterating. This is at least what I learned over the course of my bootcamp. Recursion is almost like looping except instead of going through each element in a set of data, what you’re doing is continuing to call the function while manipulating the input until a condition is met.

Why Should We Know About Recursion?

Why can’t we just iterate in every situation? Why is it important to know about recursion? Well for one thing it’s important to know for going on technical interviews. If someone asks you to implement something recursively, or asks why you chose not to implement something recursively, you want to be able to at the very least understand the concept enough to answer the question effectively. But beyond just interviewing, sometimes implementing something recursively is a good strategy to take. It can often times look much cleaner, and be clearer for other devs to understand how your function is working. There are certain situations (examples coming later) where it just makes more sense.

The Call Stack

Before I get into some examples of actually implementing recursive functions, I want to briefly talk about the call stack. The call stack is basically how functions are run within a system, like your browser for instance. The call stack is based of the principles of the “stack” data structure which operates by stacking data on top of each other, then interacting with each piece from the top down.

If you’re fuzzy on this you can go google and read more about it, but the reason I’m mentioning it here is because in order to really understand how recursive functions operate, you need to understand at least somewhat how the call stack works.

For now just know that when functions get called they get added to the call stack, one on top of the other. Then the functions resolve from the top down. So when you have a recursive function, as it continues to call itself, more functions get added to the call stack. Then they resolve in the reverse order until resolving the original function call. Here’s a visual that will maybe make a little more sense:

How Do We Implement Recursion In A Function?

Ok so what does recursion actually look like in practice. As I’ve said we’re going to use the function itself within the function in order to repeat certain steps. Here’s a simple example using the mathematical concept of factorials:

So without getting too deep into the mathematical part of this, basically we want to multiply the original number with each consecutive descending number until we get to 1. So if num starts out as “4” we want to do 4 x 3 x 2 x 1, and that gives us the factorial of 4. This is a great use case for recursion because we want to repeat the same action over and over again just with a slightly different input. So we know that once we get to 1 we just want to return 1 so that’s where we start, and it stops us from calling our function infinite times. Then we just multiply the original num by the result of the function minus 1 until we get to 1.

So if we go back to the call stack we can see how this actually happens programmatically. First the original function gets called, added to the stack, and starts to run. But when it get’s to the inner function call instead of resolving the inner function call gets added to the stack on top of the original function call. This continues on however many times the recursion repeats, and what’s happening is function calls are “stacking” on top of each other. Once we get to 1 the function at the top of the stack resolves, pops off, and the next function can then resolve as well and so on and so on until finally the original function can resolve and we get our result.

Conclusion

Recursion can be confusing, but it’s a powerful concept in programming, and important to know as you grow your skills as a dev and possibly to nail a technical interview. I’ve only scratched the surface here, but hopefully you’ll start noticing instances where recursion would make sense, or just seeing how others have used it in certain situations. What’s important to remember is that you always need to have a stopping point in your function so you don’t get caught in an infinite function call. Also your input needs to change with the recursive function calls. The more you play around with it, the more it’ll start to click.