Recursive program to print reverse of a string
Given a string, print it backwards using recursion.
For example, consider the input string “Techie Delight”. The output should be “thgileD eihceT”.
As seen in the previous post, we can easily reverse a string using the stack data structure. Since the stack is involved, we can easily modify the code to use the call stack. As recursion finishes, print the characters stored in the call stack one by one.
Following is the C, C++, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <stdio.h> // Recursive function to print reverse of a given string void reverse(char *str, int k) { // base case: end of the string is reached if (*(str + k) == '\0') { return; } // recur for the next character reverse(str, k + 1); // print current character printf("%c", str[k]); } int main() { char str[] = "Techie Delight"; printf("Reverse of the given string is "); reverse(str, 0); return 0; } |
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <string> using namespace std; // Recursive function to print reverse of a given string void reverse(string str, int k = 0) { // base case: end of the string is reached if (k == str.length()) { return; } // recur for the next character reverse(str, k + 1); // print current character cout << str[k]; } int main() { string str = "Techie Delight"; cout << "Reverse of the given string is "; reverse(str); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Main { // Recursive function to print reverse of a given string public static void reverse(char str[], int k) { // base case: end of the string is reached if (k == str.length) { return; } // recur for the next character reverse(str, k + 1); // print current character System.out.print(str[k]); } public static void main (String[] args) { char str[] = "Techie Delight".toCharArray(); System.out.print("Reverse of the given string is "); reverse(str, 0); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Recursive function to print reverse of a given string def reverse(s, k): # base case: end of the string is reached if k == len(s): return # recur for the next character reverse(s, k + 1) # print current character print(s[k], end='') if __name__ == '__main__': s = 'Techie Delight' print('Reverse of the given string is', end=' ') reverse(s, 0) |
The time complexity of the above solution is O(n) and requires O(n) implicit space for the call stack, where n is the length of the input string.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)