Whats the best way to recursively reverse a string in Java?

Question

Hi, I have been messing around with recursion today. Often a programming technique that is not used enough.

So.. I set myself the task to recursively reverse a string, heres what I came up with :

//A method to reverse a string using recursion
    public String reverseString(String s){
        char c = s.charAt(s.length()-1);
        if(s.length() == 1) return Character.toString(c);   

        return c + reverseString(s.substring(0,s.length()-1));
    }

My question is there a better way in Java?

Thanks for the replies :-)

Answer 1

The best way is not to use recursion. These stuff are usually used to teach students the recursion concept, not actual best practices. So the way you're doing it is just fine. Just don't use recursion in Java for these kind of stuff in real world apps ;)

PS. Aside what I just said, I'd choose "" as the base case of my recursive function:

public String reverseString(String s){
    if (s.length() == 0) 
         return s;

    return reverseString(s.substring(1,s.length()-1)) + s.charAt(0);
}

Answer 2

That's definitely how I'd go about recursively reversing a string (although it might be nice to extend it to the case of an empty string in your condition.) I don't think there is any fundamentally better way.

EDIT: It may be more efficient to operate on a character array and pass a "cutoff" length down the chain of recursion, if you get my drift, rather than making substrings. However, this is not really worth nitpicking about, since it's not a terribly efficient technique in the first place.

Answer 3

As Mehrdad noted, it's best not to use recursion. If you do use it, though, you might as well keep both the first and last character each call, thus halving the number of recursive calls. That is,

public String reverseString(String s){
    int len = s.length();

    if (len <= 1) {
        return s;
    }

    char fst = s.charAt(0);
    char lst = s.charAt(len - 1);

    return lst + reverseString(s.substring(1, len - 2)) + fst;
}

This also handles the case of the empty string. Perhaps passing along a StringBuilder with the appropriate capacity would speed things up even more, but that's left as an exercise to the reader ;)

Answer 4

You capture the basic idea, but extracting the last character doesn't improve clarity. I'd prefer the following, others might not:

public class Foo
{
    public static void main(String[] argv) throws Exception
    {
        System.out.println(reverse("a"));
        System.out.println(reverse("ab"));
        System.out.println(reverse("abc"));
    }


    public final static String reverse(String s)
    {
        // oft-repeated call, so reduce clutter with var
        int length = s.length();

        if (length <= 1)
            return s;
        else
            return s.substring(length - 1) + reverse(s.substring(0, length - 1));
    }
}

Answer 5

You don't want to nest too deeply. Divide-and-conquer is the way to go. Also reduces total size of temporary strings and is amenable to parallelisation.

public static String reverseString(String str) {
    int len = str.length();
    return len<=1 ? str : (
        reverseString(str.substring(len/2))+
        reverseString(str.substring(0, len/2))
    );
}

(Not tested - this is stackoverflow.)

String.concat instead of + would improve performance at the expense of clarity.

Edit: Just for fun, a tail-recursion friendly version of the naive algorithm.

public static String reverseString(String str) {
    return reverseString("", str);
}
private static String reverseString(String reversed, String forward) {
    return forward.equals("") ? reversed : (
         reverseString(reversed+forward.charAt(0), forward.substring(1)) 
    );
}

Correct handling of surrogate pairs is left to the interested reader.

Answer 6

Just for the heck of it, here's a tail-recursive method using StringBuilder (which is generally recommended over manipulating Strings).

public String reverseString(String s_) {
    StringBuilder r = new StringBuilder();
    StringBuilder s = new StringBuilder(s_);
    r = reverseStringHelper(r, s);
    return r.toString();
}
private StringBuilder reverseStringHelper(StringBuilder r, StringBuilder s) {
    if (s.length() == 0)
        return r;
    else
        return reverseStringHelper(r.append(s.charAt(0)), s.deleteCharAt(0));
}

Untested, I haven't dealt with Java in many years, but this should be about right.

Answer 7

It depends on what you define as "better". :-) Seriously, though; your solution essentially uses the maximum depth of recursion; if stack size is of a concern for your definition of "better", then you'd be better off using something like this:

public String reverseString(String s) {
   if (s.length() == 1) return s;
   return reverseString(s.substring(s.length() / 2, s.length() -1) + reverseString(0, s.length() / 2);
}

Answer 8

If you're going to do this, you want to operate on a character array, because a String is immutable and you're going to be copying Strings all over the place if you do it that way.

This is untested and totally stream of consciousness. It probably has an OB1 somewhere. And very not-Java.

public String reverseString(String s)
  {
  char[] cstr = s.getChars();
  reverseCStr(cstr, 0, s.length - 1);

  return new String(cstr);
  }

/**
 * Reverse a character array in place.
 */
private void reverseCStr(char[] a, int s, int e)
  {
  // This is the middle of the array; we're done.
  if (e - s <= 1)
    return;

  char t = a[s];
  a[s] = a[e];
  a[e] = t;
  reverseCStr(a, s + 1, e - 1);
  }

Answer 9

If you're writing real code (not learning recursion), use StringBuilder's reverse() method. The Java Tutorial gives this example:

String palindrome = "Dot saw I was Tod";   
StringBuilder sb = new StringBuilder(palindrome);
sb.reverse();  // reverse it
System.out.println(sb);