Given a string, write a recursive program to reverse it
String Reverse
Reverse String using Stack:
The idea is to push all the characters of the string in a stack. Then pop the elements of the stack and store it in the initial string from the starting index. Since the stack is based on last in first out, so the string formed will be reverse of the original string.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void reversebyStack(string &str)
{
stack<char> st;
for (int i=0; i<str.length(); i++)
st.push(str[i]);
for (int i=0; i<str.length(); i++) {
str[i] = st.top();
st.pop();
}
}
int main()
{
string str = "geeksforgeeks";
reversebyStack(str);
cout << str;
return 0;
}
|
Java
import java.util.*;
class GFG
{
public static String reversebyStack(char []str)
{
Stack<Character> st = new Stack<>();
for(int i=0; i<str.length; i++)
st.push(str[i]);
for (int i=0; i<str.length; i++) {
str[i] = st.peek();
st.pop();
}
return String.valueOf(str);
}
public static void main(String []args)
{
String str = "geeksforgeeks";
str = reversebyStack(str.toCharArray());
System.out.println(str);
}
}
|
Python3
def reversebyStack(str):
stack = []
for i in range(len(str)):
stack.append(str[i])
for i in range(len(str)):
str[i] = stack.pop()
if __name__ == "__main__":
str = "geeksforgeeks"
str = list(str)
reversebyStack(str)
str = ''.join(str)
print(str)
|
C#
using System;
using System.Collections.Generic;
class GFG
{
public static String reversebyStack(char []str)
{
Stack<char> st = new Stack<char>();
for(int i = 0; i < str.Length; i++)
st.Push(str[i]);
for (int i = 0; i < str.Length; i++)
{
str[i] = st.Peek();
st.Pop();
}
return String.Join("",str);
}
public static void Main()
{
String str = "geeksforgeeks";
str = reversebyStack(str.ToCharArray());
Console.WriteLine(str);
}
}
|
Javascript
function reverseByStack(str) {
const stack = [];
for (let i = 0; i < str.length; i++) {
stack.push(str[i]);
}
let reversedStr = '';
while (stack.length > 0) {
reversedStr += stack.pop();
}
return reversedStr;
}
function main() {
let str = "geeksforgeeks";
let reversedStr = reverseByStack(str);
console.log(reversedStr);
}
main();
|
Time Complexity: O(n)
Auxiliary Space: O(n)
Reverse String using two pointers:
The idea is to use two pointers. The left pointer is placed at the beginning of the string and the right pointer is placed at the end of the string. Now swap the characters at left and right pointers, after that left pointer moves forward by 1 step and right pointer moves backward by 1 step. This operation is continued till right pointer is ahead of left pointer.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void reverseStr(string& str)
{
int n = str.length();
for (int i = 0, j = n - 1; i < j; i++, j--)
swap(str[i], str[j]);
}
int main()
{
string str = "geeksforgeeks";
reverseStr(str);
cout << str;
return 0;
}
|
Java
import java.io.*;
class GFG {
static void reverseStr(String str)
{
int n = str.length();
char []ch = str.toCharArray();
char temp;
for (int i=0, j=n-1; i<j; i++,j--)
{
temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
System.out.println(ch);
}
public static void main(String[] args) {
String str = "geeksforgeeks";
reverseStr(str);
}
}
|
Python3
def reverseStr(str):
n = len(str)
i, j = 0, n-1
while i < j:
str[i], str[j] = str[j], str[i]
i += 1
j -= 1
if __name__ == "__main__":
str = "geeksforgeeks"
str = list(str)
reverseStr(str)
str = ''.join(str)
print(str)
|
C#
using System;
class GFG
{
static void reverseStr(String str)
{
int n = str.Length;
char []ch = str.ToCharArray();
char temp;
for (int i=0, j=n-1; i<j; i++,j--)
{
temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
Console.WriteLine(ch);
}
public static void Main(String[] args)
{
String str = "geeksforgeeks";
reverseStr(str);
}
}
|
Javascript
<script>
function reverseStr(str)
{
let n = str.length;
let ch = str.split("");
let temp;
for (let i=0, j=n-1; i<j; i++,j--)
{
temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
document.write(ch.join("")+"<br>");
}
let str = "geeksforgeeks";
reverseStr(str);
</script>
|
PHP
<?php
function reverseStr (&$str)
{
$n = strlen($str);
for ($i = 0, $j = $n - 1;
$i < $j; $i++, $j--)
list($str[$i],
$str[$j]) = array($str[$j],
$str[$i]);
}
$str = "geeksforgeeks";
reverseStr($str);
echo $str;
?>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
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.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void recursiveReverse(string &str, int i = 0)
{
int n = str.length();
if (i == n / 2)
return;
swap(str[i], str[n - i - 1]);
recursiveReverse(str, i + 1);
}
int main()
{
string str = "geeksforgeeks";
recursiveReverse(str);
cout << str;
return 0;
}
|
Java
import java.io.*;
class GFG
{
static void recursiveReverse(char[] str, int i)
{
int n = str.length;
if (i == n / 2)
return;
swap(str,i,n - i - 1);
recursiveReverse(str, i + 1);
}
static void swap(char []arr, int i, int j)
{
char temp= arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String[] args)
{
char[] str = "geeksforgeeks".toCharArray();
recursiveReverse(str,0);
System.out.println(String.valueOf(str));
}
}
|
Python3
def recursiveReverse(str, i = 0):
n = len(str)
if i == n // 2:
return
str[i], str[n-i-1] = str[n-i-1], str[i]
recursiveReverse(str, i+1)
if __name__ == "__main__":
str = "geeksforgeeks"
str = list(str)
recursiveReverse(str)
str = ''.join(str)
print(str)
|
C#
using System;
public class GFG
{
static void recursiveReverse(char[] str, int i)
{
int n = str.Length;
if (i == n / 2)
return;
swap(str,i,n - i - 1);
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;
}
public static void Main(String[] args)
{
char[] str = "geeksforgeeks".ToCharArray();
recursiveReverse(str,0);
Console.WriteLine(String.Join("",str));
}
}
|
Javascript
function recursiveReverse(str, i = 0) {
const n = str.length;
if (i >= Math.floor(n / 2))
return str;
str = str.substring(0, i) + str[n - i - 1] + str.substring(i + 1, n - i - 1) + str[i] + str.substring(n - i);
return recursiveReverse(str, i + 1);
}
let str = "geeksforgeeks";
str = recursiveReverse(str);
console.log(str);
|
PHP
<?php
function reverseStr($str)
{
echo strrev($str);
}
$str = "geeksforgeeks";
reverseStr($str);
?>
|
Time Complexity: O(n) where n is length of string
Auxiliary Space: O(n)
Reverse String using inbuilt method
Below is the implementation to reverse a string using built-in methods in different programming languages:
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str = "geeksforgeeks";
reverse(str.begin(),str.end());
cout << str << std::endl;
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static void main (String[] args) {
String str = "geeksforgeeks";
StringBuffer sb = new StringBuffer(str);
sb.reverse();
System.out.println(sb.toString());
}
}
|
Python3
if __name__ == '__main__':
str = "geeksforgeeks"
sb = str[::-1]
print(sb)
|
C#
using System;
class Program {
static void Main(string[] args)
{
string str = "geeksforgeeks";
char[] charArray
= str.ToCharArray();
Array.Reverse(charArray);
str = new string(
charArray);
Console.WriteLine(
str);
}
}
|
Javascript
let str = "geeksforgeeks";
str = str.split('').reverse().join('');
console.log(str);
|
Time Complexity: O(n)
Auxiliary Space: O(1) in all the programming languages except Java in which it will be, O(n) (The extra space is used to store the StringBuffer string).
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!