How does charAt reverse the input in this method?

Question

//method
public static String foo(String s)

{
if (s.length() == 1)

return s;

else

return foo(s.substring(1)) + s.charAt(0);
}

What does foo(“abcd”) evaluate to? It is is my understanding that this would reverse the input, but why is that?

Answer 1

It is a recursive reverse. s.substring(1) is the line without its first character; s.charAt(0) is the first character.

What the function is saying is "if the line is one character long, the answer is the line itself; otherwise, chop off the first character, compute the same function, and add the chopped off character to the end of the result".

You can work out on a piece of paper how performing the steps above amounts to reversing a string.

EDIT : It is worth noting that this implementation is going to crash with an exception if you try passing it an empty string. Changing if (s.length() == 1) to if (s.length() == 0) would address this problem (thanks to Tom Hawtin - tackline for mentioning this in a comment).

Answer 2

Hope this makes it clear how the recursion works in this case:

foo("bcd") + "a"
  (foo("cd") + "b") + "a"
    ((foo("d") + "c") + "b") + "a"
      (("d" + "c") + "b") + "a" -> "dcba"