If you’re getting into the concepts of computer science, or you’ve started taking a computer science class, you may have heard the topic recursion come up in discussion a few times. In this article, I’ll remove all confusion and misunderstandings shrouding the topic of recursion, and make it easier for you to know when and how to use recursive algorithms.

Have you ever seen a set of Russian dolls? They start out with one big object at the start, but as you start to open them up, the inner dolls become smaller and smaller until you are left with one very small doll.

Russian dolls

Often times in computer programming, you are faced with a large problem to solve. Sometimes, the easiest way to solve such problems is to subdivide the large problem into many smaller problems, until the resulting problem is so small that we can just solve it directly. This technique of dividing a large problem into many smaller ones is the concept behind recursion.

What is a Function?

Yes, I know that you probably already know what a function is, but it is good to review the purpose of functions before understanding why we even bother using recursion.

A function is a block of organized, reusable code used to perform a single, related action. Programmers create functions to reuse code instead of writing the same code over and over again, . Doing so provides a program with better modularity and an overall clean code layout.

When a function is solving a problem, it can call many other functions to assist it. Recursion is the process where a function calls itself either directly or indirectly. Such functions are named recursive functions. This process is useful in situations where a problem can naturally be split into several tasks that are simpler.

Recursive Functions

Here is an example of a simple recursive function:

def factorial(num):
  if num == 1:
    return num
  else:
    return num * factorial(num - 1)
print(factorial(0))

This function calculates the factorial value of a number. The factorial of a number is the product of all integers from 1 to that number. For example, 4 factorial (4!) is 1.

The function above has one part that is critical to all-recursive functions: the base case. The base case is what tells the program to terminate after a specified value has been met. The base case for the factorial function is written to stop the recursion once a certain condition is met. Without the base case, the function would keep recursing until the program causes a stack overflow error. In the above function, if the number that is passed into the function is 1, we return the num and do nothing else. This causes execution to break out of the function without any further recursion taking place. We use this base case because the factorial of 1 is just 1.

return num * factorial(num - 1)

If the base case is not met, the function returns the num variable multiplied by the factorial of one less than num.

How Does The Recursion Work?

Let’s explore step by step what would happen if we were to execute the factorial function with parameter 2 (factorial(2)).

First, our function would realize that 2 is not 1 and skip that part of the if statement.

Then, it would return 2 multiplied by factorial(1), and at this point, the factorial function would run again, except for the value of 1. But since 1 is equal to 1, the function we executed in the return statement would return 1. Therefore, the return statement (the one that returns 2 * factorial(1)) would return 2 * 1. And 2 factorial is indeed 2.

The same thing happens when we pass in 4 as the factorial parameter. This returns 4 * the factorial of 3, which is 3 * the factorial of 2, which is 2 * the factorial of 1, which is 1.

Image result for recursion factorial python
The above diagram explains how this recursive algorithm works visually.

The Difference Between Recursion and Iteration

There is another alternative way to solve the problem of calculating factorials, and that is by an iterative loop. A program written to calculate the factorial of a number using iteration would look something like this:

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

This code iterates through every number from 1 to the number provided, and multiplies the num variable by that number every time. This method of calculating the factorial of a number is completely fine and will work without any problems. The only difference is that in the recursive function, the function calls itself to loop through the numbers, while here an actual loop does that for us.

Why Use Recursion?

If the same factorial problem can be solved using iteration, then why bother using recursion? While in the factorial problem’s case using a recursive or iterative method made little difference, some problems can be solved quickly and cleanly with recursion.

Recursion is especially useful when solving problems that can be broken down into smaller, repetitive problems. It’s good for problems that have many possible branches, and are too complicated for an iterative approach.

For example, searching through a file system is easy with recursion. The program could start at the root folder, and then search through all the folders and files in that one. After that, the program would enter each folder and search through each folder inside of that one.

Recursion works well for this type of structure because you can search multiple branching paths without having to include many different checks and conditions for every possibility.

When Not to Use Recursion

Recursion seems like a simple solution to all of your algorithmic needs. So why not use recursion all the time when necessary?

There are two main factors that signify the efficiency of an algorithm: it’s time complexity, and space complexity. Time complexity represents the computational complexity of an algorithm, or in other words how many operations it needs to perform in a scenario. The space complexity of an algorithm is how much space it takes in memory with respect to the input size. When solving problems, programmers want these values to be as low as possible.

Recursive algorithms usually have higher space complexity. A new function call is added to the stack every time we call the function. While for small programs this may be a negligible amount of memory, as your program and input data gets bigger, the large call stack can have a potentially large impact.

Another reason to reconsider using recursion is if understanding and modifying your code would be easier to do if an iterative solution was implemented. Using recursion is great because it takes the sub-problems out of your hands, but when you need to fully understand the sub-problems and how they are to be solved, you should implement an iterative solution. You should at least try to understand how the recursion is working if you are going to use recursive algorithms in your code. Besides, using recursion yields the same time complexity as an iterative solution

Examples of Recursion

There are many applications in computer programming where you can use recursion. These problems include:

Recursion can make your projects cleaner and more efficient when used in the correct context. Remember that recursion is the word to describe a part in a program when a function calls itself. Finally, don’t forget to include a base case in your recursive functions so that you don’t cause a stack overflow!