Recursion in C++ is a function with a set of rules designed to reduce a problem into a smaller one called a base case. This may be referred to as the divide and conquer method since the idea is to solve a complex problem by solving the smaller instances of it. A classic example is the factorial function, which we’ll discuss later.

Recursive function that displays numbers

For our first example, let’s create a recursive function that displays a number. In order to do this, we create a function that prints a number to output, then we call itself.

1
2
3
4
5
6

void printnum(int n)
{
     cout << n << " ";
     printnum(n); // Recursive call
     return;
}

Unfortunately, the previous example displays behavior known as infinite recursion on any call. Depending on the environment you are programming in, you might receive a segmentation fault. This happens because each activation record of a function is pushed onto the run-time stack. When you have a function that runs indefinitely, you are bound to run out of space.

Example of Infinite Recursion

Base Cases in Recursion

In order to eliminate infinite recursion we introduce a base case. A base case is a condition that determines when to terminate a recursive function. For our previous example, we’ll introduce the following base case and also make sure we are reducing our input into a smaller case each call (otherwise, we’d never reach our base case).

1
2
3
4
5
6
7
8
9
10
11

void printnum(int n)
{
     // Base case
     if ( n == 0 ) 
          return;
     cout << n << " ";
 
     // Recursive call that reduces input into a smaller case
     printnum(n-1); 
     return;
}

Below is an example of the output of executing such a function.

1

printnum(5);

5 4 3 2 1

Example of printnum(3) and output to the console

Now, what happens if we execute printnum(-2)? We will never reach our base case and thus receive infinite recursion. In order to avoid this behavior, its essential that we create robust base cases that allow our recursive functions to terminate.

The following is the modified version of our recursive function.

1
2
3
4
5
6
7
8
9
10
11

void printnum(int n)
{
     // Improved base case 
     if ( n <= 0 ) 
          return;
     cout << n << " ";
 
     // Recursive call that reduces input into a smaller case
     printnum(n-1);
     return; 
}

Things to remember about C++ Recursion

Below are some things that you should take into consideration when solving recursive problems in C++.

• Recursion in C++ is a very difficult subject. It takes dedication in order to understand and master the subject.
• The best way to solve recursive functions is to write down the problem on a piece of paper and identify how you are going to break down the problem into a smaller instance and when to terminate (base cases).
• A good way to visualize recursion is to draw the activation records by drawing the run time stack of a simple recursive call

Going further with C++ Recursion

Now that you know the basic concept, the best way to learn recursion is by solving problems.

Next: C++ Recursion Examples