How does this code work? (Java recursion)

Question

Why does this code work?

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

And this doesn't?:

public static String reverse(String a) {
            if(a.length() == 0) {
                return a;
            } else {
                return reverse(a.substring(1)) + a.substring(0);
            }
        }

Also, how does the recursion work in case 1, what does adding a.charAt(0) do? And how does this method ever reach the base case?

**Read the documentation**, i.e. the javadoc of [`substring(int beginIndex)`](https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#substring-int-): *Returns a string that is a substring of this string. The substring begins with the character at the specified index and **extends to the end of this string**.*. — Andreas, Oct 30 '17 at 03:03
You could also have tried **debugging** the code to see what happens. It would very quickly have shown you why. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, Oct 30 '17 at 03:05
Play computer with pencil and paper-most effective way to grok recursion forever. — Dave Newton, Oct 30 '17 at 04:29

score 5 · Accepted Answer · answered Oct 30 '17 at 03:02

Because a.charAt(0) returns the first character, while a.substring(0) returns the entire String (from index 0). Change

 return reverse(a.substring(1)) + a.substring(0);

to something like

 return reverse(a.substring(1)) + a.substring(0, 1);

And it will work as expected.

score 1 · Answer 2 · answered Oct 30 '17 at 03:43

To get better understanding about recursive code, you can try to print the state for each method calls, e.g.

public static String reverse(String a) {
    System.out.println("Calling reverse(\"" + a + "\")");
    if(a.length() == 0) {
        System.out.println("Base case encountered for string : \"" + a + "\"");
        return a;
    } else {
        String b = reverse(a.substring(1));
        String c = a.charAt(0);
        System.out.println(reverse(\"" + a + "\") returning \"" + b + "\" + \"" + c + "\"");
        return b + c;
    }
}

When you try to call reverse("xyz"), then you can see the following text printed within standard output:

Calling reverse("xyz")
Calling reverse("yz")
Calling reverse("z")
Calling reverse("")
Base case encountered for string : ""
reverse("z") returning "" + "z" = "z"
reverse("yz") returning "z" + "y" = "zy"
reverse("xyz") returning "zy" + "x" = "zyx"

We can see several things:

You reduce the string recursively until reaching the base case where the string is empty (has zero length).
For each non base case, you split the string into two segment, namely b and c. Then you return reverse(b) + c.

SazzadSH · Answer 3 · 2017-10-30T12:55:40.480

Firstly, 'a.substring()' returns the substring starting from the index given as parameter, so while using 'a.substring(1)' as the parameter of the recursive method the first character always gets skipped and the length of the string given as parameter decreases gradually. Once no character remains it reaches the base case.

Secondly, 'a.charAt()' returns the character exists at the index of the string given as parameter. So 'a.charAt(0)' returns the first index of the string 'a' which is given as the parameter of the recursive method.

Finally, the first code works because each time it sends the entire string except the first character and it includes that first character at the end of the string that is returned reversed. So at the end, the entire string gets reversed. On the other hand, the second code includes the entire substring starting from the first index of the string given as its parameter instead of the first character.

To make the code work you can either use 'charAt(0)' like the first code -

return reverse(a.substring(1)) + a.charAt(0);

or you can use 'a.substring(0, 1)' which considers only the first character as the substring and returns it -

return reverse(a.substring(1)) + a.substring(0, 1);

How does this code work? (Java recursion)

3 Answers3