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.
1217 Answers
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 it through a debugger. All will become clear.
1Because this is recursive your output at each step would be something like this:
- "Hello" is entered. The method then calls itself with "ello" and will return the result + "H"
- "ello" is entered. The method calls itself with "llo" and will return the result + "e"
- "llo" is entered. The method calls itself with "lo" and will return the result + "l"
- "lo" is entered. The method calls itself with "o" and will return the result + "l"
- "o" is entered. The method will hit the if condition and return "o"
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"
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; }
}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) + HSecond
return reverse(llo) + eWhich 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"
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
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"); }
}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"
}}
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; }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.
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)); }
}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.
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);
}
