Reverse String using Recursion
The recursive algorithm to reverse a string works by swapping the first and last characters until the middle of the string is reached. This process is performed through recursive calls, where in each call, characters at positions i
and n-i-1
are swapped, and i
is incremented. This continues until i
reaches n/2
, and the string is completely reversed.
- Define a recursive function that takes a string as input.
- If the string is empty or has only one character, return the string as it is the base case.
- Otherwise, call the function recursively with the substring excluding the first character.
- Append the first character to the result of the recursive call.
Below is the implementation of the above approach:
C++
// Recursive C++ program to reverse a string #include <bits/stdc++.h> using namespace std; // Recursive function to reverse the string void recursiveReverse(string &str, int i = 0) { int n = str.length(); if (i == n / 2) return ; // Swap the i and n-i-1 character swap(str[i], str[n - i - 1]); // Call Recursive function after incrementing i. recursiveReverse(str, i + 1); } // Driver program int main() { string str = "w3wiki" ; recursiveReverse(str); cout << str; return 0; } |
Java
// Recursive Java program to reverse a string import java.io.*; class GFG { // Recursive function to reverse the string static void recursiveReverse( char [] str, int i) { int n = str.length; if (i == n / 2 ) return ; // Swap the i and n-i-1 character swap(str,i,n - i - 1 ); // Call Recursive function after incrementing i. recursiveReverse(str, i + 1 ); } static void swap( char []arr, int i, int j) { char temp= arr[i]; arr[i]=arr[j]; arr[j]=temp; } // Driver program public static void main(String[] args) { char [] str = "w3wiki" .toCharArray(); recursiveReverse(str, 0 ); System.out.println(String.valueOf(str)); } } // This code is contributed by 29AjayKumar |
Python3
# Recursive Python program to reverse a string def recursiveReverse( str , i = 0 ): n = len ( str ) if i = = n / / 2 : return # Swap the i and n-i-1 character str [i], str [n - i - 1 ] = str [n - i - 1 ], str [i] # Call Recursive function after incrementing i. recursiveReverse( str , i + 1 ) if __name__ = = "__main__" : str = "w3wiki" # converting string to list # because strings do not support # item assignment str = list ( str ) recursiveReverse( str ) # converting list to string str = ''.join( str ) print ( str ) # This code is contributed by # sanjeev2552 |
C#
// Recursive C# program to reverse a string using System; public class GFG { static void recursiveReverse( char [] str, int i) { int n = str.Length; if (i == n / 2) return ; // Swap the i and n-i-1 character swap(str,i,n - i - 1); // Call Recursive function after incrementing i. recursiveReverse(str, i + 1); } static char [] swap( char []arr, int i, int j) { char temp= arr[i]; arr[i]=arr[j]; arr[j]=temp; return arr; } // Driver program public static void Main(String[] args) { char [] str = "w3wiki" .ToCharArray(); recursiveReverse(str,0); Console.WriteLine(String.Join( "" ,str)); } } // This code is contributed by Princi Singh |
Javascript
// Recursive JavaScript function to reverse a string function recursiveReverse(str, i = 0) { const n = str.length; if (i >= Math.floor(n / 2)) return str; // Swap the i and n-i-1 characters str = str.substring(0, i) + str[n - i - 1] + str.substring(i + 1, n - i - 1) + str[i] + str.substring(n - i); // Call Recursive function after incrementing i. return recursiveReverse(str, i + 1); } // Driver program let str = "w3wiki" ; str = recursiveReverse(str); console.log(str); |
PHP
<?php // A Simple PHP program // to reverse a string // Function to reverse a string function reverseStr( $str ) { // print the string // from last echo strrev ( $str ); } // Driver Code $str = "w3wiki" ; reverseStr( $str ); // This code is contributed // by Srathore ?> |
skeegrofskeeg
Time Complexity: O(n) where n is length of string
Auxiliary Space: O(n)
String Reverse in C/C++/Java/Python/JavaScript
String reverse or reverse a string means changing the position of each character of the given string to its opposite position from end, i.e. if a character is at position 1 then its new position will be String.length, similarly if a character is at position 2 then its new position will be String.length – 1, and so on.
Given a string, write a program to reverse the string.
Input: original_string[] = Geeks
Output: string_reversed[] = skeeGInput: original_string[] = w3wiki
Output: string_reversed[] = skeeGroFskeeG
Table of Content
- Reverse String using a Loop:
- Reverse String using inbuilt method
- Reverse String using Recursion:
- Reverse String using two pointers:
- String Reverse String using Stack: