Reverse String Comparison

Problem Statement

Write a Java program that implements string reversal using both recursive and iterative approaches. The program should take a string as input and return the reversed string. Test the program with various strings, including empty strings, single-character strings, and long strings, and compare the code readability and execution time of both approaches. You can visualize this as rearranging the letters of a word on a signboard, either by recursively breaking it into smaller parts or by iteratively swapping characters from the ends toward the center.

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 recursiveReverse(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 + recursiveReverse(substring)
ENDFUNCTION

FUNCTION iterativeReverse(str)
    IF str is null OR length of str <= 1 THEN
        RETURN str
    ENDIF
    CONVERT str to array of characters
    SET left to 0
    SET right to length of array - 1
    WHILE left < right
        SWAP characters at left and right
        INCREMENT left
        DECREMENT right
    ENDWHILE
    RETURN array converted to string
ENDFUNCTION

Algorithm Steps

1. For the recursive approach: a. Check if the input string is null, empty, or has one character. If so, return the string as is. b. Define a recursive function that takes the input string as a parameter. c. Extract the last character of the string and recursively call the function on the substring excluding the last character. d. Combine the last character with the result of the recursive call to build the reversed string. e. Return the reversed string.
2. For the iterative approach: a. Check if the input string is null, empty, or has one character. If so, return the string as is. b. Convert the string to a character array for in-place manipulation. c. Initialize two pointers: left at the start (index 0) and right at the end (index length - 1). d. While left is less than right, swap the characters at left and right, increment left, and decrement right. e. Convert the character array back to a string and return it.
3. Test both methods with various inputs and measure execution time for large strings to compare performance.

Java Implementation

public class ReverseStringComparison {
    // Reverses a string using recursion
    public String recursiveReverse(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) + recursiveReverse(str.substring(0, str.length() - 1));
    }

    // Reverses a string using iteration
    public String iterativeReverse(String str) {
        // Check for null, empty, or single-character string
        if (str == null || str.length() <= 1) {
            return str;
        }
        // Convert string to char array
        char[] charArray = str.toCharArray();
        int left = 0;
        int right = charArray.length - 1;
        // Swap characters from ends toward center
        while (left < right) {
            char temp = charArray[left];
            charArray[left] = charArray[right];
            charArray[right] = temp;
            left++;
            right--;
        }
        // Convert char array back to string
        return new String(charArray);
    }
}

Output

For the input string "hello", both methods output:

olleh

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

For an empty string "", both methods output:

""

Explanation: An empty string remains empty after reversal.

For a single-character string "a", both methods output:

a

Explanation: A single-character string is already reversed.

How It Works

• Recursive Approach:
  • Step 1: The recursiveReverse method checks if the string is null, empty, or has one character. For "hello", it proceeds to recursion.
  • Step 2: Recursion:
    • For "hello": Returns 'o' + recursiveReverse("hell").
    • For "hell": Returns 'l' + recursiveReverse("hel").
    • For "hel": Returns 'l' + recursiveReverse("he").
    • For "he": Returns 'e' + recursiveReverse("h").
    • For "h": Base case, returns "h".
    • Unwind: 'h' + 'e' + 'l' + 'l' + 'o' = "olleh".
  • Example Trace: For "hello", computes 'o' + ('l' + ('l' + ('e' + 'h'))) = "olleh".
• Iterative Approach:
  • Step 1: The iterativeReverse method checks if the string is null, empty, or has one character. For "hello", it converts to ['h', 'e', 'l', 'l', 'o'].
  • Step 2: Initializes left = 0, right = 4. Swaps:
    • Swap h and o: ['o', 'e', 'l', 'l', 'h'], left = 1, right = 3.
    • Swap e and l: ['o', 'l', 'l', 'e', 'h'], left = 2, right = 2.
    • Stop as left >= right.
  • Step 3: Converts array to "olleh".
  • Example Trace: For "hello", swaps characters from ends: h ↔ o, e ↔ l, resulting in "olleh".
• Comparison:
  • Readability: Iterative is more straightforward, using simple swaps, while recursive is more abstract but elegant for small inputs.
  • Execution Time: Iterative is faster for large strings due to O(1) space complexity, while recursive uses O(n) space and creates substrings, increasing overhead.

Complexity Analysis Table

Note:

• n is the length of the input string.
• Time complexity: O(n) for both, as recursive processes each character once, and iterative performs n/2 swaps.
• Space complexity: O(n) for recursive due to call stack and substring creation; O(n) for iterative due to the character array (though in-place swapping reduces overhead in practice).
• Best, average, and worst cases are O(n) for both.

✅ Tip: Use the iterative approach for large strings to avoid stack overflow and reduce memory usage due to substring creation in recursion. Test both methods with long strings (e.g., 10^4 characters) to compare execution times and assess readability.

⚠ Warning: The recursive approach may cause stack overflow for very large strings due to O(n) space complexity from the call stack and substring operations. Ensure inputs are within reasonable bounds to prevent performance issues.