Reverse a string without using standard functions

Question

I recently got asked this during an interview. As a recent graduate, and only been programming about 2 years (all school work), I was at a loss. I had a vague idea, but I'm sure I failed it. This is what I'd written:

string Reverse(string word, string reversed)
{
    if(word.length() == 0)
    {
        return reversed;
    }
    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        Reverse(temp, reversed);
    }

    return reversed;
}

Now that I'm home, I'm testing it, and the return is only the first letter in the input. I'm vaguely familiar with the concept of recursion, but I'm obviously failing at this. Any help/pointers/suggestions are very much appreciated. Thank you.

EDIT: Following Dennis Meng's post, I've made the following change:

string Reverse(string word, string reversed)
{
    if(word.length() == 0)
    {
        return reversed;
    }
    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        return Reverse(temp, reversed);
    }
}

Now, I get the proper return value. Thank you so very much.

What's the question? Did they ask you to solve it w/ recursion? — Luchian Grigore
– Luchian Grigore, Commented Aug 9, 2012 at 16:45
The answer I'd have been looking if I asked this question in an interview would be one which involved constructing a new string using a reverse iterator pair. I'm not going to give you a full answer - you can look that up yourself. — marko
– marko, Commented Aug 9, 2012 at 16:51
@Marko: Interview questions don't have to be "hard to answer". Interview is not supposed to be a competition because usually you need a good candidate for a job, not a champion. — SChepurin
– SChepurin, Commented Aug 9, 2012 at 18:21
@SChepurin very much so - there is often the case for having the diligent, and more junior completer-finisher rather than another star-developer with a huge ego in your team, and sometimes budget constrains what you hire. There's nothing wrong with expecting to mentor new team members either - but it depends very much on the project environment and having somebody to do it. What you never want is a liability that you then later have difficult firing for not being terribly good. — marko
– marko, Commented Aug 9, 2012 at 18:36

Dennis Meng · Accepted Answer · 2012-08-09 16:56:34Z

2

What's going wrong is in here:

    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        Reverse(temp, reversed); // <-- Here's your problem
    }

    return reversed;
}

You know that the call should return the correct answer, so why not just return that? In other words, what if you did

    else
    {
        string temp;
        reversed = word.substr(0,1) + reversed;
        temp = word.substr(1);
        return Reverse(temp, reversed);
    }
}

instead? The specifics of why your code was only returning the first letter involves pass-by-reference/pass-by-value; because of the pass-by-value stuff, you never actually used what was done in the recursive calls. (You just made the call and threw away what it returned.)

answered Aug 9, 2012 at 16:56

Dennis Meng

5,18714 gold badges35 silver badges37 bronze badges

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

12 Comments

Renrael Over a year ago

Thank you very much! That little change did it. Is this type of question commonplace in interviews? In my classes, my instructors always emphasized "not reinventing the wheel". I'm wondering if I was given the wrong mindset. Thanks again!

Dennis Meng Over a year ago

It's a pretty common interview question to start things off, make sure you have the basics, etc. Your instructors are right in saying that you shouldn't reinvent the wheel, but it's good to know how the wheel was invented, and interviewers want to know your thought process more than the answer anyway.

Dennis Meng Over a year ago

