Recursion is a very important and powerful idea in computer science and algorithms. A problem can be solved recursively if it can be reduced into smaller similar problems. Recursion is usually implemented by creating a function which calls itself from within its own code.

Let us understand this by a simple example of calculating $n!$ (read as ’n factorial’).

Factorial of a positive integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$. For example, the value of $4!$ is $4\times3\times2\times1 = 24$ . Note that the value of 0! is 1, according to the convention for an empty product.

We can write $n!$ as :

This can be written as the following (for $n > 0$):

For $n=0$, we define $n! = 1$.

Let’s see how we can implement a function factorial(n) which calculates $n!$

int factorial(int n) {
    if (n == 0) return 1; 
    return n * factorial(n-1);      // <== recursion
}
int main() {
    cout << "Factorial of 3 is " << factorial(3) << endl;
    cout << "Factorial of 1 is " << factorial(1) << endl;
    return 0;
}

Output:

Factorial of 3 is 6
Factorial of 1 is 1

The factorial() function above implements the equations we saw earlier quite directly. We’ll take a detailed look at what happens when factorial(3) is called in a bit. First, we want to draw your attention to the following points:

• In the code above, the function factorial() calls itself in its definition (line 6). This process is called recursion and the function factorial() is a recursive function.
• The case for $n=0$ is called a base case. Base case is the condition for which we already know the solution (usually a small / trivial case) so as to terminate the recursive calls. Every recursive function must have a base case, otherwise the recursive function will keep calling itself indefinitely forever.

Note: If you are thinking that the above factorial() function can also be implemented iteratively using a single for-loop, then what’s the need of recursion. The main advantage of recursion is that it often simplifies the code, and we will see an example at the end of this tutorial.

Execution flow of a recursive function

Let us understand the execution flow of the factorial() function you saw earlier.

int factorial(int n) {
    if (n == 0) return 1; 
    return n * factorial(n-1);  
}
int main() {
    cout << "Factorial of 3 is:\n" << factorial(3) << endl;
    return 0;
}

• The execution begins in the main() function. This calls factorial(3).
• The execution switches to the factorial() function, with n = 3.
• Since n == 0 is not satisfied, we move to return n * factorial(n-1);. This calls the factorial() function again with argument 2. (At this point, the execution of factorial(3) function pauses, since it’s waiting for factorial(2) to execute and return.)
• The execution switches to the factorial() function, with n = 2.
• Since n == 0 is not satisfied, we move to return n * factorial(n-1);. This calls the factorial() function again with argument 1. Again, the execution of factorial(2) function pauses.
• The execution switches to the factorial() function, with n = 1.
• Again, n == 0 is not satisfied. This calls the factorial(0).
• The execution switches to the factorial() function, with n = 0.
• Now (finally!), n == 0 is satisfied, and the function simply returns 1.
• Once factorial(0) returns, factorial(1) can then continue executing from where it had paused.
• It performs return 1 * factorial(0), and hence returns 1. (since factorial(0) had returned 1).
• Once factorial(1) has returned, factorial(2) can now continue executing from where it had paused.
• It performs return 2 * factorial(1), and hence returns 2. (since factorial(1) had returned 1).
• Finally, factorial(3) can now continue executing. It performs return 3 * factorial(2), and hence returns 6. (since factorial(2) had returned 2).
• Now, the main function can continue executing.

Take a moment and go over the above a couple of times to make sure you understand the code execution flow.

To recap, factorial(3) called factorial(2), which called factorial(1), and which further called factorial(0). Because of the (n == 0) check, factorial(0) simply returned 1 instead of making another call to factorial(). Then, factorial(1) could resume execution and return a value, which allowed factorial(2) to resume execution and return, which finally allowed factorial(3) to resume execution and return.

To verify the code execution we just discussed, let’s rearrange our factorial() function a bit and add a cout statement at the beginning and end.

int factorial(int n) {
    cout << "Starting to calculate " << n << " factorial." << endl;   // Statement 1
    int result;
    if (n == 0)
        result = 1;
    else
        result = n * factorial(n-1);
    cout << "Finished calculating " << n << " factorial." << endl;    // Statement 2
    return result;
}
int main() {
    cout << "Factorial of 3 is:\n" << factorial(3) << endl;
    return 0;
}

This code produces the following output:

Factorial of 3 is:
Starting to calculate 3 factorial.
Starting to calculate 2 factorial.
Starting to calculate 1 factorial.
Starting to calculate 0 factorial.
Finished calculating 0 factorial.
Finished calculating 1 factorial.
Finished calculating 2 factorial.
Finished calculating 3 factorial.
6

Notice that there is an equal number of steps going down in recursion as coming up. Depending on where the statement is written, it will be executed either before or after the recursive call.

The important fact to notice here is that when we make the recursive call, the execution in that function instance pauses and only resumes once the recursive call is executed completely.

Importance of base case

You must be careful when writing recursive functions so that we always reach the base case. If the code does not encounter the base case, it will go into an infinite recursion.

In particular, apart from defining the base case, we also need to ensure that:

1. The recursive call should not skip the base case
2. The base case must be checked before the recursive call

Let’s do an exercise to make sure we understood this well.

Fibonacci sequence

The Fibonacci sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

The next number in the sequence is the sum of the two numbers before it.

The sequence follows the following recurrence:

with the base case as $F(0)=0$ and $F(1) = 1$ .

As we know the base case and the recurrence relation, we can write the recursive function for fibonacci as:

int fib(int n) {
    if (n == 0 || n == 1) 
        return n;
    else 
        return ( fib(n-1) + fib(n-2) );    
}
int main() {
    cout << fib(5) << endl; 
    return 0; 
}

Let’s see what happens when we call fib(n).

When we call fib(n), it calls fib(n-1) and fib(n-2). fib(n-1) calls fib(n-2) and fib(n-3). fib(n-2) calls fib(n-3) and fib(n-4).

The following diagram shows the function calls when fib(5) is called.

The diagram above is called a recursion tree. For each function call, you can see the recursive calls it makes right below it, and the recursive calls those functions make right below them, and so on till the base cases are reached.

Note: The diagram above does not directly show the order in which the recursive calls are made.

Based on the recursion tree, we can observe that the run-time complexity of finding the above code is exponential. To see this, notice that the height of the recursion tree is $O(n)$ and we can see from the left branches that each node calls 2 nodes. Therefore, the complexity is $O(2^n)$.

Advantages of recursion

In many situations, a recursive implementation is the simplest way to solve a problem.

For example, suppose you have to explore the file system on your computer. The recursive approach to explore your entire file system would be (pseudo-code):

define explore(current_folder) {
   for each sub_folder in current_folder:
       explore(sub_folder)
}

Summary

In this tutorial you learned about:

• Recursion - a function calling itself
• Base case - the condition at which recursion terminates
• base cases must never be skipped
• base case must be checked before the recursive call
• If a recursive function calls itself multiple times, the run-time may become exponential
• In many situation, using recursion greatly simplifies the implementation

Further reading

1. Recursion | Utah
2. Merge Sort | CommonLounge: Application of Recursion