Recursion

10.15.22

I have been wanting to write a blog post about data structures and algorithms and since it’s October and officially horror movie season, I figured I would start by picking the scariest topic I could think of. A topic feared by comp-sci students, aspiring coders and sometimes even seasoned devs. Recursion.


I think one of the big reasons that recursion is so feared is because it is very avoidable. Anything that uses recursion can be accomplished with iteration of for loops. A close second is definitely because it actually can be pretty confusing. Third might be because it can break code easily. If you don’t have a base case, you can send your code into an infinite loop. Fourth would probably be that using recursion doesn’t even necessarily mean improving the space and time complexity of your algorithm, meaning it probably won’t even increase performance.

Then why use it at all? Recursion can be an elegant way to increase readability. Yes, there are some specific cases where it can improve the time complexity of an algorithm (google Tower of Hanoi if you are interested in a famous one). It sometimes helps with object traversal. It also helps developers write less code by reducing the actual amount of lines they need to write but it most importantly makes certain things easier to demonstrate, explain and read. Which is huge when dealing with super complicated algorithms. This is also why new developers should get a firm grasp on recursion. As a new developer, you will be reading a lot of other people’s code. And let’s be honest, recursion is a favorite topic for interviewers.

Face the fear. What is recursion? To put it simply, recursion is when a function calls itself. Technically not exclusive to computer science, recursion occurs when a thing is defined in terms of itself. I am obviously talking about it in terms of computer science and for this blog post I will stick to JavaScript for examples and context, even though recursion is possible in (probably) all programming languages.

Functions use other functions all the time. When a function is passed to another function as an argument that is called a callback function.


Mandatory Inception meme. Except a recursive function isn’t just a function within another function. Again, it is when a function calls itself. Let’s just get into an example. A famous use case for recursion is finding the factorial of a number. In case you need a little refresher on 10th grade math, the factorial of a number is the product of all positive integers less than or equal to the given integer. It is also written with an exclamation mark. So, 5! = 1 x 2 x 3 x 4 x 5 = 120.

That first function above is the recursive function that calls itself. The second is a bonus of doing it with a for loop. Even though these are relatively simple, I think they demonstrate how recursion can actually make code a little easier to read despite the double take of it calling itself.

As I mentioned earlier, a recursive function requires a base case or it will send your code into an infinite loop. It will actually cause a stack overflow. A stack overflow is actually more than just a website where people steal code from. A stack is a linear data structure. In a stack, functions rely on each other to move on. They are either first in, last out or last in, first out. When a function is called it is placed (pushed) on top of the call stack and when JavaScript sees the return keyword or when the function ends, the compiler will remove (pop) it from the stack. An overflow occurs when a function calls itself so many times that the space needed to store the variables and information associated with each call is more than can fit on the stack and whatever is running your code (probably a browser if you are coding in JavaScript) stops or crashes. A base case is usually a conditional statement to end the loop.

The last thing I want to share here is a weird little story that kind of stuck with me and can help you understand recursion for problem solving. The setup is weird, don’t overthink it. A little boy is hanging out with a stubborn dragon. The little boy has a list of numbers and needs to know which numbers are odd and which are even and asks the dragon for help. The stubborn dragon says he will only tell him if the first number in his list is odd or even. So the little boy asks the dragon about the first number in his list and gets his answer. Then instead of quitting, he removes that first number from the list and asks the dragon again and gets his answer for the second number and repeats that process until he has all of his answers. This clever hypothetical boy was using a recursive algorithm.