Require assistance with String recursion in Java

Question

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!

add logs and use set-by-step debugger to see what comes in and out of the function — njzk2
– njzk2, Commented Feb 6, 2015 at 18:52
Try stepping through it. What happens to the input with every recursive call? — Platinum Azure
– Platinum Azure, Commented Feb 6, 2015 at 18:52
as a side note, if (str.length() == 0) could be if (str.length() == 1) — njzk2
– njzk2, Commented Feb 6, 2015 at 18:53

pascalh · Accepted Answer · 2015-02-06 18:54:22Z

5

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.

answered Feb 6, 2015 at 18:54

pascalh

5,8764 gold badges34 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Malik Brahimi · Accepted Answer · 2015-02-06 18:54:47Z

0

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

answered Feb 6, 2015 at 18:54

Malik Brahimi

16.8k7 gold badges46 silver badges76 bronze badges

Comments

Reid Harrison · Accepted Answer · 2015-02-06 18:57:23Z

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.

Collectives™ on Stack Overflow

Require assistance with String recursion in Java

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related