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 slicing tricks like [::-1].

The recursive insight is: reversing a string means putting the first character at the end, after reversing the rest. Alternatively, you can recurse to the end of the string and build the result on the way back. The base case is reaching the end of the string (index == len). Each recursive call processes one character deeper, and concatenation happens on the way back up.

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

- Using [::-1] slicing — this works but defeats the purpose of learning recursion - Not understanding how the concatenation order creates the reversal (the deepest character is added first) - String concatenation in Python creates new strings, making this O(N^2) — for production, use a list and join - Forgetting the base case, leading to infinite recursion

This problem shows how recursion can replace iteration for string processing. The pattern of "recurse to the end, then build on the way back" is important — it appears in tree traversals and many other recursive algorithms. Understanding the call stack unwinding process is key to grasping how this reversal works.