How to reverse a string using recursion in Java

During one of my software testing interviews with Persistent Systems, the interviewer asked me to write a program to reverse a String. After I completed the solution, he asked a follow-up question: “How would you reverse the String using recursion?”

This was an interesting question because recursion requires a different way of thinking compared to using a simple loop.

In this article, I am going to explain how to reverse a String using recursion in Java, along with how recursion works and why a base case is important.

What is Recursion?

Recursion is a technique where a method calls itself to solve a problem by breaking it down into smaller subproblems.

For example, a recursive method can call itself with a smaller portion of the input until it reaches a condition where it can stop.

A recursive method generally consists of two important parts:

1. Recursive case – The method calls itself with a smaller or simpler input.
2. Base case – The condition that stops further recursive calls.

The base case is very important. Without it, the method would continue calling itself indefinitely, eventually causing a StackOverflowError.

Since recursive method calls are stored on the call stack, a very large number of recursive calls can consume significant stack memory.

In the next section, let’s see how we can use recursion to reverse a String in Java.

The following program demonstrates how to reverse a String using recursion in Java.

import org.testng.annotations.Test;

public class StringFunctions {

    String s = "Selenium Automation";

    @Test
    public void recursiveReverse() {

        int len = s.length() - 1;

        String rev = reverse(len);

        System.out.println("Reverse of " + s + " is " + rev);
    }

    public String reverse(int index) {

        if (index == 0) {
            return String.valueOf(s.charAt(index));
        } else {
            return String.valueOf(s.charAt(index)) + reverse(index - 1);
        }
    }
}

Explanation:

In the above program, we use the reverse(int index) method recursively, starting from the last index of the String, which is s.length() - 1, and continue until the index reaches 0.

From the StringFunctions class, the recursiveReverse() method is executed using the TestNG @Test annotation. Inside this method, we call the reverse() method and print the returned result.

The reverse() method takes the current index as an argument. It retrieves the character at that index using s.charAt(index), converts it to a String using String.valueOf(), and then appends the result of the next recursive call, passing index - 1 as the argument.

This process continues until the index reaches 0. When index == 0, the base case is reached, and the method returns the character at index 0. The recursive calls then return in reverse order, producing the reversed String.

In this program, we pass the String "Selenium Automation" as the input. The program reverses the String using recursion and produces the following output:

Output: "noitamotuA muineleS"

Watch YouTube video here: Reverse a string using recursion in Java