Here is some Java code to reverse a string recursively.
Could someone provide an explanation of how it works?
public static String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
return reverse(str.substring(1)) + str.charAt(0);
}
I'm not understanding how this can possibly work.
The function takes the first character of a String - str.charAt(0) - puts it at the end and then calls itself - reverse() - on the remainder - str.substring(1), adding these two things together to get its result - reverse(str.substring(1)) + str.charAt(0)
When the passed in String is one character or less and so there will be no remainder left - when str.length() <= 1) - it stops calling itself recursively and just returns the String passed in.
So it runs as follows:
reverse("Hello")
(reverse("ello")) + "H"
((reverse("llo")) + "e") + "H"
(((reverse("lo")) + "l") + "e") + "H"
((((reverse("o")) + "l") + "l") + "e") + "H"
(((("o") + "l") + "l") + "e") + "H"
"olleH"
You need to remember that you won't have just one call - you'll have nested calls. So when the "most highly nested" call returns immediately (when it finds just "o"), the next level up will take str.charAt(0) - where str is "lo" at that point. So that will return "ol".
Then the next level will receive "ol", execute str.charAt(0) for its value of str (which is "llo"), returning "oll" to the next level out.
Then the next level will receive the "oll" from its recursive call, execute str.charAt(0) for its value of str (which is "ello"), returning "olle" to the next level out.
Then the final level will receive the "oll" from its recursive call, execute str.charAt(0) for its value of str (which is "hello"), returning "olleh" to the original caller.
It may make sense to think of the stack as you go:
// Most deeply nested call first...
reverse("o") -> returns "o"
reverse("lo") -> adds 'l', returns "ol"
reverse("llo") -> adds 'l', returns "oll"
reverse("ello") -> adds 'e', returns "olle"
reverse("hello") -> adds 'h', returns "olleh"
Run the code below - it prints:
Step 0: ello / H
Step 1: llo / e
Step 2: lo / l
Step 3: o / l
Step 3 returns: ol
Step 2 returns: oll
Step 1 returns: olle
Step 0 returns: olleH
Code:
public class Test {
private static int i = 0;
public static void main(String args[]) {
reverse("Hello");
}
public static String reverse(String str) {
int localI = i++;
if ((null == str) || (str.length() <= 1)) {
return str;
}
System.out.println("Step " + localI + ": " + str.substring(1) + " / " + str.charAt(0));
String reversed = reverse(str.substring(1)) + str.charAt(0);
System.out.println("Step " + localI + " returns: " + reversed);
return reversed;
}
}
Because this is recursive your output at each step would be something like this:
So now on to the results:
The total return value will give you the result of the recursive call's plus the first char
To the return from 5 will be: "o"
The return from 4 will be: "o" + "l"
The return from 3 will be: "ol" + "l"
The return from 2 will be: "oll" + "e"
The return from 1 will be: "olle" + "H"
This will give you the result of "olleH"
Inline sample;
public static String strrev(String str) {
return !str.equals("") ? strrev(str.substring(1)) + str.charAt(0) : str;
}
Take the string Hello and run it through recursively.
So the first call will return:
return reverse(ello) + H
Second
return reverse(llo) + e
Which will eventually return olleH
The call to the reverce(substring(1)) wil be performed before adding the charAt(0). since the call are nested, the reverse on the substring will then be called before adding the ex-second character (the new first character since this is the substring)
reverse ("ello") + "H" = "olleH"
--------^-------
reverse ("llo") + "e" = "olle"
---------^-----
reverse ("lo") + "l" = "oll"
--------^-----
reverse ("o") + "l" = "ol"
---------^----
"o" = "o"
run the following and you'll see what's going on:
public class RS {
public static String reverse(String str) {
System.out.println("--- reverse --- " + str);
if ((null == str) || (str.length() <= 1)) {
return str;
}
return add(reverse(str.substring(1)), charAt(str));
}
public static char charAt(String s) {
System.out.println("--- charAt --- " + s);
return s.charAt(0);
}
public static String add(String s, char c) {
System.out.println("--- add --- " + s + " - " + c);
return s + c;
}
public static void main(String[] args) {
System.out.println("start");
System.out.println("result: " + reverse("hello"));
System.out.println("end");
}
}
AFAIK, there 2 thing in every recursion function :
There is always a stop condition which is :
if ((null == str) || (str.length() <= 1)) { return str; }
Recursion use the stack memory which use LIFO mechanism that's why the revert happen.
Another Solutions for reversing a String in Java.
Convert you string into a char array using .toCharArray() function.
public static char[] reverse(char in[], int inLength, char out[],
int tractOut) {
if (inLength >= 0) {
out[tractOut] = in[inLength];
reverse(in, inLength - 1, out, tractOut + 1);
}
return null;
}
import java.util.*;
public class StringReverser
{
static Scanner keyboard = new Scanner(System.in);
public static String getReverser(String in, int i)
{
if (i < 0)
return "";
else
return in.charAt(i) + getReverser(in, i-1);
}
public static void main (String[] args)
{
int index = 0;
System.out.println("Enter a String");
String input = keyboard.nextLine();
System.out.println(getReverser(input, input.length()-1));
}
}
Best Solution what I found.
public class Manager
{
public static void main(String[] args)
{
System.out.println("Sameer after reverse : "
+ Manager.reverse("Sameer"));
System.out.println("Single Character a after reverse : "
+ Manager.reverse("a"));
System.out.println("Null Value after reverse : "
+ Manager.reverse(null));
System.out.println("Rahul after reverse : "
+ Manager.reverse("Rahul"));
}
public static String reverse(String args)
{
if(args == null || args.length() < 1
|| args.length() == 1)
{
return args;
}
else
{
return "" +
args.charAt(args.length()-1) +
reverse(args.substring(0, args.length()-1));
}
}
}
Output:C:\Users\admin\Desktop>java Manager Sameer after reverse : reemaS Single Character a after reverse : a Null Value after reverse : null Rahul after reverse : luhaR
public class ReverseString{
private static String reverse(String text, String reverseStr){
if(text == null || text.length() == 0){
return reverseStr;
}
return reverse(text.substring(1), text.charAt(0)+reverseStr);
}
public static void main(String [] args){
System.out.println(reverse("hello", "")); //output is "olleh"
}
}
class Test {
public static void main (String[] args){
String input = "hello";
System.out.println(reverse(input));
}
private static String reverse(String input) {
if(input.equals("") || input == null) {
return "";
}
return input.substring(input.length()-1) + reverse(input.substring(0, input.length()-1));
} }
Here is a sample code snippet, this might help you. Worked for me.
`public class reverseString {
public static void main(String[] args) {
// TODO Auto-generated method stub
String brr= "momo";
int n=brr.length()-1;
string_Finder(brr,n);
}
public static void string_Finder(String arr,int n) {
if(n==0) {
System.out.println(arr.charAt(0));
}else {
System.out.println(arr.charAt(n));
string_Finder(arr,n-1);
}
}
}`
import java.util.Scanner;
public class recursion{
public static void main (String []args){
Scanner scan = new Scanner(System.in);
System.out.print("Input: ");
String input = scan.nextLine();
System.out.print("Reversed: ");
System.out.println(reverseStringVariable(input));
}public static String reverseStringVariable(String s) {
String reverseStringVariable = "";
for (int i = s.length() - 1; i != -1; i--) {
reverseStringVariable += s.charAt(i);
}
return reverseStringVariable;
}
}
Try this:
public static String reverse(String str) {
return (str == null || str.length()==0) ? str : reverseString2(str.substring(1))+str.charAt(0);
}
