recursive function void reverse()

[rowley4]

I need to write a program that implements the reverse function using a recursive solution by removing the first character, reversing a sentence consisting of the remaining text, and combining the two.

I have written this code below. I have two problems. 1, I am getting a fatal error on my Visual C++ program (I am uninstalling and reinstalling now) and it is not compiling anything. I can not check to see if I have errors in this program nor can I see if this correctly answers everything I need to do. 2. I am not really fully understanding what I am supposed to be doing with this program. Did I answer everything with this code? Thanks for your help!!

#include <iostream>
#include <string>

using namespace std;

class Sentence
{
public:
   
   Sentence(string aPhrase);
   
   string reverse();
     
private:
   string phrase;
};

Sentence::Sentence(string aPhrase)   
{
   phrase = aPhrase;
}

  
string Sentence::reverse()
{
   string r;
for (int i = 0; i < phrase.length(); i++)
r = phrase.substr(i, 1) + r;
phrase = r;
return phrase;}

int main()
{
   Sentence greeting("Hello!");
   cout << greeting.reverse() << "\n";
   return 0;
}

[dusktreader]

Your solution is not recursive. Recursive logic is very elegant and powerful, and for algorithm junkies like myself, completely awesome. The trick is understanding how recursion works. I'll use your reverse problem as an example.

Suppose we want to reverse the string "Hello". Well, the fundamental problem is switching the location of each letter. The first step would be putting "H" at the end of the string:

Hello
|____
     v
 elloH

Well, that's all fine and good, but if we continue to use that logic within the same fuction, we will just get the original string back:

elloH
|____
     v
 lloHe

lloH
|____
     v
 loHel

The key is to do this swap at different levels:

Hello
|____
     v
 elloH

ello   [H]
|___
    v
 lloe  [H]

llo   [eH]
|__
   v
 lol  [eH]

lo   [leH]
|__
   v
  ol  [leH]

o
|
v
o [lleH]

This can be done rather easily with recursion. The trick is to understand how to order your function so that the correct logic is used. Here's the pseudo code for the recursive reverse function:

string reverseR( string target ):
    if length( target ) == 1:          # if the target is only one character long
        return target                  #   there is no need to reverse it
    character first := target[0]       # remove first letter and save it for later
    string newTarget := target[1:end]  # now, reverse the rest of the letters
    newTarget := reverseR( newTarget ) # the remaining letters have been reversed
    string result = newTarget + first  # append the first letter to the back
    return result                      # now the string is reversed

This code can be further reduced to make it even more elegant, but I wanted each step to be clear. The beauty of a recursive algorithm is that each call to the function only needs to do a small piece of the work and trust that the remainder of the work will be done by the recursive call. The key is to correctly define your base case which tells the function where to stop recursing, and to place your recursive call in the correct place.

Recursion is a powerful tool. Mastery of this concept will separate true computer scientists from wannabes, so be sure you apply yourself to this concept. It really isn't hard, but it is a different way of solving problems than you are accustomed. Good luck!

[rowley4]

Thank you so much! This was a great explaination! Really appreciate the help with this!