As soon as you start programming, you deal with some basic concepts, such as loops. When you need to print something 10 times, iterate through a name list, or calculate the sum of the numbers, you use a simple for or while loop. This is the easiest way.

However, as you dig deeper into programming, you get acquainted with a completely new logic – recursion. This is the concept that may seem magical and scary for a beginner programmer. Nevertheless, recursion appears in programming quite often. Recursion takes place when a function calls itself to solve the smaller problem of the same kind.

Although this looks weird, recursion is a vital part of programming. Using recursion, you can make an impossible task solvable with a few lines of code. Once you strip down all technical details, recursion becomes clear.

Russian Nesting Dolls: Practical Example of Recursion

In general, it is easier to explain recursion with a real-life example without the use of programming.

For example, let us assume that you have a painted wooden doll and the task is to find a tiny golden key inside the innermost doll. What should you do to accomplish your goal? Since you do not know the number of dolls, you cannot apply a loop. Instead, you should use a self-referential approach.

You open the current doll.

You inspect what you have discovered.

If it is the key, you find it and finish your mission.

Otherwise, you repeat the same steps for the next doll inside.

[Open Doll] —-> Is it the key?

                          ├── Yes: Stop! (Mission Accomplished)

                          └── No: Open the next doll —-> [Open Doll]

Each time when you open a doll and discover the next doll inside, you perform a recursive step. You call the same function, but now the problem is reduced and you move closer to the solution.

Two Laws of Recursive Function

If you try to implement a recursive function without defining its boundaries, you will make the computer crash due to Stack Overflow. To avoid this unpleasant situation, you should stick to two major rules of writing a recursive algorithm.

Rule 1: Base Case (Emergency Brake)

Base Case is the most important element of a recursive function. It is a special case that stops further iterations and gives the result. In our Russian nesting doll example, base case appears once you open the doll and discover the golden key inside. Once you have the key, you stop the process. Without a defined base case, your function will keep going on and on.

Rule 2: Recursive Case (Approaching the Base Case)

Here comes the magic! Your function calls itself again and again, moving closer to the base case with every step. At this point, you should remember one thing: with each recursive call of the function, you should change its input parameters. Otherwise, your function will never stop.

Call Stack: Behind the Scenes of Recursion

In order to fully understand how recursion works, you should dig deeper and take a look at the way functions operate in the computer’s memory. Here you should know the concept called Call Stack.

Imagine that the Call Stack is a stack of cafeteria trays. Each time when you invoke a function, the computer adds a new memory tray to the stack. Normally, after executing a function, the computer removes its corresponding tray.

With a recursive function, the computer continues adding memory trays because the function keeps calling itself.

Look at the classic example of calculating mathematical factorial. Factorial is the product of all integers lower or equal to the number you specified. Thus, 4! = 4 * 3 * 2 * 1 = 24.

Let us consider how the computer computes 4! using recursion:

Program invokes the factorial(4) function. Computer creates a new tray: “Calculate 4 * factorial(3)”. It pauses the factorial(4).

Computer invokes the factorial(3) function. A new tray is added: “Calculate 3 * factorial(2)”. It pauses.

Computer invokes the factorial(2) function. A new tray is created: “Calculate 2 * factorial(1)”. It pauses.

Now computer invokes the factorial(1) function. It is the base case. Computer returns the value: 1.

We have reached our base case, so it is time to unwind the recursion:

The factorial(1) tray is popped. The factorial(2) function resumes its operation. It calculates 2 * 1 and pops its tray.

The factorial(3) function resumes its operation. It calculates 3 * 2 and pops its tray.

Finally, the factorial(4) function resumes its operation. It calculates 4 * 6 and finishes the process.

When to Apply Recursion Instead of Loop?

Recursion is a great technique, but you cannot use it to replace loops. In most cases, the loop is a better option because it is more efficient. While standard loops take less memory and allocate memory resources predictably, recursion consumes extra memory space as each function call requires a new memory frame.

Under what circumstances would you prefer recursion over a loop?

Apply recursion if your problem can be reduced to the identical subproblem. Common situations include:

Traversal of file directories. Let us say you have a project where you have to scan the folder on your hard drive in order to find pdf files. This folder has numerous subfolders, and each of those subfolders can contain other folders in different combinations. It is not easy to do it with loops. Recursion works perfectly well. You only need to tell your function to scan the current folder and make a recursive call upon discovery of a subfolder.

Processing of tree and graph data. Nowadays, applications have complicated tree-like data structures in the form of organizational charts, family trees, HTML DOM on websites, or social media connections. Recursion is the most effective approach for dealing with such data.

Recursion vs. Loop Comparison Chart

In order to understand the paradigm shift, compare the features of iterative loops and recursive functions using this convenient chart.

Questions and Answers

What is “Stack Overflow” and how does it happen?

Stack Overflow occurs when a recursive function fails to reach its base case or simply lacks it. This results in an infinite loop that consumes extra memory space by adding memory frames to the stack. Eventually, the stack overflows, causing a program crash to prevent hardware damages.

Is recursion faster than a loop?

Generally speaking, recursion is slower. As recursion uses more memory space, it is typically slower than a standard loop. Nevertheless, we use recursion because it is much easier to implement and maintain than a nested loop.

What is Tail Recursion and why is it valuable?

Tail Recursion is a type of recursion when a recursive self-call is the last thing done by the function. There is nothing left to do. Some compilers can optimize tail-recursiveness and convert it to a loop.

Are all recursive problems solvable by a loop?

Yes, mathematically speaking. Although you can solve any recursive problem using an iterative loop and managing the stack manually, you will spend hundreds of lines of code implementing a nested loop for solving the tree-like problem.

How to write a recursive function?

If you want to create a recursive function from scratch, you should start with defining the Base Case. First, you have to find out what is the simplest form of the problem you need to solve. It should require no computations and have a clear solution.