CODEWITHSUNDEEP
javastringrecursionmethodssubstring
Michael Martin
Michael Martin

Reputation: 61

Require assistance with String recursion in Java

I am just learning how to use recursion now and I'm having a bit of trouble understand exactly how the following code is working: 

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

The goal of my program is to write a recursive method which will accept a String as an argument and return the reverse form of that String. I also know that this code DOES WORK.

I'm just a bit confused as to why it works. I was hoping someone who understands recursion and knows how to explain it! I understand how substring works and how the method is separating the first letter from the word (Ex. Mike ---> ike + M).

What I don't understand is how the base case ever reaches Zero and how the method returns the String in reverse order instead of just going through infinitely.

Any help would be greatly appreciated!

Upvotes: 2

Views: 82

Answers (3)

Reid Harrison
Reid Harrison

Reputation: 406

str.substring(1) will return a substring of the original, starting at the first index to the end of the string. So, for example:

"test".substring(1).equals("est") == true

So for every recursive call, the passed string will be once character shorter, eventually satisfying the terminating condition of a 0-length string.

What the code you have shown is doing is basically just appending the first character of the given string onto the end of the rest of the string (second character to last).

For recursive problems, try writing out the call stack with the explicit parameter values. Once you get to the final call of the stack, you will hit the terminating condition and the returned result will "bubble" back up the call stack.

Upvotes: 0

Malik Brahimi
Malik Brahimi

Reputation: 16711

Let's evaluate line by line:

1. reverseString(str.substring(1)) + str.charAt(0) // ______ + M
2. reverseString(str.substring(1)) + str.charAt(0) // ______ + i + M
3. reverseString(str.substring(1)) + str.charAt(0) // ______ + k + i + M
4. reverseString(str.substring(1)) + str.charAt(0) //      e + k + i + M

Upvotes: 0

pascalhein
pascalhein

Reputation: 5846

Each time the method is called with a shorter string: The first character is removed and appended afterwards.

The calls will proceed as follows (for you example "Mike"):

reverseString("Mike")
reverseString("ike") + 'M'
(reverseString("ke") + 'i') + 'M'
((reverseString("e") + 'k') + 'i') + 'M'
(((reverseString("") + 'e') + 'k') + 'i') + 'M'
((("" + 'e') + 'k') + 'i') + 'M' // base case is reduced: length is zero, therefore reverseString returns ""
(("e" + 'k') + 'i') + 'M'
("ek" + 'i') + 'M'
"eki" + 'M'
"ekiM"

In the first iteration, the string has length 4. Each time reverseString is executed, the length decreases so it will finish after a certain number of calls.

Upvotes: 5

Related Questions