CODEWITHSUNDEEP
javastringrecursion
user3287264
user3287264

Reputation:

Recursion- reversing String

I believe that I have a decent understanding of recursion (factorial etc), however in the following example in reversing a string I do not understand the line. Can someone please explain what it does?

return reverseString(str.substring(1)) + str.charAt(0);

Full Code from method:

public static String reverseString(String str){

            if(str.length()<2){
                System.out.println("reached Base case");
                return str;
            }

            return reverseString(str.substring(1)) + str.charAt(0);


            }

Upvotes: 1

Views: 172

Answers (6)

Vivin Paliath
Vivin Paliath

Reputation: 95518

Try to think of reversing a string in this manner:

//reverse of a string can be expressed as the last character 
//plus the reverse of everything remaining. For example, if we had
//"food", you would have "d" + reverse("foo"), which is "d" + "oof"
//which gives you "doof". So:

reverse(str)    = str[str.length - 1] + reverse(str[0:str.length - 2]);
reverse(str[0]) = str[0] //reverse of a 1 character string is the character itself

So apply this to the string abcd:

You have:

reverse("abcd") = "d" + reverse("abc")
reverse("abc")  = "c" + reverse("ab")
reverse("ab")   = "b" + reverse("a")
reverse("a")    = "a";

Now when you substitute you have:

reverse("ab")   = "b" + "a" = "ba"
reverse("abc")  = "c" + "ba" = "cba"
reverse("abcd") = "d" + "cba" = "dcba"

Think about how you can write code that mimics this behavior.

Upvotes: 0

Elliott Frisch
Elliott Frisch

Reputation: 201439

It inefficiently reverses the string by placing each successive sub-string on the stack until it reaches a length less then 2; it then reverses the characters by popping those results off the stack and appending the first character to the sub-string. It is inefficient because Java includes the StringBuilder class and that has a reverse method.

Upvotes: 0

Brian English
Brian English

Reputation: 466

Let's take this string:

str = "Reverse";

The value of str.substring(1) is "everse". The value of str.charAt(0) is "R".

I think you can take it from there if you understand recursion.

Upvotes: 0

exception1
exception1

Reputation: 1249

return reverseString(str.substring(1)) + str.charAt(0);

For example, the String is HelloWorld Then "HelloWorld".substring(1) returns "elloWorld" and "HelloWorld".charAt(0) returns "H"

You take the first letter and add it to the end od the string. But before, you do it again with the first part. In the end, this algorithm reverses the string.

Upvotes: 0

RacerNerd
RacerNerd

Reputation: 1579

It takes everything after the first character and calls the recursive function. The first character is put at the end of the string. This results in a reversal.

return reverse(Everything after the first) + the first

Upvotes: 0

rgettman
rgettman

Reputation: 178263

The call substring(1) takes the first character off of the string. That is fed into the recursive call, which reverse all but the last character. Then, the first character is appended, completing the reversal.

Example:

reverseString("abc") =>
reverseString("bc") + 'a' =>
(reverseString("c") + 'b') + 'a' =>
("c" + 'b') + 'a' =>
"cb" + 'a' =>
"cba"

Upvotes: 2

Related Questions