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 coding is awesome. Input: emosewa si gnidoc Output: Recursion is easy ysae si noisruceR Input: Output: 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. 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. Induction Hypothesis: 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. Base condition: 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. Generating the solution: 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]. - Example 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));
		
		}
	}
} Note: Since the String in java is completely immutable every time we append the solution string in every recursive call, java internally generates a new string with the content of the joined string. This increases the worst-case time complexity from O(n) to O(n^2), where n is the length of the input string. 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 class with time complexity O(n) is as follows: StringBuilder 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 rather take an extra integer input is as follows: substr function #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;
}

Apple

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

How to Check if a Graph is Bipartite in C++

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

How to Check if a Graph is Bipartite in C++

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps