2
public static void main(String args[]) {
    System.out.println(reverseString("His"));
}

public static String reverseString(String s) {
    if (s.length() <= 1) {
        return s;
    } else {
        char c = s.charAt(0);
        return reverseString(s.substring(1)) + c;
    }
}

Can someone explain me in details how this method works

Clayton Louden
  • 1,056
  • 2
  • 11
  • 28
Lexy Feito
  • 143
  • 1
  • 2
  • 9

5 Answers5

5

I think the best way to understand how these types of methods work is to go through them by hand once with a simple example. Let's take the string "abc" and consider what happens when we call

reverseString("abc")

On the first iteration, we consider the else block (since "abc".length() is not less than or equal to 1). The method returns

reverseString("abc".substring(1)) + "abc".charAt(0)

which is equivalent to

reverseString("bc") + 'a'

Now we must consider reverseString("bc"). Again, we find ourselves in the else block, the method will return

reverseString("bc".substring(1)) + "bc".charAt(0)

which is equivalent to

reverseString("c") + 'b'

Evidently, reverseString("c") is just "c" - so reverseString("bc") is "cb" which, by above, means that reverseString("abc") is "cb" + 'a' which gives us "cba", as expected.

To summarize, we are essentially doing something like this:

reverse("abc")
reverse("bc") + 'a'
reverse("c") + 'b' + 'a'
"cba"

With a 4 character string:

reverse("abcd")
reverse("bcd") + 'a'
reverse("cd") + 'b' + 'a'
reverse("d") + 'c' + 'b' + 'a'
"dcba"
arshajii
  • 127,459
  • 24
  • 238
  • 287
4

Suppose, you have a String "Hello" then it will perform the recursion over the string starting from left to right.

char c = s.charAt(0);

return reverseString(s.substring(1)) + c;

1) for H

c = 'H'

return reverseString("ELLO") + H

2) For E

c = 'E'

return reverseString("LLO") + E

3) for E

c = 'E'

return reverseString("LLO") + E

4) for L

c = 'L'

return reverseString("LO") + L

5) for L

c = 'L'

return reverseString("O") + L

6) Since, substring s<= 1

return S = 'O'

7) Now it will resume back the recursive functions from bottom to top and will concatenate all the string s at each level

So, O + L + L + E + H = "OLLEH"

BTW, In java, string reversal is a cakewalk using StringBuilder/StringBuffer. e.g. StringBuffer("Hello".toReverse()).toString();

If you are using single threaded and simpler applications, go with StringBuilder

For, concurrent complex applications go with StringBuffer, its Synchrinized.

Hope, it helps.

BenMorel
  • 34,448
  • 50
  • 182
  • 322
Pankaj Gadge
  • 2,748
  • 3
  • 18
  • 25
  • It really helps a lot, btw im reversing the string using recursion because i want to learn how recursion works but your explination was really good thank you – Lexy Feito Oct 15 '12 at 00:36
2

This is simple.

If your method is called with one char string, it returns the same string and stops. Otherwise it removes the first character to append in the last and call your same method with remaining characters.

Take you example of His

This will work like this.

  1. Since string length is 3 (>1), it takes H out of it to append in the last and calls reverse method with is.
  2. Since now string length is 2 (>1), it takes i out of it to append in the last and calls reverse method with s.
  3. Now string length is 1 so it will return s and recursion will stop.
  4. Finally its will start appending your character in LAST-IN-FIRST-OUT fashion of their occurance e.g. s+i+H
  5. This way it will return you the final output as siH.

Other way to explain:

   reverse("His" ) ->  reverse("is" )+H -> ( reverse("s" )+i)+H -> (s+i)+H ->siH

Hope this helps.

Yogendra Singh
  • 33,927
  • 6
  • 63
  • 73
2

Put some print statements in there to see when the reverseString method is being called with what arguments. Here's what you'll get:

his
is
s

So each time the function recurses, it chops off the first character with s.substring(1). Then it adds that chopped off first character to the end of the result of reversing that substring. Using the same above three calls, this looks like:

reverse(is) + h
reverse(s) + i
s

Notice the final case just returns the single letter "s". That's called the base case of the recursion, and every recursive function needs one to return a result.

If you substitute the result of reverse(x) into the above three calls, you get this:

si + h
s + i
s

So that's how it works. To reverse a string, you reverse letters [1-n], then add letter 0 to the end of that. The only exception is to reverse a one-letter string, which just returns that one-letter string itself.

Zach Musgrave
  • 1,012
  • 7
  • 7
0

Intresting function i have not done java in a few years but this shold be how it works.

Check to make sure what we are reversing is more than one character if its not than return it. Now what we do is we take the fist character and move it to the end of the string, and then we return the rest of the string infront of it.

I in the end the end the string your versering gets to be one character and the first if clausse caues the full string to be returned. :)

Now i am sure there are better ways of solving this function. I am sure java has a reverse string function if you have to make your own for some reason do something like this. also it may not work i did this from memeory and my java is rusty

`public static  String reverseString(String s){
    for(int x=s.length(); x>=0; x--) {
      s2 .= s.charAt(x);

    }
    return s2;`
WojonsTech
  • 1,277
  • 1
  • 13
  • 28