Recursion 101

Solve problems recursively by taking it one step at a time

Adam Snyder
Nov 6 · 10 min read
Photo by Tine Ivanič on Unsplash

Welcome to Recursion 101. By the end of this piece, you will have a deeper understanding of solving problems recursively and also of a relating data structure. These are some of the heavier topics in the programming world, and newer programmers often dread the word recursion. Although it would be nearly impossible to explain all these concepts in depth in a single article, you will obtain a stronger grasp of recursion and why understanding a bit about data structures will aid in the overall picture. Like many things you first learn in programming, it seems difficult. But if you take it slow and understand the fundamentals, you’ll realize it’s nothing to be afraid of.


Stack

I believe the stack is an essential building block to understanding recursion. A stack is known as an abstract data type(ADT). An abstract data type means it’s a logical way of picturing data and ways to manipulate the data without going into detail of how it will be implemented. A simple way of remembering this is that an ADT answers the question, what does it do? The actual implementation of an ADT, known as a data structure, answers the question, how does it do it? The how would be represented by the actual programming of the methods detailed by the ADT. ADTs are language-independent. Because it doesn’t specify how it needs to be done, it can be written in any language.

A stack models the behavior last-in, first-out (LIFO). As the name stack implies, imagine a stack of blocks. You put several blocks on top of one another. To remove a block safely without destroying the stack, you remove the one on top, which is the last block you placed. The stack ADT works the same way. You can only remove items you place on a stack in the reverse order you placed them on the stack.


The Call Stack

Perhaps without even knowing it, you’ve been using a stack in all of your code. Your program uses a stack to control the flow of subroutines and to return control to the correct part of your program after certain procedures are performed.

