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

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));
}

CodePudding user response：

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];

CodePudding user response：

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() };
}