Java Implementation
Java
public class StringReversal {
public static String reverseString(String s) {
if (s.isEmpty()) {
return s;
}
return reverseString(s.substring(1)) + s.charAt(0);
}
public static void main(String[] args) {
String original = "hello";
String reversed = reverseString(original);
System.out.println("Reversed string: " + reversed);
}
}

You can also try this code with Online Java Compiler
Run Code
Output
Reversed string: olleh
In this Java code, we define a method reverseString that checks if the string is empty. If it is, the method returns the empty string; otherwise, it calls itself with the rest of the string (s.substring(1)) & adds the first character to the end of the result of the recursion.
C Implementation
C
#include <stdio.h>
#include <string.h>
void reverseString(char *s, int start, int end) {
if (start >= end) return;
char temp = s[start];
s[start] = s[end];
s[end] = temp;
reverseString(s, start + 1, end - 1);
}
int main() {
char str[] = "hello";
reverseString(str, 0, strlen(str) - 1);
printf("Reversed string: %s\n", str);
}

You can also try this code with Online C Compiler
Run Code
Output
Reversed string: olleh
The C version uses a helper function reverseString that swaps characters from the start & end of the string until it meets in the middle, recursively moving closer to the center after each swap.
C++ Implementation
C++
#include <iostream>
#include <string>
void reverseString(std::string &s, int start, int end) {
if (start >= end) return;
std::swap(s[start], s[end]);
reverseString(s, start + 1, end - 1);
}
int main() {
std::string str = "hello";
reverseString(str, 0, str.length() - 1);
std::cout << "Reversed string: " << str << std::endl;
}

You can also try this code with Online C++ Compiler
Run Code
Output
Reversed string: olleh
This C++ code is similar to the C version but uses the std::swap function to make the character swapping cleaner & more efficient.
Python Implementation
Python
def reverse_string(s):
if s == "":
return s
else:
return reverse_string(s[1:]) + s[0]
original = "hello"
reversed_string = reverse_string(original)
print("Reversed string:", reversed_string)

You can also try this code with Online Python Compiler
Run Code
Output
Reversed string: olleh
Python's implementation is concise & clear. It uses string slicing to create substrings & recursion to build the reversed string step by step.
Time & Space Complexity of Recursive String Reversal
Understanding the time & space complexity of recursive methods is important because it helps us evaluate the efficiency of our code. Let's discuss the complexities for this :
Time Complexity
The time complexity of reversing a string recursively is O(n), where n is the length of the string. This is because the recursion needs to process each character in the string exactly once. For each character, the function is called recursively, leading to n calls in total.
Space Complexity
The space complexity for the recursive approach is also O(n). This is because each recursive call adds a layer to the call stack. Since there is a call for each character in the string, the maximum depth of the call stack will be n, which corresponds to n additional memory space used.
These complexities suggest that while the recursive method is elegant & easy to understand, it might not be the most efficient in terms of memory usage, especially for very long strings. This is due to the large number of call stack frames that could potentially lead to a stack overflow error if the string is too long.
Efficient Approach to String Reversal
While recursion is a straightforward way to reverse a string, there are more efficient methods that can reduce space complexity & avoid potential stack overflow errors for long strings. One effective approach is to use an iterative method, which uses a loop to swap characters until the middle of the string is reached.
Iterative Method
Here's how you can implement this method:
-
Initialize two pointers - One pointer starts at the beginning of the string, & the other at the end.
-
Swap characters - Swap the characters at the two pointers.
-
Move the pointers - Move the starting pointer one step forward & the ending pointer one step backward.
- Repeat the process - Continue this process until the two pointers meet in the middle.
This method only uses a constant amount of extra space, making the space complexity O(1). The time complexity remains O(n) because each character is still processed once. However, the absence of recursive calls means we do not have to worry about the call stack size, making this approach more suitable for very long strings.
Example in Python
Python
def iterative_reverse_string(s):
s = list(s)
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
original = "hello"
reversed_string = iterative_reverse_string(original)
print("Reversed string:", reversed_string)

You can also try this code with Online Python Compiler
Run Code
Output
Reversed string: olleh
This Python code converts the string into a list (since strings in Python are immutable), performs the swaps using a while loop, & then joins the list back into a string.
This efficient approach reduces the risk of running into memory issues & is a practical choice for applications where performance is a critical factor.
Frequently Asked Questions
Why does recursion use more memory than the iterative approach?
Recursion involves numerous function calls, which means each call adds a new layer to the stack. This increases memory usage compared to the iterative approach, which uses a fixed amount of memory throughout its execution.
Can recursion cause errors in string reversal?
Yes, if the string is very long, you might encounter a stack overflow error because of the deep recursion needed to reverse the string.
Is the iterative method always better than recursion for reversing strings?
While the iterative method is more memory-efficient, recursion is often clearer & easier to understand. The best method depends on the specific requirements of your application & the size of the input.
Conclusion
In this article, we've learned how to reverse a string using recursion & an iterative approach. We explored the implementation in Java, C, C++, & Python, & discussed the time & space complexities associated with each method. By comparing these approaches, we highlighted the practicality of the iterative method in scenarios where performance & memory efficiency are paramount.
You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.