Recursive solution to reverse a String in Java
In this post, we will show we how to reverse a string in Java using recursion.
Recursion is a technique of solving a problem by breaking it down into smaller subproblems and calling the same function repeatedly. In the previous post, we have discussed how we can easily reverse a string in Java using the stack data structure. As the stack is involved, we can easily convert the code to use recursion. There are several ways to reverse a string using recursion in Java:
1. Using a char array
The idea here is to first convert the given string into a character array, reverse the character array recursively, and finally convert the character array back into a string. Here is an example of how to write and use a recursive function to reverse a string in Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
class Main { // Recursive method to reverse given character array private static void reverse(char[] chars, int l, int h) { if (l < h) { char ch = chars[l]; chars[l] = chars[h]; chars[h] = ch; reverse(chars, l + 1, h - 1); } } // Recursive method to reverse a string in Java public static String reverse(String str) { // base case: if the string is null or empty if (str == null || str.isEmpty()) { return str; } // convert string into a character array char[] chars = str.toCharArray(); // reverse character array reverse(chars, 0, chars.length - 1); // convert character array into the string return String.copyValueOf(chars); } public static void main(String[] args) { String str = "Reverse me!"; // string is immutable str = reverse(str); System.out.println("Reversed string: " + str); // "!em esreveR" } } |
2. Using substring() method
We can also use String.substring() method to recursively reverse a string in Java. The idea is to use the String.charAt() method to isolate the first or last character of the string and recur for the remaining string using substring().
Approach #1: Isolate last character
The recursive case here is when the string has more than one character, we remove the last character from the string and append it to the start of the reversed substring. The base case is when the string is empty or has only one character, in which case we return the same string.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Main { // Method to reverse a string in Java using recursion private static String reverse(String str) { // base case: if the string is null or empty if (str == null || str.isEmpty()) { return str; } // last character + recur for the remaining string return str.charAt(str.length() - 1) + reverse(str.substring(0, str.length() - 1)); } public static void main(String[] args) { String str = "Reverse me!"; // string is immutable str = reverse(str); System.out.println("Reversed string: " + str); // "!em esreveR" } } |
Approach #2: Isolate first character
The recursive case here is when the string has more than one character, we remove the first character from the string and append it to the end of the reversed substring. The base case is when the string is empty or has only one character, in which case we return the same string.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Main { // Method to reverse a string in Java using recursion public static String reverse(String str) { // base case: if the string is null or empty if (str == null || str.isEmpty()) { return str; } // isolate the first character and recur for the remaining string return reverse(str.substring(1)) + str.charAt(0); } public static void main(String[] args) { String str = "Reverse me!"; // string is immutable str = reverse(str); System.out.println("Reversed string: " + str); // "!em esreveR" } } |
However, using recursion to reverse a string in Java is inefficient and prone to errors. This approach creates multiple function calls and string objects, which consume more memory and time. Also it can cause stack overflow error if the string is too long or the recursion is too deep.
That’s all about recursively reversing a string in Java.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)