0

I am doing some recursive exercises. The previous one was to make a reverse() function for a string which basically removes the first character and then combines the solution. I managed to do that, here is the source code (the entire source) The current task is to modify this function (the following exercise in the book) by adding a helper function which reverses a substring of the string. At this moment I am stuck at this. It is my understanding that you use helper functions when you need to pass additional arguments or something and this function takes none so I really have no idea how to approach this problem. Help appreciated.

    #include <iostream>
    #include <string>
    using namespace std;

    void reverse(string& text)
    {
        if (text.length() == 0)
        {
            return;
        }
        if (text.length() == 1)
        {
            return;
        }
        else
        {
            string firstLetter = text.substr(0,1);
            text = text.substr(1, text.length()-1);
            reverse(text);
            text += firstLetter;
            }
    }
    int main()
    {
        string a = "tyu";
        reverse(a);
        cout << a << endl;
        return 0;
    }

A guy suggested to use parameters, ect, this is my try with it:

#include <iostream>
#include <string>
using namespace std;
//is actually doing the hard work
void reverse1(string& input, int a, int b)
{
        // base case
        if( a >= b)
        {
             return;
        }
        //swap the characters
        char tmp;
        tmp = input[a];
        input[a] = input[b];
        input[b] = tmp;
        //create the boundries for the new substring
        a++;
        b--;
        //call the function again
        reverse1(input, a, b);
}

// sets the parameters and calls the helper function
void strreverse(string& input)
{

    reverse1(input, 0, input.length()-1);
}

int main()
{
    cout << "Please enter the string which you want to be reversed:";
    string a;
    cin >> a;
    strreverse(a);
    cout << a << endl;
    return 0;
}
4
  • 1
    What about the case where text.length() == 0? You have to cover all bases... Of course, you can change the == to <=, but the other part of the function is not going to work well if the length is zero (subtracting 1 from 0 leaves a large number if the string size is unsigned). Commented May 16, 2013 at 15:28
  • Since I am decrementing one character at a time, this bug shouldn't appear, though I will add this as a base case as well. Commented May 16, 2013 at 15:29
  • Always make sure you cover your Base Case when using recursion... or prepare yourself for lots of waiting Commented May 16, 2013 at 15:30
  • The base case is added. Commented May 16, 2013 at 15:31

3 Answers 3

2

The goal is probably to avoid creating all of the intermediate substrings. The helper function will take iterators, or a start and end index in addition to the string begin reversed.

Sign up to request clarification or add additional context in comments.

3 Comments

... or only a start index, from which the end index can be derived.
I have added my take on it as a second source. Is that what you mean?
@Bloodcount It looks OK to me. I'd use a half open interval, but in this case mainly because that's the C++ tradition. And I'd inverse the if and put the logic inside the conditional, to avoid the premature return, which is confusing and makes reasoning about correction more difficult (in general---in this case, it may even make is simpler).
1

Try to implement reversing so that there is only one instance of std::string (i.e. work with it as with an array). Then you will need a helper function with additional parameters (at least one parameter - which index to reverse now).

I would implement reverse here as series of exchanges: a[0] <-> a[n-1], a[1] <-> a[n-2] etc. where n is length of the string.

Comments

0

You can define a helper function that takes a start and an end index of the substring which it will reverse. The function should exchange the element at the start index with that at the end index IFF the difference between the start and the end indices is 1. Otherwise, it places a recursive call to itself by decrementing the end index and incrementing the start index. You will need to keep check on the condition if the start and end index become same though.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.