Module 15 · Recursion and Divide-and-Conquer

144. Reverse a String Recursively

Foundation · Download this solution · All solutions and shared helpers

Problem

Return a string reversed through a recursive algorithm. Strings are treated as sequences of Python characters, without Unicode grapheme normalization. Empty input returns an empty string. Use a mutable character buffer so recursion need not create a new suffix string at every level.

Examples

Example 1

recursive_reverse("abcd")
=> 'dcba'

Each recursive level finalizes one mirrored pair.

Example 2

recursive_reverse("")
=> ''

The initial interval is empty.

Example 3

recursive_reverse("abc")
=> 'cba'

The middle character is its own mirror.

Reveal the worked solution and reasoning

Why this mechanism works

Define the helper contract on an inclusive interval of the character buffer: reverse that interval. Swap its two endpoints, which have fixed final destinations, then delegate the smaller interior. The recursion stops once fewer than two positions remain.

State and boundaries

chars is the mutable output buffer. reverse(left,right) owns the interval it must reverse; outside positions are already final.

Protocol

Copy characters into a list.
Stop the helper when left>=right.
Swap endpoints.
Recursively reverse the interior.
Join the buffer into the returned string.

Visualization

abcd -> swap a,d -> dbca
reverse interior bc -> cb
result dcba

Python implementation

def recursive_reverse(text):
    chars = list(text)
    def reverse(left, right):
        if left >= right:
            return
        chars[left], chars[right] = chars[right], chars[left]
        reverse(left + 1, right - 1)
    reverse(0, len(chars) - 1)
    return ''.join(chars)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

recursive_reverse("abcd")

L2 recursive_reverse: chars = list(text)
text='abcd'; chars=['a', 'b', 'c', 'd']

L4 reverse: if left >= right:
left=0; right=3; chars=['a', 'b', 'c', 'd']

L6 reverse: chars[left], chars[right] = chars[right], chars[left]
left=0; right=3; chars=['d', 'b', 'c', 'a']

L4 reverse: if left >= right:
left=1; right=2; chars=['d', 'b', 'c', 'a']

L6 reverse: chars[left], chars[right] = chars[right], chars[left]
left=1; right=2; chars=['d', 'c', 'b', 'a']

L4 reverse: if left >= right:
left=2; right=1; chars=['d', 'c', 'b', 'a']

L7 reverse: reverse(left + 1, right - 1)
left=0; right=3; chars=['d', 'c', 'b', 'a']

L8 recursive_reverse: reverse(0, len(chars) - 1)
text='abcd'; chars=['d', 'c', 'b', 'a']

Result: 'dcba'. Each recursive level finalizes one mirrored pair.

recursive_reverse("")

L2 recursive_reverse: chars = list(text)
text=''; chars=[]

L4 reverse: if left >= right:
left=0; right=-1; chars=[]

Result: ''. The initial interval is empty.

Why the solution is correct

The base interval is empty or a singleton and is already reversed. For a larger interval, swapping endpoints puts them in their mirrored destinations, while the recursive call correctly reverses the remaining interior. Induction on interval size proves the whole reversal.

Time and space

O(n) time and O(n) space for the character buffer and linear-depth call stack.

Common mistakes

Recursing on text[1:] copies shrinking suffixes and can use quadratic aggregate storage. A string itself cannot be mutated at an index.

Reasoning card

State: chars is the mutable output buffer. reverse(left,right) owns the interval it must reverse; outside positions are already final.

Invariant: Each call returns the reversed form of its own substring.

Decision to rehearse: Solve the suffix and place the first character appropriately.

Finish: Join the buffer into the returned string

Transfer exercise

Explain why the iterative two-pointer version uses constant auxiliary state while this recursive version still has linear call depth.