Problem Statement
The task is to reverse a given string using recursion.
Definition
- Given a string, reverse the order of characters in the string.
- Example: For the input "hello", the reversed string would be "olleh".
Example Inputs
- Input: "hello"
- Output: "olleh"
Explanation: The reversed string of "hello" is "olleh".
Approach - Use Recursion
Approach
The recursive approach to reversing a string works by reducing the string step by step. At each recursive call, we take the first character of the string and append it to the reversed substring obtained from the rest of the string.
Steps
- If the string is empty, return the string (base case: an empty string is already reversed).
- Otherwise, take the first character, reverse the rest of the string, and then append the first character to the reversed substring.
- Continue the process until the string is fully reversed.
Time & Space Complexity
- Time Complexity: O(n), where
n is the length of the string. We traverse each character of the string once.
- Space Complexity: O(n), due to the recursion stack. Each recursive call adds a new layer to the stack.
Code Snippet
Dry Run
Let’s dry run the code with the input str = "hello":
- reverseString("hello"): reverseString("ello") + "h"
- reverseString("ello"): reverseString("llo") + "e"
- reverseString("llo"): reverseString("lo") + "l"
- reverseString("lo"): reverseString("o") + "l"
- reverseString("o"): reverseString("") + "o"
- reverseString(""): return "" (base case)
- Return from reverseString("o"): "" + "o" = "o"
- Return from reverseString("lo"): "o" + "l" = "ol"
- Return from reverseString("llo"): "ol" + "l" = "oll"
- Return from reverseString("ello"): "oll" + "e" = "olle"
- Return from reverseString("hello"): "olle" + "h" = "olleh"
Output:
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(n), where
n is the number of characters in the string. We traverse each character once.
- Space Complexity: O(n) due to the recursion stack. Each recursive call adds a layer to the stack.
Conclusion
The recursive approach to reversing a string is simple and effective, though it comes with a space complexity of O(n) because of the recursion stack. This approach is suitable for smaller strings. For larger strings, an iterative approach might be more efficient in terms of space.