Что лучший способ состоит в том, чтобы рекурсивно инвертировать строку в Java?

Как заметил Мердад , лучше не использовать рекурсию. Однако, если вы все-таки используете его, вы можете сохранить как первый, так и последний символ при каждом вызове, тем самым уменьшив вдвое количество рекурсивных вызовов. То есть

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;
}

Это также обрабатывает регистр пустой строки. Возможно, передача StringBuilder с соответствующей емкостью ускорит процесс еще больше, но это оставлено как упражнение для читателя;)

Это определенно то, как я бы сделал рекурсивное реверсирование строка (хотя было бы неплохо расширить ее на случай пустой строки в вашем условии.) Я не думаю, что есть какой-либо принципиально лучший способ.

РЕДАКТИРОВАТЬ: Может быть более эффективно работать с массивом символов и передайте отрезок длины по цепочке рекурсии, если вы понимаете мой ход, вместо того, чтобы создавать подстроки. Тем не менее, не стоит придираться к этому вопросу, поскольку это не очень эффективный метод.

Вы уловили основную идею, но извлечение последнего символа не улучшает ясности. Я бы предпочел следующее, другие - нет:

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));
    }
}

Это зависит от того, что вы определяете как «лучше». :-) Если серьезно; ваше решение по существу использует максимальную глубину рекурсии; если размер стека имеет значение для вашего определения «лучше», тогда вам лучше использовать что-то вроде этого:

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);
}

На всякий случай вот хвостовой рекурсивный метод, использующий StringBuilder (который обычно рекомендуется вместо манипулирования String s).

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));
}

Не проверено, я не имел дела с Java много лет, но это должно быть примерно правильно.

Не стоит влезать слишком глубоко. Разделяй и властвуй - вот правильный путь. Также уменьшает общий размер временных строк и поддается распараллеливанию.

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))
    );
}

(Не тестировалось - это переполнение стека.)

String.concat вместо + улучшит производительность за счет ясности.

Изменить: просто для удовольствия, дружественная к хвостовой рекурсии версия наивного алгоритма.

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)) 
    );
}

Правильная обработка суррогатных пар оставлена ​​на усмотрение заинтересованного читателя.

Если вы собираетесь это сделать, вы хотите работать с массивом символов, потому что String неизменяем, и вы собираетесь копировать строки повсюду, если вы это сделаете таким образом.

Это непроверенный и полностью поток сознания. Наверное, где-то есть OB1. И очень не-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 <= 0)
    return;

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

Если вы пишете реальный код (не изучаете рекурсию), используйте метод reverse () StringBuilder. В Руководстве по Java приведен следующий пример:

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