The Fundamentals of Recursion
Utilizing the Call Stack in Javascript
In my last post, I introduced the basic concept behind Big O notation and how we use it to analyze the efficiency of our functions. We talked through the differences between calculating time complexity and space complexity as well as gaining an understanding that Big O is generally a practice in measuring general trends rather than precise calculations.
To recap a single idea from Big O, one of the most common ways we work with sets of data, whether it be a string or array, is through iteration. This can occur in the form of while loops, for statements, or anything that begins with the first element, and works through each subsequent element in the data set. Since Big O focuses on the worst case scenario, we can say that iteration generally has a time complexity of O(n), because if the size of our data set is n, the function would potentially have to perform n number of operations before finishing.
In many cases, this may be an acceptable approach, but can we do better? It turns out, in many of the same cases, we can! Recursion is a cleaner alternative to basic iteration that is utilized in everything from basic functions to object traversals and complex data structures. Let’s take a look at what recursion entails.
Defining Recursion
When I was a child, we had a set of Russian matryoshka dolls on our bookshelf. While the painted faces still give me the heebie-jeebies, let’s compare recursion to how these dolls work.
You start out with a single large doll. When you open it, you find a slightly smaller doll inside. You take the smaller doll out, open it, and out appears an even smaller doll. This continues until you finally reach the tiniest doll of them all, made out of a single piece that does not open. In a sense, this is how recursion works!
In order to make a function recursive, two components are required: a base case and different inputs. We can think of the base case as the smallest doll inside the Russian dolls. Different inputs can be likened to each larger doll of sequential sizes.
What does this mean? Well, once we find the smallest doll, that’s the end. We can no longer open that doll to find more dolls. In the same way, a base case is how we end the recursive process. Let’s take a look at our first recursive function in Javascript.
Base Case in Recursion
In a recursive function, it’s generally a good idea to write the base case first in order to avoid something called stack overflow. We will talk about what the stack is in a moment, but first let’s reiterate why the base case is so important.
Recursion is quite simply just another form of looping like iteration. The only thing that can put an end to our recursive function is the base case. Otherwise, just like an infinite while loop, our recursion will keep going forever until our computer forces it to crash.
I always like to think of the base case as a big red stop sign. When you get to the base case, STOP. With this in mind, we can now write a base case for our countDown function:
Different Inputs in Recursion
Since we are only working with positive numbers and we don’t want to print anything to the console lower than zero, we return out of the function once num equals 0. However, just writing a base case by itself won’t work. As it is, unless the number passed in is zero, nothing else will run at all!
That’s where different inputs come in. Another way we define a recursion is by how a recursive function will call itself within the function. The only catch is it must have a different input each time. In the same way that Russian dolls wouldn’t fit inside each other if they were all the same exact size, we can’t call a function within itself if the input is identical. We must pass in a different value each time, until we finally reach the base case at the end. Again, think of this like how we keep opening smaller and smaller dolls.
In the countDown function, how do we pass in different inputs until we reach zero? By subtracting the input number by one each time!
After putting together our base case with an else block that decrements the input each time, we have our completed countDown function using recursion!
The Call Stack
An entire blog could be devoted to talking about the data structure known as the call stack (and I would be very under-qualified to take on the task), but instead of that, let’s do a quick crash course on how recursion operates with it.
What does the call stack have to do with recursion? Any time a function is invoked within the context of another function, Javascript pushes it to the top of the call stack. In order to visualize this, we’ll use our countDown function and pass in the number 5 as an argument. When we call this function, countDown(5) is placed at the beginning of the call stack.
The function begins to run. Is 5 equal to 0? No. Therefore, we redirect to the else branch, print 5 to the console, and call countDown using a smaller input (countDown(n-1).
What is happening here? Well, if we think about it, can our original countDown(5) finish running by itself? It cannot because it needs to wait for a return value from countDown(n-1) inside it. In this case, that would be countDown(4). The bottom of our call stack “waits” until the function above it finishes running.
countDown(4) begins its operations. Is 4 equal to 0? Nope. We go to the else branch, print out 4, and invoke countDown of 4 minus 1.
As Harvard professor David Malan eloquently puts it, think of the call stack as a pile of books or a stack of trays in a cafeteria. If we tried to take a book from the bottom of a pile of books, the whole thing might topple. Therefore, we need to remove books from the top before we can grab a book from the bottom.
In a similar way, when you enter a cafeteria and pick up a tray for your food, which one do you grab? In most cases, the one from the top of the pile right? Going through the trouble of taking the tray at the bottom of the stack would be an insane thing to do! And finally, when you’re finished eating and the tray is ready to be used again, where is it put back to? The top of the pile or stack.
Let’s keep going with our countDown function. countDown(3) is invoked, 3 is not equal to 0, so countDown(2) is placed at the top of the call stack after printing 3.
And the same thing happens again with countDown(1).
Inside countDown(1), we call the function itself yet again with countDown(0).
With countDown(0), we finally reach the base case! Is 0 equal to 0? Yes indeed. We print 0 and at last reach the return command. Again, this return functions as our recursion “stop sign”. Once you reach the base case, STOP!
Getting a return from countDown(0), it is “popped” off from the top of the stack and countDown(1) can resume running. countDown(1) finishes and pops off of the stack. We can return to countDown(2), and the same thing continues until our stack is empty again.
Keep in mind, we are returning a NULL value at the end of countDown, as the purpose of our return is only to know when to stop printing numbers to the console. However, this same concept of using the call stack and pushing/popping items from the top can work just as easily in a function that adds multiple numbers together, produces an array of values, or anything else.
Anytime a function is called while other functions are running, Javascript and many other programming languages allow us to utilize this data structure. As mentioned earlier however, always make sure any recursion you implement with the call stack contains a base case.
If we had neglected to add a return at the very end of our countDown stack, OR if we had not changed the input at every invocation, the function would have resulted in stack overflow, a data structure that has exceeded the stack bound permitted.
Conclusion
There are many other advanced ways to implement a recursive function, but we have now learned the two main components that make this method possible. Other strategies such as helper method recursion and pure recursion can make solving difficult problems much easier. Although it’s not the case all the time, recursion can also improve the Big O of a function. In some cases, recursion allows us to achieve time and space complexities ranging anywhere from O(n) to O(1) constant time.