Reverse a String Using Recursion

Given a string S, produce its reverse using a recursive function - that is, express the reverse of S in terms of the reverse of a shorter substring, rather than an iterative loop or a built-in reverse utility. Print the reversed string.

Input: A single line containing the string S. Output: A single line containing S reversed.

1 <= |S| <= 1000. S consists of printable ASCII characters with no leading or trailing whitespace.

This exact 'peel off the first element, recurse on the rest, combine at the end' template is identical in shape to 'Sum of Digits', just applied to characters instead of digits - recognizing shared templates across problems builds recursive intuition faster than treating each as brand new.

Reverse a string by expressing its reverse in terms of the reverse of a shorter piece of itself. Brute force: Reverse the string iteratively with a loop (or two-pointer swap) - equally efficient, but this problem specifically asks for the recursive framing (no loops, no built-in reverse utility) to practice expressing reversal as recursion. Optimised: Expressing 'the reverse of the whole string' as 'the reverse of everything AFTER the first character, with the first character appended at the end' directly captures the recursive structure of reversal - each call handles one character, trusting the smaller recursive call to correctly reverse the rest.

1. The BASE CASE: the reverse of a string of length 0 or 1 is itself. 2. The RECURSIVE CASE: reverse(S) = reverse(S without its first character) + the first character of S. 3. Each call strips off the first character, recursively reverses what's left, and appends the stripped character at the very end.

Time: O(n²) if string concatenation at each step costs O(n) (common in many languages, since strings are often immutable), or O(n) if implemented with a mutable buffer instead. Space: O(n), for the recursion call stack (one frame per character).

A string of length 1 reverses to itself. The maximum length (1000) must be handled without exceeding recursion limits.

Be ready to discuss the potential O(n²) time cost if naive string concatenation is used at every recursive level (due to immutable strings) - a good example of how a seemingly simple recursive solution can hide a real efficiency trap.