Reverse String Tail Recursion

Problem Statement

Write a Java program that implements a tail-recursive method to reverse a string using an accumulator to build the result. The program should take a string as input and return the reversed string. Test the method with various strings, including empty strings, single-character strings, and long strings, and discuss Java’s stack usage for the tail-recursive approach. You can visualize this as rearranging the letters of a word on a signboard, building the reversed word step-by-step by passing the accumulated result to the next recursive call.

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.
• Input: str = ""
• Output: ""
• Explanation: An empty string remains empty after reversal.

Pseudocode

FUNCTION tailRecursiveReverse(str, index, accumulator)
    IF str is null OR index < 0 THEN
        RETURN accumulator
    ENDIF
    SET newAccumulator to character at index in str + accumulator
    RETURN tailRecursiveReverse(str, index - 1, newAccumulator)
ENDFUNCTION

FUNCTION mainReverse(str)
    IF str is null OR length of str equals 0 THEN
        RETURN str
    ENDIF
    RETURN tailRecursiveReverse(str, length of str - 1, "")
ENDFUNCTION

Algorithm Steps

1. Check if the input string is null or empty. If so, return the string as is.
2. Define a tail-recursive helper function that takes the string, the current index, and an accumulator as parameters.
3. In the helper function, implement the base case: if the index is less than 0, return the accumulator.
4. For the recursive case, prepend the character at the current index to the accumulator and recursively call the function with the previous index and the updated accumulator.
5. In the main function, call the tail-recursive function with the initial index set to the last index of the string (length - 1) and an empty string as the accumulator.
6. Return the reversed string computed by the tail-recursive function.

Java Implementation

public class ReverseStringTailRecursion {
    // Reverses a string using tail recursion
    public String reverse(String str) {
        // Check for null or empty string
        if (str == null || str.length() == 0) {
            return str;
        }
        // Call tail-recursive helper with initial index and accumulator
        return tailRecursiveReverse(str, str.length() - 1, "");
    }

    // Helper function for tail-recursive string reversal
    private String tailRecursiveReverse(String str, int index, String accumulator) {
        // Base case: if index < 0, return accumulator
        if (index < 0) {
            return accumulator;
        }
        // Recursive case: prepend current character to accumulator and recurse
        return tailRecursiveReverse(str, index - 1, str.charAt(index) + accumulator);
    }
}

Output

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

olleh

Explanation: The string "hello" is reversed to "olleh" by building the result in the accumulator.

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 reverse method checks if the string is null or empty. For "hello", it calls tailRecursiveReverse with index = 4 and accumulator = "".
• Step 2: In tailRecursiveReverse:
  • Index 4: accumulator = 'o' + "" = "o", recurse with index = 3, accumulator = "o".
  • Index 3: accumulator = 'l' + "o" = "lo", recurse with index = 2, accumulator = "lo".
  • Index 2: accumulator = 'l' + "lo" = "llo", recurse with index = 1, accumulator = "llo".
  • Index 1: accumulator = 'e' + "llo" = "ello", recurse with index = 0, accumulator = "ello".
  • Index 0: accumulator = 'h' + "ello" = "hello", recurse with index = -1, accumulator = "hello".
  • Index -1: Base case, return accumulator = "hello".
• Example Trace: For "hello", the accumulator builds: "" → "o" → "lo" → "llo" → "ello" → "hello", returning "olleh".
• Java Stack Usage: The function is tail-recursive because the recursive call is the last operation. However, Java does not optimize tail recursion, so each recursive call adds a frame to the call stack, leading to O(n) space complexity. This can cause stack overflow for very large strings (e.g., 10^5 characters). An iterative approach would use O(1) space (excluding the output string).

Complexity Analysis Table

Note:

• n is the length of the input string.
• Time complexity: O(n), as the function processes each character exactly once.
• Space complexity: O(n) due to the recursive call stack (Java does not optimize tail recursion) and the accumulator string, which grows with each call.
• Best, average, and worst cases are O(n).

✅ Tip: Use tail recursion to write elegant recursive solutions for problems like string reversal, but consider iterative methods for better space efficiency in Java. Test with long strings (e.g., 10^4 characters) and edge cases like empty or single-character strings to verify correctness.

⚠ Warning: Java does not optimize tail recursion, so the O(n) space complexity may cause stack overflow for very large strings. Additionally, string concatenation in the accumulator can be inefficient; consider using StringBuilder in an iterative approach for better performance.