Reverse a String by Swapping Mirrored Characters

A string reverses when every mirrored pair swaps places

The characters in "CODE" sit at indices 0 through 3. To reverse the string, pair the character at the left end with the character at the right end, then move toward the center. The first mirrored pair is C at index 0 and E at index 3. Swapping them changes the string from "CODE" to "EODC".

Before: C O D E
         0 1 2 3

Swap indices 0 and 3:

After:  E O D C
         0 1 2 3

The first swap does not finish the reversal because O and D are still in the wrong order. The recursive call must work on the remaining active range, from index 1 to index 2. That call swaps O and D, producing "EDOC". Each call handles one mirrored pair, so the whole operation is a sequence of pair swaps.

Both boundaries must move inward for recursion to reach the untouched pair

A recursive helper can describe its active range with two indices, left and right. It swaps those positions, then calls itself with left increased by one and right decreased by one. For "CODE", the calls are reverse(chars, 0, 3), reverse(chars, 1, 2), and reverse(chars, 2, 1). The first two calls swap a pair, and the last call stops.

void reverse(string& chars, int left, int right) {
    if (left >= right) {
        return;
    }

    swap(chars[left], chars[right]);
    reverse(chars, left + 1, right - 1);
}

The condition left >= right is the stopping condition. When left equals right, only the middle character remains, so it has no partner to swap with. When left is greater than right, every mirrored pair has already been handled. If only left moved inward while right stayed at 3, the next call would select indices 1 and 3, pairing O with C instead of pairing O with D. Recursion would continue, but it would no longer be reversing the original mirrored pairs.

Removing two active characters per call still takes linear time

Let k be the number of characters in the active range. One call swaps the two endpoints, which takes Theta(1) time, and leaves an active range with two fewer characters. The recurrence is T(k) = T(k - 2) + Theta(1). For "CODE", the active ranges have lengths 4, 2, and 0 across the three calls.

The recurrence makes about k / 2 pair-swaps before stopping. Dividing the input into pairs changes the number of calls by a constant factor, not by an entire level of growth, so the time complexity is Theta(n). The recursive calls remain on the call stack until the stopping call returns, giving O(n) recursive stack space. For four characters, the exact depth is three calls when the stopping call is included: reverse(chars, 0, 3), reverse(chars, 1, 2), and reverse(chars, 2, 1).

String mutability changes the wrapper, not the recursive steps

C++ strings can be changed through their character positions, so the helper can receive a std::string reference and swap its characters directly. The recursive steps stay the same: stop when left >= right, swap the two endpoints, then call the helper with left + 1 and right - 1.

void reverse(string& chars, int left, int right) {
    if (left >= right) {
        return;
    }

    swap(chars[left], chars[right]);
    reverse(chars, left + 1, right - 1);
}

string chars = "CODE";
reverse(chars, 0, 3);
cout << chars;

Java String objects cannot be changed character by character. The wrapper therefore copies "CODE" into a char[] first, passes that array through the same recursive helper, and builds a String from the changed array afterward. The mutable representation changes, but the active left and right indices, swap, inward call, and stopping condition do not.

static void reverse(char[] chars, int left, int right) {
    if (left >= right) {
        return;
    }

    char temp = chars[left];
    chars[left] = chars[right];
    chars[right] = temp;
    reverse(chars, left + 1, right - 1);
}

char[] chars = "CODE".toCharArray();
reverse(chars, 0, 3);
System.out.println(new String(chars));