Need help with my recursive program that reverses the input

Question

Possible Duplicate:
Write a recursive function that reverses the input

Recently, I've been reading the book C++ For Everyone and I've been having trouble putting together a recursive function (Confusing to think about...)

The question was: Write a recursive function string reverse(string str) that returns the reverse of str

This is what I have so far:

string reverse(string str)
{
    string word = "";

    if (str.length() <= 1)
    {
        return str;
    }
    else
    {
        string str_copy = str;
        int n = str_copy.length() - 1;
        string last_letter = str_copy.substr(n, 1);

        str_copy = str_copy.substr(0, n);
        word += reverse(str_copy);
        return last_letter;
    }
    return word;
}

My problems now is:

If I enter wolf, it returns f

If I change return last_letter to return word, I get w

If I change to return str_copy, I get wol

Is this question different from http://stackoverflow.com/questions/5760774/write-a-recursive-function-that-reverses-the-input? It looks pretty similar. — Greg Hewgill, Apr 23 '11 at 00:25
That's a wrong perception. If you don't satisfy with the kind of answers given, wait at least for half a day. Then, you could start bounty for the same question instead of posting it again. — Mahesh, Apr 23 '11 at 00:36

ikegami · Answer 1 · 2011-04-23T03:02:21.640

3

You need to return the combination of the the last character (last_letter) and the reversal of the rest of the string, but you don't do that in any of your attempts. You only ever return one part or the other.

string reverse(string str)
{
    int len = str.length();
    if (len <= 1)
    {
        return str;
    }
    else
    {
        return str.substr(len-1, 1) + reverse( str.substr(0, len-1) );
    }
}

edited Apr 23 '11 at 03:02

answered Apr 23 '11 at 00:28

ikegami

367,544
15
269
518

Off by one error -- should be `reverse( str.substr(0, len-1) );` otherwise the inner `reverse` has the same `str` as the outer `reverse`. – user470379 Apr 23 '11 at 00:40

score 1 · Accepted Answer · answered Apr 23 '11 at 00:28

1

This would do the work:

Delete return last_letter;

Change `

word += reverse(str_copy);

to

word = last_letter+reverse(str_copy);

I'll leave the thinking to you!

Best.

answered Apr 23 '11 at 00:28

zw324

26,764
16
85
118

YES. IT WORKS!!!!!! Started this yesterday and can't figure it out. Thanks – Alex Apr 23 '11 at 00:41

Need help with my recursive program that reverses the input

2 Answers2