My recursive function to reverse the chars of a string does not work

hafsa 0
Viewed 57

I was trying to make different recursive functions for the same problem i.e. to reverse the letters of a word. While all my solutions with a void return type (where i just printed letters in reverse) worked, I've been trying to make one using the string return type but am running into a problem. When entered hello, the following code gives me l. And I can't seem to figure out why...

string reverse(string s)
{
    int len = s.length();
    if (len <= 1)
    {
        return s;
    }
    swap(s[0], s[len-1]);
    return reverse(s.substr(1, len-2));
}
function-definition string recursion c++
2 Answers

You're calling your function with a substring each time and only returning the final character. In your lower return statement ( return reverse(s.substr(1, len-2)); ) you need to include the first and last characters as well.

Something like: return s[0] + reverse(s.substr(1,len-2)) + s[len-1];

Portal0

The word "Hello" has an odd number of letters. So the last recursive call of the function returns the letter 'l' due to this if statement

if (len <= 1)
{
    return s;
}

that is the return value of all the recursive calls of the function.

You should write at least like

string reverse(string s)
{
    auto len = s.length();
    if (len <= 1)
    {
        return s;
    }
    swap(s[0], s[len-1]);
    return s[0] + reverse(s.substr(1, len-2)) + s[len-1];
}

In fact using the function swap is redundant. You could write

string reverse(string s)
{
    return s.length() < 2 ? s 
                          : s[s.length() - 1] + reverse( s.substr( 1, s.length() - 2 ) ) + s[0];
}

Without the recursion the function can look for example the following way

string reverse( const string &s )
{
    return { s.rbegin(), s.rend() };
}
Vlad from Moscow0
Related