6.1.3 Recursion Example: Reverse String

Take a look at another example, this time with a string. The problem you are trying to solve is to print a string in reverse order.

From your knowledge of loops, you should know that you can print a string in reverse order using a loop, for example:

string str = "hello";

for (int i = str.size() - 1; i >= 0; i--) {
    cout << str[i];   
}

Output:

olleh

This problem can also be solved recursively. Recursion is another form of an iterative statement and you will find that many recursive problems can be rewritten with a for or while loop.

Reverse a String Recursively

In the problem below, notice that the base case when the string length is less than or equal to 1. When the string only has a length of 1, it is the same backward and forwards. The same could be said for a length of 0. Either scenario works for a base case, however, if you do want to consider the case of an empty string, you must cover zero in your base case.

When you are in your base case, you can simply print the string since it is the same backward and forwards.

When you are not in the base case, your recursive call should be to a string one smaller than the current string and then print the first letter.

Tracing Example

Take a look at how this would work if the user entered hello.

The first call from main would be:

• reverse("hello") - Not the base case, so the return will call reverse("ello"). Notice that the return statement will add the letter h after the recursive call returns.

• reverse("ello") - Not the base case. Calls reverse("llo").

• reverse("llo") - Not the base case. Calls reverse("lo").

• reverse("lo") - Not the base case. Calls reverse("o").

• reverse("o") - Base case. Returns o to reverse("lo"). Remember this will be the first letter in the return string since all others are waiting on the recursive call to finish.

• reverse("lo") returns the o + the l to reverse("llo").

• reverse("llo") returns the ol + the other l to reverse("ello")

• reverse("ello") returns oll + the e to reverse("hello")

• reverse("hello") returns olle + the h to the main function, which then prints the string reversed.

Switching the order

One of the things that is really nice about recursion is that a small change can be made to the program to get very different results. In this example, try switching the order of the recursive call and the substring from:

return reverse(s.substr(1)) + s.substr(0,1);

to

return s.substr(0,1) + reverse(s.substr(1));

This small change will have a noticeable impact on the code. How could a small change like this impact some of the data structures you have seen?

Try This Example