Reverse a String Recursively

Problem Statement

Write a Java program that uses recursion to reverse a string by breaking it into smaller substrings. The program should take a string as input and return the reversed string. Test the program with various strings, including empty strings and single-character strings. You can visualize this as rearranging the letters of a word written on a whiteboard, starting from the last letter and moving backward to the first, using smaller pieces of the word.

Input: A string (e.g., str = "hello"). Output: A string representing the reversed input (e.g., "olleh"). Constraints:

• The string length is between 0 and 10^5.
• The string contains printable ASCII characters.
• The string may be empty. Example:
• Input: str = "hello"
• Output: "olleh"
• Explanation: The string "hello" is reversed to "olleh" by rearranging its characters starting from the last one.

Pseudocode

FUNCTION reverseString(str)
    IF str is null OR length of str <= 1 THEN
        RETURN str
    ENDIF
    SET lastChar to character at index (length of str - 1)
    SET substring to str from index 0 to (length of str - 1)
    RETURN lastChar + reverseString(substring)
ENDFUNCTION

Algorithm Steps

1. Check if the input string is null, empty, or has one character. If so, return the string as is, since no reversal is needed.
2. Define a recursive function that takes the input string as a parameter.
3. In the recursive function, implement the base case: if the string is empty or has one character, return the string itself.
4. For the recursive case, extract the last character of the string and recursively call the function on the substring excluding the last character.
5. Combine the last character with the result of the recursive call to build the reversed string.
6. Return the final reversed string from the initial function call.

Java Implementation

public class ReverseStringRecursively {
    // Reverses a string using recursion
    public String reverseString(String str) {
        // Check for null, empty, or single-character string
        if (str == null || str.length() <= 1) {
            return str;
        }
        // Recursive case: last character + reverse of remaining string
        return str.charAt(str.length() - 1) + reverseString(str.substring(0, str.length() - 1));
    }
}

Output

For the input string "hello", the program outputs:

olleh

Explanation: The string "hello" is reversed to "olleh" by recursively rearranging characters.

For an empty string "", the program outputs:

""

Explanation: An empty string remains empty after reversal.

For a single-character string "a", the program outputs:

a

Explanation: A single-character string is already reversed.

How It Works

• Step 1: The reverseString method checks if the input string is null, empty, or has one character. For "hello", it has length 5, so it proceeds to the recursive case.
• Step 2: In the recursive case:
  • For "hello": Returns 'o' + reverseString("hell").
  • For "hell": Returns 'l' + reverseString("hel").
  • For "hel": Returns 'l' + reverseString("he").
  • For "he": Returns 'e' + reverseString("h").
  • For "h": Base case reached (length 1), returns "h".
• Step 3: The recursion unwinds: 'h' + 'e' + 'l' + 'l' + 'o' = "olleh".
• Example Trace: For "hello", the algorithm recursively processes: 'o' + reverse("hell") = 'o' + ('l' + reverse("hel")) = 'o' + 'l' + ('l' + reverse("he")) = 'o' + 'l' + 'l' + ('e' + reverse("h")) = 'o' + 'l' + 'l' + 'e' + 'h' = "olleh".

Complexity Analysis Table

Note:

• n is the length of the input string.
• Time complexity: O(n), as the algorithm makes one recursive call per character.
• Space complexity: O(n) due to the recursive call stack and the creation of substrings in Java, which involves new string objects.
• Best, average, and worst cases are all O(n), as every character is processed exactly once.

✅ Tip: Use recursion for string reversal when the problem naturally breaks into smaller subproblems, and test with edge cases like empty strings, single characters, or long strings to ensure robustness.

⚠ Warning: Be cautious with very long strings, as the O(n) space complexity from the recursive call stack and substring creation can lead to stack overflow or memory issues. Consider iterative solutions for large inputs.