How to Reverse a Sentence Using Recursion in C++ and Java

Problem statement

We are given a sentence that needs to be reversed using the method of recursion. By reversing, we mean the interchange of characters starting from the right to the left, i.e. interchanging (i)th character with (n-i)th character, where n is the length of the given string.

Example

Input: coding is awesome.

Output: emosewa si gnidoc

Input: Recursion is easy Output: ysae si noisruceR

Recursive Algorithm

An easy way to solve the problem is through simple iteration by just using a for loop with i from index 0 to n/2 and then character interchanging with n-i. But here, we will look into the solution of the problem using recursion.

Since a solution using recursion involves the idea to represent a problem in terms of one or smaller problems. It mainly consists of three main things:

• Induction hypothesis.

• Base condition.

• Generating the solution assuming the hypothesis to be correct.

  
  

Induction Hypothesis: Let say we have a string of length n and let's assume that reverseFunction() is the function that takes a string as an input and returns the string which is the reverse of the input string.

Base condition: When n=0 or n=1 (empty string) return input string only. Since the reverse of a single character or an empty string is itself only.

Generating the solution: Now we need to calculate the reverse of a string of length n and we have the reverse of the string with length n-1. Therefore, the reverse of the string with length n will be the reverse of a string with length n-1 with the additional character attached at last.

Example - For string s of length n, Rev(s,i) will return the reverse of the string from index i to n. Rev(s,0) = Rev(s,1)+s[0]. Let’s say s=”APPLE” Rev(s,0) = “ELPPA”, while Rev(s,1) = “ELPP” and s[0]=”A”. Therefore Rev(s,0) == rev(s,1) +s[0].

Let F(s,0) be the reverse function. Where s=”APPLE” , n=5. F(s,0) => F(s,1)+”A”. => “ELPP” + “A” = “ELPPA”. F(s,1) => F(s,2) + “P” => “ELP”+”P” = “ELPP” F(s,2) => F(s,3) + “P” => “EL” + ”P” = “ELP” F(s,3) => F(s,4) + “L” => “E”+”L” = “EL” F(s,4) => F(s,5) + “E” => “E”.

Java Implementation

The algorithm involves the use of the recursive reverse function which works on the above induction hypothesis and recursion. It basically uses the substring function of strings and concatenates the string in every recursive call.

import java.util.*;
public class Main
{
    static String reverseFunction(String s){
        if( s.length()==0 ){
            return new String();                         // Base Case
        }
        return reverseFunction(s.substring(1)) + s.charAt(0);       // recursion call
    }
// Tester Code / Input Code

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		while(n-->0){
		System.out.print("Input: ");
		String s = sc.nextLine();
		System.out.print("Output: ");
		System.out.println(reverseFunction(s));
		
		}
	}
}

One solution to the above problem is to use an inbuilt string class of java that is mutable i.e. StringBuilder, which cuts/appends the string in O(1) time. Therefore, java code using StringBuilder class with time complexity O(n) is as follows:

import java.util.*;
public class Main
{
    static StringBuilder reverseFunction(String s){
        if( s.length()==0 ){
            return new StringBuilder();          // Base case
        }
        return reverseFunction(s.substring(1)).append(s.charAt(0));     // recursive call
    }

// Tester Code / Input Code

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		while(n-->0){
		System.out.print("Input: ");
		String s = sc.nextLine();
		System.out.print("Output: ");
		System.out.println(reverseFunction(s));
		
		}
	}
}

Output: -
2
Input: Hello World!
Output: !dlroW olleH
Input: Reverse it.
Output: .ti esreveR

Another better solution/algorithm to avoid concatenation of string in every recursive call is to use another parameter that will take input i as an integer such that the function will give the reverse of the string starting from the index i to the end of the string.

Java code for the following is given below:

import java.util.*;
public class Main
{
    static String reverseFunction(String s, int i){
        if(i==s.length()){
            return "";                               		// base case
        }
        return reverseFunction(s,i+1)+s.charAt(i);   // recursive call
    }


// Tester Code / Input Code

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		while(n-->0){
		System.out.print("Input: ");
		String s = sc.nextLine();
		System.out.print("Output: ");
		System.out.println(reverseFunction(s,0));
		}
	}
}

The complexity can further be improved by the use of the StringBuilder class in the recursive call to append the character since the use of string makes a new string in every recursive call. The implementation for that is given below.

import java.util.*;
public class Main
{
    static StringBuilder reverseFunction(String s, int i){
        if( i == s.length() ){
            return new StringBuilder();
        }
        return reverseFunction(s,i+1).append(s.charAt(i));
    }
// Tester Code / Input Code

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		while(n-->0){
		System.out.print("Input: ");
		String s = sc.nextLine();
		System.out.print("Output: ");
		System.out.println(reverseFunction(s,0));
		}

		}
	}
}

Output:

C++ Code Implementation

Since the string in C++ is mutable. Therefore, we don’t need to implement the strings with any different classes.

Thus, the first implementation with input string as only recursive function parameter is as follows:

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
static string reverseFunction(string &s){
    if (s.length()==0) return s;
    string rest = s.substr(1);
    return reverseFunction(rest) + s[0];
}


int main()
{
    string s;
    s= "Interviewbit is Cool";
    cout<< "Input string is : "<<"\""<<s<<"\""<<endl;
    cout <<"Output reversed string is : "<<"\""<< reverseFunction(s) <<"\""<< endl;
    

    return 0;
}

You could also try running this code on an online C++ compiler.

Output:

Input string is : "C++ is Cool"

Output reversed string is : "looC si ++C"

The second implementation which doesn't make use of the substr function rather take an extra integer input is as follows:

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
static string reverseFunction(string s , int i){
    if (i==s.length()) return "";
    return reverseFunction(s,i+1) + s[i];
}


// Input Code/ Tester Code
int main()
{
    int n;
    cin >> n ;
    while (n-- > 0) {
    string s;
    getline( cin , s );
    cout << reverseFunction(s,0) << endl;
    }
    return 0;
}