C++ Program To Print Reverse of a String Using Recursion

Try it on GfG Practice

Write a recursive function to print the reverse of a given string. 
Code: 

// C++ program to reverse a string using recursion 
#include <bits/stdc++.h>
using namespace std;

/* Function to print reverse of the passed string */
void reverse(string str) 
{ 
    if(str.size() == 0)
    {
        return;
    }
    reverse(str.substr(1));
    cout << str[0];
} 

/* Driver program to test above function */
int main() 
{ 
    string a = "Geeks for Geeks"; 
    reverse(a); 
    return 0; 
} 

// This is code is contributed by rathbhupendra

Output: 
 

skeeG rof skeeG

Explanation: Recursive function (reverse) takes string pointer (str) as input and calls itself with next location to passed pointer (str+1). Recursion continues this way when the pointer reaches '\0', all functions accumulated in stack print char at passed location (str) and return one by one.

Time Complexity: O(n^2) as substr() method has a time complexity of O(k) where k is the size of the returned string. So for every recursive call, we are reducing the size of the string by one, which leads to a series like (k-1)+(k-2)+...+1 = k*(k-1)/2 = O(k^2) = O(n^2)
See Reverse a string for other methods to reverse string.
Auxiliary Space: O(n)

Efficient Approach: 

We can store each character in recursive stack and then can print while coming back as shown in the below code: 

// C++ program to reverse a string using recursion
#include <bits/stdc++.h>
using namespace std;

/* Function to print reverse of the passed string */
void reverse(char *str, int index, int n) 
{
    if(index == n)      // return if we reached at last index or at the end of the string
    {
        return;
    }
    char temp = str[index];    // storing each character starting from index 0 in function call stack;
    reverse(str, index+1, n);  // calling recursive function by increasing index everytime
    cout << temp;              // printing each stored character while recurring back
}

/* Driver program to test above function */
int main()
{
    char a[] = "Geeks for Geeks";
    int n = sizeof(a) / sizeof(a[0]);
    reverse(a, 0, n);
    return 0;
}

Output:

skeeG rof skeeG

Time Complexity: O(n) where n is size of the string

Auxiliary Space: O(n) where n is the size of string, which will be used in the form of function call stack of recursion.

Please suggest if someone has a better solution that is more efficient in terms of space and time.

kartik

Follow

Improve

Article Tags :

• C++ Programs
• C++
• CPP Strings Programs

Practice Tags :

• CPP