What Is Recursion in Programming? 

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.

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 ​an​other 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. ​H​ere’s how it could be written in Python:

def count_line(count):​ 
  ​if (no_one_behind(count)):​ 
    ​return count​ 
  ​elseif (no_one_in_front(count)):​ 
    ​return count_line(0)​ 
  ​else: ​ 
    ​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:

​def indirect_function1():​ 
  ​# Execute code... ​ 
  ​indirect_function2()​ 
 
​def indirect_function2():​ 
  ​# Execute code...​ 
  ​indirect_function1()​ 

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):​ 
    ​return x​ 
  ​if (y > 0):​ 
    ​return 1 + sum(x, y​ ​-​ ​1)​

Instead of just summing ​​x​ and ​​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​ example​s​ 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: 

def recursive_factorial(n):​ 
  ​if n == 1:​ 
    ​return n​ 
  ​else:​ 
    ​return n​ ​*​ ​recursive_factorial(n​ ​-​ ​1)​ 

Here is the same function written iterative​ly​: 

​def factorial(n): ​ 
  ​fact = 1​ 
  ​for num in range(2, n + 1):​ 
    ​fact *= num​ 
  ​return fact​ 

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: 

​def fibonacci(n):​ 
  # Base case 
  ​if n <= 1:​ 
    ​return n​ 
  ​else:​ 
    # Recursive call 
    ​return(fibo​nacci​(n​ ​-​ ​1) + fibo​nacci​(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.​ ​A​ll 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 

​​W​hile ​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. 

​​I​f you want to try your hand at recursive programming, you can check out our Python, Java, JavaScript, and other programming language courses to get started. We even have Learn Recursion with Python for an in-depth introduction to recursion. There’s also our Java: Algorithms course that will teach you recursion and other important algorithms in the Java programming language.