CODEWITHSUNDEEP
c++algorithmsortingreverse
joasdf
joasdf

Reputation: 87

Trying to reverse a string in C++ but getting the same string back

I get the same string back when I try to reverse it in C++.

I read that recursion is a good way to reverse things. I tried to implement a recursive algorithm by returning the first character of the string and calling the same function with the first character removed until the string has a size of 1. My first function removes the first character of the string and the second function reverses it:

string deleteFirstElement(string input) {

    if (input.size() == 1) {
        return input;
    }

    // This loop brings the first element to the last position
    for (int i = 0; i < input.size()-1; i++) { 
        char temp;
        temp = input.at(i);
        input.at(i) = input.at(i+1);
        input.at(i + 1) = temp;
    }

    input.pop_back();   // Delete last element of the string
    return input;
}

string reverseit(string input) {
    if (input.size() == 1) {
        return input;
    }
    else {
        return input.at(0) + reverseit(deleteFirstElement(input));
    }
}

But why do I get the same string back and no reverse?

Upvotes: 3

Views: 427

Answers (4)

Michael Surette
Michael Surette

Reputation: 711

Recursion is not the easy way to reverse things.

Here is the easy way:

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

int main()
{
    string s { "hello" };

    reverse(s.begin(), s.end());

    cout << s << endl;
}

Here is a recusive solution. It works but is much less reasonable and efficient.

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

string recursiveReverse(string value, string accum = "")
{
    if(value.size() == 0)
    {
        return accum;
    }
    else
    {
        accum += value.back();
        value.pop_back();
        return recursiveReverse(value, accum);
    }
}

int main()
{
    string s { "hello" };

    s = recursiveReverse(s);

    cout << s << endl;
}

Upvotes: 2

darune
darune

Reputation: 10982

If you have , this problem basicly boils down:

string reverseit(string input) {
  string result(input);
  boost::range::reverse(result);
  return result;
}

Without , you may instead use:

std::reverse(result.begin(), result.end());

As noted, recursion reduced readability of your program and should be reserved for rare cases (usually where another solution is just more complicated).

Upvotes: 1

FalcoGer
FalcoGer

Reputation: 2457

You get the same string back because you build the same string again. Using the example of "ABC" you'll see what the function does:

reverseit("ABC") returns 'A' + reverseit("BC")
reverseit("BC") returns 'B' + reverseit("C")
reverseit("C") returns 'C'

You'd want

char firstChar = input.at(0);
return  reverseit(deleteFirstElement(input)) + firstChar;

But really you should be looking into another solution. Recursion

  • reduces readability
  • is slow
  • uses lots of stack memory
  • easily creates hard to debug endless loops

in general it should be avoided if possible. Some solutions are really elegant with it, to be sure, but loops are almost always faster.

Upvotes: 9

Akash Jain
Akash Jain

Reputation: 730

change the else part from this

  string reverseit(string input) {
        if (input.size() == 1) {
            return input;
        }
        else {
            return input.at(0) + reverseit(deleteFirstElement(input));
        }
    }

to this

string reverseit(string input) {
    if (input.size() == 1) {
        return input;
    }
    else {
        return reverseit(deleteFirstElement(input))+ input.at(0);
    }
}

Upvotes: 3

Related Questions