Introduction to Recursion in C++

RSS

Introduction to Recursion in C++

26 Nov

Recursion in C++ is simply a function that calls itself that terminates when a base case is met. It’s very useful to learn how recursion for a couple of reasons.

It’s easier to solve certain problems with recursion as the resulting code is usually shorter
Sometimes its the only way

Displaying Numbers Recursively

So what’s an example of a recursive function? Let’s make one. Let’s start by creating a function that displays a number (it isn’t the best example, but it’s good enough to introduce you to recursion).

void display(int n)
{
     cout << n << " ";
     return;
}

All this function does is simply print the number passed in.

Recursive Display Function

Now let’s have this function call itself but lets decrement the value being displayed each time.

void display(int n)
{
     cout << n << " ";
     display(n-1); //Will call display but with (n-1)
     return;
}

So let’s say we executed display(10)

What would this display? It would display 10 9 8 7 6 5 4…and would never stop. Why? We never told the function when to terminate. This will either cause your program to run until you kill it, or may cause it to segmentation fault. In order to fix this, this calls for the addition ofbase case.

Base Cases in recursion : In order for your recursive function to terminate you always need a base case. You may have multiple base cases.

Recursive Display Function With a Base Case

Let’s make the function terminate when n is 0. Or better yet, let’s make it terminate when n is less than or equal to 0. (Why do you think this is better?)

void display(int n)
{
     if ( n <= 0 ) return;
     cout << n << " ";
     display(n-1); //Will call display but with (n-1)
     return;
}

So now, if we execute display(10), what would it display?

10 9 8 7 6 5 4 3 2 1

How Recursion Works in C++

So how does recursion work in C++? Each function creates an activation record on thestack. As a function gets called, it gets added to the top of the stack. Until the function is terminated, is then taken off the stack. A visual example for our display function is below.

The first function called was display(10) which is the activation record seen at the bottom of our stack. If you notice, the following function keep getting called as long as the base case isn’t met. Up until n = -1, then the activation record of the functions are popped off.

What is shown previously is a very basic recursive algorithm. More recursion techniques will be discussed later. So even if you don’t understand the purpose of recursion just yet, don’t hesitate. You’ll understand why it’s important when you understand recursion is the only way to do certain problems.

Prasanth's Blog