Write a recursive function that reverses the input string

Try this one

string reverse(string &s)
{
    if( s.length() == 0 )  // end condtion to stop recursion
        return "";

    string last(1,s[s.length()-1]);  // create string with last character
    string reversed = reverse(s.substr(0,s.length()-1));
    return last+reversed; // Make he last character first
}

A recursive function must have the following properties

  • It must call itself again
  • It must have a condition when the recursion ends. Otherwise you have a function which will cause a stack overflow.

This recursive function does basically create a string of the last character and then call itself again with the rest of the string excluding the last character. The real switching happens at the last line where last+reversed is returned. If it would be the other way around nothing would happen.

It is very inefficient but it works to show the concept.


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

I'll instead explain the recursive algorithm itself. Take the example "input" which should produce "tupni". You can reverse the string recursively by

  • If the string is empty or a single character, return it unchanged.
  • Otherwise,
    1. Remove the first character.
    2. Reverse the remaining string.
    3. Add the first character above to the reversed string.
    4. Return the new string.