For example, consider this line of code print(user.getName(). From left to right, first we encounter the print() function, so it’s placed on the stack. In the parameters of the print function, a method user.getName() is given as an argument that returns a string. Before the print method can execute, it needs to get the name from the user. Now it places getName() on the stack. This halts the execution of print until getName() has finished executing. Think of this like hitting pause. “Hey, I’m going to let you finish, but pause what you’re doing so I can get this name for you. I’ll grab this name and give it to you so you can continue exactly where you left off.”

With the print() function temporarily paused and user.getName() placed on the stack, user.getName() has control. It goes and gets the name of the user and returns a string to the print() function. After completion of the user.getName() method, it’s popped off the stack and control returns to print(), where it does its job of printing the user’s name. Once it’s finished, it’s also popped off the stack.


Recursion

Okay, now that we’ve created a bit of foundation, this will be a little easier to understand. What is recursion exactly? Recursion is a distinct algorithmic problem-solving technique. That might sound a little intimidating, but it essentially boils down to creating smaller and smaller versions of the same problem until the smallest solution is easily solved and then going in reverse to solve the larger problem piece by piece.

Recursion occurs when a function calls itself over and over again. The function itself is referred to as a recursive function. You might be wondering how a function can call itself and what good that would do. Let’s look at a simple example using exponents.

This is the most simple example I could think of. Honestly, you would never solve exponents this way, but it will allow you to see exactly how recursion works without complicating things too much. How could we solve 3 to the power 3 using recursion? Let’s think of a way we could break down this problem into smaller pieces that are self-similar.

3 to the 3rd power = 3*3*3
3 to the 3rd power = 3 * (3 to the 2md power)
3 to the 2nd power = 3 * (3 to the 1st power)
3 to the 1st power = 3 * (3 to the 0 power)
3 to the 0 power = 1

If you look at the first two lines in the example above, you’ll see that they are two ways to get the exact same answer. The first line is the traditional way you would solve this problem. The second line is a way to resolve this problem recursively.

From the second line down, you’ll notice a pattern or algorithm that can solve this problem. We kept breaking down the problem into smaller and smaller pieces using the same algorithm until we got the smallest problem and the most simple solution: 1 to the 0 power = 1. Let’s look at how we can write a function that would use this algorithm.

public int power(int base, int exponent) {
if(exponant == 0) {return 1;}
return base * power(base, exponent - 1);

Let’s break down this function line by line. The definition of the function power returns an int. It has two parameters. It takes in a base and an exponent.

The second line checks to see if the exponent is 0. If the exponent is 0 we don’t need to break down the problem into smaller pieces anymore. This is known as the base case. I’ll explain more about that shortly. If we’ve reached the smallest the problem needs to be broken down into, it returns 1.(Remember the zero-exponent rule: Any base with an exponent of 0 equals 1).

The third line only gets called if the second line didn’t return 1. This means we can break down the problem into smaller pieces until we reach the base case. This is known as the smaller caller. The smaller version of this problem, according to our algorithm, is base * power(base, exponent — 1). We multiply the base times the power of the base and (exponent -1). Remember earlier we showed that 3*3*3 is the same as saying 3 * (3 to the power of 2)?

Let’s look at what’s happening visually, using the call stack to get a better understanding of the exact process that’s occurring.

We start by calling the function power(3, 3) and that gets added to the call stack:

Now the method runs its course. It checks if 3(exponent) == 0.That's false, so it goes to the next line, return 3 * power(3, 2). Before this function can return the value, we run into another function. So we will pause this current function to get the value of this function being called power(3, 2. This new function gets added to the stack and gains control.

Now the new current method runs its course. It checks if 2(exponent) == 0. That's false, so it goes to the next line, return 3 * power(3, 1). Before this function can return the value, we run into another function again! So we will pause this current function to get the value of this function being called power(3, 1). This new function gets added to the stack and gains control.

Now the newest function on the stack has control. It runs down its code and checks if 1(exponent) == 0. That's false, so it goes to the next line, return 3 * power(3, 0). Before this function can return the value, we run into yet another function! Fear not, though, we are making progress. So we will pause this current function to get the value of this function being called power(3, 0). This new function also gets added to the stack and gains control.

Once again the newest function on the stack has gained control, and we repeat what we’ve been doing. It runs down its code and checks if 0(exponent) == 0. That is true! Finally, we’ve broken down the problem into the smallest version of the problem(the base case). Since we’ve now reached the base case, we can return 1. From here we go back through the stack in LIFO order. Since this function returned 1, it has gone through all of its functionality and we are finished with it, so it’s popped off the stack, and control is given to the prior function with the value of 1.

This is where things get interesting. It’s basically like fill in the blanks all the way through the stack. The function power(3, 1) is what called the function power(3, 0). We paused the execution of power(3, 1) to figure out power(3, 0) and the result was 1. So control now belongs to power(3,1) and we pick up right where we left off. The last remaining part of code in that function is return 3 * power(3, 0). We now know that power(3, 0) = 1, so we can just fill in the blanks. It now becomes return 3 * 1. Simple math tells us 3 * 1 = 3, so we return 3. We are now finished with this function and it’s popped off the stack, and control is given to the next function.

Once again we are just going to fill in the blanks. Since the function power(3, 2) called power(3,1) and we got the 3, we can substitute that in the remaining line of the function. The final line becomes return 3 * 3 and we get 9. This completes this function call and it gets popped off the stack while returning control to the next function on the stack with the value of 9.

Now we are at the initial function call and can solve this problem thanks to recursion and breaking down the problem into smaller problems. The final line in this function left to execute is return 3 * 9. This returns the number 27 and would be the solution to the initial function call power(3, 3). Since this function is now done, we pop it off the stack and we are left with an empty stack. We can double-check our work. Does 3*3*3 = 27? Yes, it does! Solving this problem recursively does indeed give us the correct result


The Three Questions

When attempting to solve a problem recursively, there are three questions you need to ask yourself. This will make finding an algorithm to solve your problem easier. To verify a recursive solution works, we must be able to answer “yes” to all three of these questions.

  1. The Base Case Question: Is there a nonrecursive way out of the algorithm, and does the algorithm work correctly for this base case?
    Answer: Yes, when the exponent reaches 0, we no longer need to make recursive calls and can return 1 instead.
  2. The Smaller Caller Question: Does each recursive call to the algorithm involve a smaller case of the original problem, leading inescapably to the base case?
    Answer: Yes, the smaller caller always involves decrementing the exponent by 1, leading directly to the base case.
  3. The General Case Question: Assuming the recursive call(s) to the smaller case(s) work correctly, does the algorithm work correctly for the general case?
    Answer: Assuming that the recursive call power(base, exponent-1) gives use the correct value, then the return statement computes base * exponent. Yes.

When trying to break down your problem into smaller self-similar problems to solve recursively, make sure to ask yourself these questions before you try to implement your algorithm.


Conclusion

Congratulations! You now have a fundamental understanding of how to solve problems recursively. There are still many ways to expand on this newfound knowledge of recursion. Looking into recursive vs. iterative ways of programing will explain the pros and cons of both. Recursion is used in many functional programming languages such as Elixer. Functional programming is a paradigm of programming just like object-oriented programming is also a paradigm. Also, there is tail call optimization, and that doesn’t need to save all of the functions on the stack. But that’s a topic for another day. Looking into recursive vs. iterative ways of programing will explain the pros and cons of both.

Hopefully, now you won’t feel intimidated if you ever encounter a problem that needs a recursive solution. Just take it step-by-step and break down the problem into smaller self-similar problems. Then ask yourself The Three Questions.

Better Programming

Advice for programmers.

Adam Snyder

Written by

Student programmer with big dreams. Hoping to build up the people around me.

Better Programming

Advice for programmers.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade