什么是在Java中递归反转字符串的最佳方法？

Question

我今天一直在搞乱递归.通常编程技术不够用.

我开始以递归方式反转一个字符串.这是我想出的:

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

我的问题:Java有更好的方法吗？

Answer 1

最好的方法是不使用递归.这些东西通常用于教学生递归概念,而不是实际的最佳实践.所以你这样做的方式很好.只是不要在Java中使用递归来获取真实应用程序中的这些东西;)

PS.除了我刚才所说的,我选择""作为递归函数的基本情况:

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

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

Answer 2

如果您要这样做,您希望对字符数组进行操作,因为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);
  }

Answer 3

你不想深深地嵌套.分而治之是必须走的路.还减少了临时字符串的总大小,并且可以进行并行化.

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

(未测试 - 这是stackoverflow.)

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

代理对的正确处理留给感兴趣的读者.