(Also, the other guys are right in saying that there are much better ways to do this, but I'd say on the fly in an interview question this approach is perfectly fine.)

Renrael Over a year ago

Having seen my original response, even though it didn't get the proper return value, what would you think as an interviewer? Just trying to gauge a potential call back. I felt the rest of the interview and test went fine. Just got caught on this.

Dennis Meng Over a year ago

Well, I'm probably not the best person to ask for what an interviewer would say, but if I were interviewing you and saw this code, I'd see that you at least have a rough understanding of recursion, point out that there was a bug, and encourage you to fix it. Once it's fixed, then I'd see if you can do this recursively without the accumulator, and finally see if you can do the iterative solution.

|

Mooing Duck · Accepted Answer · 2012-08-09 16:51:31Z

string Reverse(string word, string reversed) 
{
    ...
    Reverse(temp, reversed);

First of all, you should be passing word by const reference, and reversed by reference. When you call the recursive function, you're making a copy of each of those strings, so the outermost function cannot see anything they do. Another option would have been to assign the result of the recursed function to reversed, but then you still have a silly number of string copies everywhere. So: pass the variables by reference.

Second: There's way easier ways to reverse a string:

 string Reverse(string word) //caller should _not_ see my changes, so I pass by value
 {
     for(int i=0; i<word.size()/2; ++i) { //for each letter in the first half
         int otherindex = word.size()-1-i; //find the letter on the other half
         char t = word[i];  //and swap them
         word[i] = word[otherindex];
         word[otherindex] = t;
     }
     return word; //return the result
 }

ewok · Accepted Answer · 2012-08-09 18:25:18Z

1

I'm not sure why you're using recursion here. it's really unnecessary:

string Reverse(string word)
{
    string reversed = "";

    if(word.length() == 0)
    {
        return reversed;
    } 

    for (int i = word.length()-1; i>=0; i--){
        reversed = reversed+word[i];
    }

    return reversed;
}

edited Aug 9, 2012 at 18:25

answered Aug 9, 2012 at 16:49

ewok

21.7k56 gold badges166 silver badges267 bronze badges

6 Comments

Xeo Over a year ago

"sizeof(word)" -- nonononononoNO!

Praetorian Over a year ago

@ewok sizeof(word) does not return the length of the string, but the size of the std::string class, which is not what you want. You need to use word.size()

Mooing Duck Over a year ago

why are you being passed in reversed?

Dennis Meng Over a year ago

OP was originally using it as an accumulator.

Dennis Meng Over a year ago

True, but at this point I'd just chalk it up to answerer doing copy/paste and not pruning everything out.

|

Senthil Babu · Accepted Answer · 2012-08-09 16:55:07Z

0

A string is nothing but an array of characters. Generally in this case, you should use an array of characters to explain the algorithm. Here is a better way to do it.

void reverse(char* str, int len)
{
    for (int i = 0, j = len -1 ; i < len / 2; ++i, --j) {
         // Swap the values as i and j.
         int temp = str[i];
         str[i] = str[j];
         str[j] = temp;
    }
}

If the same question is asked in Java, you have to make sure that you are converting the string to char[] array reverse it and then form a String. This helps in keeping the number of object that are getting created minimal. At least, you should use a StringBuilder.

answered Aug 9, 2012 at 16:55

Senthil Babu

1,2732 gold badges11 silver badges21 bronze badges

1 Comment

cHao Over a year ago

There's no need for a StringBuilder in C++; strings are mutable. And since they implement operator [], you could effectively use this very same algorithm with it, except that you no longer need to pass len cause the string already knows it. :P

Alexander Rios · Accepted Answer · 2012-08-09 19:27:50Z

0

Here is another solution (similar to one already posted). But now I see that this solution is not ok for you, since it uses std stuff.

std::string reverse(std::string const& character_queue_) {
    using namespace std;
    string result;
    if(!character_queue_.empty()) {
        vector<char> character_stack;
        std::copy(character_queue_.begin(),character_queue_.end(),std::back_inserter(character_stack));
        while(!character_stack.empty()) {
           result.push_back(character_stack.back());
           character_stack.pop_back();
        }
    }
    return result;
}

edited Aug 9, 2012 at 19:27

answered Aug 9, 2012 at 18:48

Alexander Rios

823 bronze badges

Comments

totjammykd · Accepted Answer · 2013-02-28 22:02:51Z

-2

Just to suggest a better way of handling recursion:

String reversal using recursion in C++:

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

string reverseStringRecursively(string str){
    if (str.length() == 1) {
        return str;
    }else{
        return reverseStringRecursively(str.substr(1,str.length())) + str.at(0);
    }
}

int main()
{
    string str;
    cout<<"Enter the string to reverse : ";
    cin>>str;

    cout<<"The reversed string is : "<<reverseStringRecursively(str);
    return 0;
}

answered Feb 28, 2013 at 22:02

totjammykd

3474 silver badges10 bronze badges

1 Comment

cHao Over a year ago

Google "Schlemiel the Painter's Algorithm". :P

Collectives™ on Stack Overflow

Reverse a string without using standard functions

6 Answers 6

12 Comments

Comments

6 Comments

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

12 Comments

Comments

6 Comments

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related