Reverse String

Write a recursive function reverse_string(s) that returns the reversed string. Input: "hello" → Output: "olleh". Input: "abc" → Output: "cba". You must use recursion — no loops or [::-1].

Reversing recursively: recurse to the end of the string, then append characters in reverse order as the stack unwinds. The $i$-th call places s[i] after all characters from index $i+1$ onward.

1. Use an index parameter (default 0) to track position.
2. Base case: if index == len(str), return "".
3. Recursive case: return reverse_string(str, index + 1) + str[index].
4. This recurses to the end first, then appends characters in reverse on the way back.

• Using [::-1] slicing — correct but defeats the purpose of learning recursion
• Not understanding how the concatenation order creates the reversal
• String concatenation in Python creates new strings — $O(N^2)$ total; use a list + join for production
• Forgetting the base case, causing infinite recursion

The pattern of "recurse to the end, then build on the way back" appears in tree traversals and many recursive algorithms. Understanding the call stack unwinding is key to grasping how this reversal works.