Print reverse of a string using recursion
Write a recursive function to print the reverse of a given string.
Code:
C++
// C++ program to reverse a string using recursion #include <bits/stdc++.h> using namespace std; /* Function to print reverse of the passed string */ void reverse(string str) { if (str.size() == 0) { return ; } reverse(str.substr(1)); cout << str[0]; } /* Driver program to test above function */ int main() { string a = "Beginner for Beginner" ; reverse(a); return 0; } // This is code is contributed by rathbhupendra |
C
// C program to reverse a string using recursion # include <stdio.h> /* Function to print reverse of the passed string */ void reverse( char *str) { if (*str) { reverse(str+1); printf ( "%c" , *str); } } /* Driver program to test above function */ int main() { char a[] = "Beginner for Beginner" ; reverse(a); return 0; } |
Java
// Java program to reverse a string using recursion class StringReverse { /* Function to print reverse of the passed string */ void reverse(String str) { if ((str== null )||(str.length() <= 1 )) System.out.println(str); else { System.out.print(str.charAt(str.length()- 1 )); reverse(str.substring( 0 ,str.length()- 1 )); } } /* Driver program to test above function */ public static void main(String[] args) { String str = "Beginner for Beginner" ; StringReverse obj = new StringReverse(); obj.reverse(str); } } |
Python
# Python program to reverse a string using recursion # Function to print reverse of the passed string def reverse(string): if len (string) = = 0 : return temp = string[ 0 ] reverse(string[ 1 :]) print (temp, end = '') # Driver program to test above function string = "Beginner for Beginner" reverse(string) # A single line statement to reverse string in python # string[::-1] # This code is contributed by Bhavya Jain |
C#
// C# program to reverse // a string using recursion using System; class GFG { // Function to print reverse // of the passed string static void reverse(String str) { if ((str == null ) || (str.Length <= 1)) Console.Write(str); else { Console.Write(str[str.Length-1]); reverse(str.Substring(0,(str.Length-1))); } } // Driver Code public static void Main() { String str = "Beginner for Beginner" ; reverse(str); } } // This code is contributed by Sam007 |
Javascript
<script> // JavaScript Program for the above approach /* Function to print reverse of the passed string */ function reverse(str, len) { if (len == str.length) { return ; } reverse(str, len + 1); document.write(str[len]); } /* Driver program to test above function */ let a = "Beginner for Beginner" ; reverse(a, 0); // This code is contributed by Potta Lokesh </script> |
PHP
<?php // PHP program to reverse // a string using recursion // Function to print reverse // of the passed string function reverse( $str ) { if (( $str == null) || ( strlen ( $str ) <= 1)) echo ( $str ); else { echo ( $str [ strlen ( $str ) - 1]); reverse( substr ( $str , 0, ( strlen ( $str ) - 1))); } } // Driver Code $str = "Beginner for Beginner" ; reverse( $str ); // This code is contributed by // Manish Shaw(manishshaw1) ?> |
Output:
skeeG rof skeeG
Explanation: Recursive function (reverse) takes string pointer (str) as input and calls itself with next location to passed pointer (str+1). Recursion continues this way when the pointer reaches ‘\0’, all functions accumulated in stack print char at passed location (str) and return one by one.
Time Complexity: O(n) where n is the length of string
See Reverse a string for other methods to reverse string.
Auxiliary Space: O(n)
Efficient Approach:
We can store each character in recursive stack and then can print while coming back as shown in the below code:
C++
// C++ program to reverse a string using recursion #include <bits/stdc++.h> using namespace std; /* Function to print reverse of the passed string */ void reverse( char *str, int index, int n) { if (index == n) // return if we reached at last index or at the end of the string { return ; } char temp = str[index]; // storing each character starting from index 0 in function call stack; reverse(str, index+1, n); // calling recursive function by increasing index everytime cout << temp; // printing each stored character while recurring back } /* Driver program to test above function */ int main() { char a[] = "Beginner for Beginner" ; int n = sizeof (a) / sizeof (a[0]); reverse(a, 0, n); return 0; } // This is code is contributed by anuragayu |
C
// C program to reverse a string using recursion #include <stdio.h> /* Function to print reverse of the passed string */ void reverse( char *str, int index, int n) { if (index == n) // return if we reached at last index or at the end of the string { return ; } char temp = str[index]; // storing each character starting from index 0 in function call stack; reverse(str, index+1, n); // calling recursive function by increasing index everytime printf ( "%c" , temp); // printing each stored character while recurring back } /* Driver program to test above function */ int main() { char a[] = "Beginner for Beginner" ; int n = sizeof (a) / sizeof (a[0]); reverse(a, 0, n); return 0; } // This is code is contributed by anuragayu |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { /* Function to print reverse of the passed string */ static void reverse( char [] str, int index, int n) { if (index == n) // return if we reached at last index or at the end of the string { return ; } char temp = str[index]; // storing each character starting from index 0 in function call stack; reverse(str, index + 1 , n); // calling recursive function by increasing index everytime System.out.print(temp); // printing each stored character while recurring back } public static void main(String[] args) { char a[] = "Beginner for Beginner" .toCharArray(); int n = a.length; reverse(a, 0 , n); } } // This code is contributed by aadityaburujwale. |
Python3
# Python3 program to reverse a string using recursion def reverse(string, index, n): if index = = n: # return if we reached at last index or at the end of the string return temp = string[index] # storing each character starting from index 0 in function call stack; reverse(string, index + 1 , n) # calling recursive function by increasing index everytime print (temp, end = "") # printing each stored character while recurring back # Driver code string = "Beginner for Beginner" n = len (string) reverse(string, 0 , n) # This code is contributed by Potta Lokesh |
C#
// Include namespace system using System; public class GFG { // Function to print reverse of the passed string public static void reverse( char [] str, int index, int n) { if (index == n) { // return if we reached at last index or at the end of the string return ; } var temp = str[index]; // storing each character starting from index 0 in function call stack; GFG.reverse(str, index + 1, n); // calling recursive function by increasing index everytime Console.Write(temp); } public static void Main(String[] args) { char [] a = "Beginner for Beginner" .ToCharArray(); var n = a.Length; GFG.reverse(a, 0, n); } } // This code is contributed by aadityaburujwale. |
Javascript
// JavaScript program to reverse a string using recursion function reverse(string, index, n) { if (index === n) { // return if we reached at last index or at the end of the string return ; } var temp = string[index]; // storing each character starting from index 0 in function call stack; reverse(string, index+1, n); // calling recursive function by increasing index everytime console.log(temp); // printing each stored character while recurring back } // Driver code var string = "Beginner for Beginner" ; var n = string.length; reverse(string, 0, n); // This code is contributed by pradeepkumarppk2003 |
Output:
skeeG rof skeeG
Time Complexity: O(n) where n is size of the string
Auxiliary Space: O(n) where n is the size of string, which will be used in the form of function call stack of recursion.
C++
#include <iostream> using namespace std; // Function to reverse a string using recursion string reverse(string str, int len) { if (len < 1) { return "" ; } // Base case if (len == 1) { return string(1, str[0]); } return str[len - 1] + reverse(str, len - 1); } int main() { string str = "Beginner for Beginner" ; cout << reverse(str, str.length()) << endl; return 0; } // This code is contributed by akshitaguprzj3 |
Java
import java.util.*; public class Main { // Function to reverse a string using recursion public static String reverse(String str, int len) { if (len < 1 ) { return "" ; } // Base case if (len == 1 ) { return String.valueOf(str.charAt( 0 )); } return str.charAt(len - 1 ) + reverse(str, len - 1 ); } public static void main(String[] args) { String str = "Beginner for Beginner" ; System.out.println(reverse(str, str.length())); } } |
Python3
def reverse(string, length): if length < 1 : return "" # Base case if length = = 1 : return string[ 0 ] return string[length - 1 ] + reverse(string, length - 1 ) if __name__ = = "__main__" : input_str = "Beginner for Beginner" print (reverse(input_str, len (input_str))) |
C#
using System; class Program { // Function to reverse a string using recursion static string Reverse( string str, int len) { // Base case: If the string length is less than 1, return an empty string if (len < 1) { return "" ; } // Base case: If the string has only one character, return that character as a string if (len == 1) { return str[0].ToString(); } // Recursive case: Concatenate the last character of the string with the reversed substring return str[len - 1] + Reverse(str, len - 1); } static void Main() { string str = "Beginner for Beginner" ; // Call the Reverse function and print the reversed string Console.WriteLine(Reverse(str, str.Length)); } } |
Javascript
// Javascript program to reverse string using recursion function reverse(str , len){ if (len < 1){ return } // base case if (len === 1){ return str[0] } return str[len-1] + reverse(str , len -1 ) } // Driver code let str = "Beginner for Beginner" console.log(reverse(str, str.length)) // This code is contributed by rithikpathak123 |
skeeg rof skeeG
Time Complexity: O(n) where n is size of the string
Auxiliary Space: O(n) where n is the size of string, which will be used in the form of function call stack of recursion.
Explanation: This problem can be expressed in terms of smaller instance of same subproblem.
str= “Beginner for Beginner”
reverse string of str = last character of str + reverse string of remaining str = “s” + reverse string of “Beginner for geek” = “skeeg rof skeeG”
Please suggest if someone has a better solution which is more efficient in terms of space and time.
This article is contributed by Anurag Mishra and Aarti_Rathi .
Contact Us