Knowing how to use recursion to solve a problem can be very useful when you’re writing code. Questions or coding challenges that involve recursive thinking can come up in technical interviews, because hiring managers want to see that you understand how to break down a problem into smaller sub-problems. And if you’re into competitive programming, recursion can come up pretty often as a problem-solving tool.
Ahead, we’ll go over recursion and how it’s used, its advantages and disadvantages, and how to know when using recursion is a good way to solve a problem.
Learn something new for free
What is recursion used for?
Recursion is breaking a component down into smaller components using the same function. This function calls itself either directly or indirectly over and over until the base problem is identified and solved. For some programming problems, using recursion makes for a concise and simple solution that would be more complex using another algorithm.
For a real-life example of recursion, imagine you’re at the front of a line of people at a crowded supermarket and the cashier wants to know how many people are in the line total. Each person can only interact with the person directly in front of or behind them. How would you be able to count them all?
You could have the first person in line ask the second person in line how many people are behind them. This continues all the way until the nth person in line (in a recursive function, this would be when the base case is hit). Then, the information is passed back from the nth person to the first person. Now, the first person in line knows how many people there are and can provide that info to the cashier helping the line of people.
This is recursion. The same function is used by each person to count, and the answer is passed on to the next person so they can use it in their calculation. Here’s how it could be written in Python:
return count_line(count + 1)
The function returns itself after adding 1 to the
count until there is no one behind the current person, then it just returns the
count. We can use it to illustrate some of the concepts in recursion.
What is a base case in recursion?
A function has to call itself at least once to be recursive, but eventually, it has to return the value you are looking for — otherwise it’s useless and will probably also result in the program crashing. In the function above, the function calls itself in two places, but it also returns the count if there is no one behind the person.
This is the base case of this recursive function. The base case is also called the halting case, or base condition, because it’s like a stopping point or safety net that keeps the function from endlessly calling itself. It’s met when a recursive function finally returns a value, and the problem is solved. Ours is solved when there is no one left in line to count.
Direct vs. indirect recursion
The recursive function above is an example of direct recursion because the function calls itself. Indirect recursion is when a function calls another function. Here is an example of indirect recursion:
# Execute code...
# Execute code...
Examples of recursion
The examples of recursion above display the concept simply, but it‘s not a real-world problem and our “code” is only pseudocode. Here are some examples of problems that can be solved using recursion:
Calculate the sum of two numbers
This is a simple example that demonstrates recursion. FYI: This probably wouldn’t be used in production because it‘s a contrived way of adding two numbers:
def sum(x, y):
if (y == 0):
if (y > 0):
return 1 + sum(x, y - 1)
Instead of just summing
y, we subtract 1 from y and return the function again added to 1. Once
y is 0, the value of
x is returned. This function will only work with positive numbers. Here‘s how all these returns will stack up if
x is 1 and
y is 2. Consider each set of parentheses as one function call.
(1 + (1 + (1)))
Calculating a factorial of a number
Now that we’ve seen two examples of recursion, let’s look at a place where recursion is really useful: calculating a factorial.
In math, a factorial of a number
n is represented by
n! and is the product of all positive integers that are less than or equal to
n. The calculation for 5 factorial is:
5 * 4 * 3 * 2 * 1 = 120
Writing a recursive function for this is one of the easiest ways to calculate this value. Here is a Python function that will calculate a factorial:
if n == 1:
return n * recursive_factorial(n - 1)
Here is the same function written iteratively:
fact = 1
for num in range(2, n + 1):
fact *= num
The recursive function doesn’t save many lines of code in this example, but it represents the actual problem clearly. We are multiplying the current number by one less than the current number until we reach 1. Here’s how the returns would stack up for calculating the factorial of 5:
(5 * (4 * (3 * (2 * (1)))))
Calculating a Fibonacci sequence
A Fibonacci sequence is another type of calculation where recursion works well. A Fibonacci sequence is a series of numbers where each number is a sum of the two numbers before it. Here is an example:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
And here is a recursive function in Python to find a number in this sequence based on its location:
# Base case
if n <= 1:
# Recursive call
return(fibonacci(n - 1) + fibonacci(n - 2))
The function calls itself twice at the end — once for the number right before the number passed in and one for two numbers before. These numbers continue to get smaller until they reach 1 and the function returns the value. Here’s how all the returns will stack up to find the number in the 2nd position.
((1 + 0) + (0))
Advantages of recursion
Recursion can’t be used for everything, but it does have some advantages for specific types of problems. Here are some of its advantages:
- It can make your code easier to write, replacing complex logic with one function.
- It can make your code more concise and efficient.
- It can reduce the amount of time it takes your solution to run. (Though it also can make it slower, as we will see in the disadvantages section.) Often, making a recursive function fast requires using memoization, which involves storing the result of each calculation so that it can be used in each recursive call instead of combining the result and the function.
- Recursion is efficient at traversing tree data structures. A tree is a collection of objects that are linked to one another. This type of data structure is well-suited for recursion, because the same function or operation can be applied over and over.
Disadvantages of recursion
Recursion also has some disadvantages. Here are a few of the most significant:
- Recursion uses more memory. In a computer, a function call is added to the “call stack” and stays there until it returns a value. A recursive function will call itself until the point when a value is finally returned when a base case is hit. All of those function calls go on the stack and remain on the stack until that point. This eats up memory.
- Recursion can cause stack overflows. This happens when the call stack has no more room to hold another function call and the recursive function has not returned any value yet.
- Recursion can be slow if you don’t use it correctly with memoization.
- Recursion can be confusing. It can make your code simpler but also give you more mixed signals. Unless you understand recursion, it can be hard to grasp what a recursive function is doing. But once you know how recursion works, it can make coding simpler.
Learn more about recursion
While recursion might take a little practice before it sinks in, there are many problems in code that you can solve by using it. When you use it successfully, it seems like magic. Many modern programming languages support recursion. Some, like Haskell and Scheme, require coders to strictly use recursion instead of loops.