在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中有更好的方法吗？

- binarycreations

Answer 1

最好的方法是不使用递归。这些东西通常用于教授递归概念，而不是实际最佳实践。所以你现在的做法很好。只是不要在Java的真实应用中使用递归来处理这种类型的问题 ;)

另外，我会选择""作为我的递归函数的基本情况：

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

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

- Mehrdad Afshari

---

请纠正我，但我认为Mehrdad只是指像这样的琐碎情况。虽然递归解决方案实际上可能更容易考虑而不是迭代解决方案，但我认为它需要更多的“堆栈”来执行递归。在反转字符串的情况下，为什么要制作一个根本不需要递归解决方案呢？基本上，在绝对需要时才使用递归。 - FateNuller

这将需要一个大的堆栈。 - gurghet

Answer 2

如果您要执行此操作，建议使用字符数组进行操作，因为字符串是不可变的，如果您采用这种方式，将会在各个地方复制字符串。

以下内容未经测试，完全是心血来潮。它可能有一个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);
  }

- Adam Jaskiewicz

---

我知道C/C++使用字符字符串的方式，但我更感兴趣的是Java实现，不过我确实喜欢这种比较高效的方式。 - binarycreations

好的，这确实是用Java编写的。只是这不是一种Java-ish的做事方式。无论如何，我都不会在Java或C中递归地执行此操作，因此将C编写成Java并不觉得像应该感觉的那样错误。 - Adam Jaskiewicz

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

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

- Tom Hawtin - tackline

---

没有太大的区别...它仍然是O(n)操作（假设字符串连接作为O(1)操作）。它只是看起来更像MergeSort和其他东西，但实际上并不是。唯一的好处就是-正如你所描述的那样-递归树的深度。 - Mehrdad Afshari

字符串连接的时间复杂度为O(n)（当n足够大时）。 - Tom Hawtin - tackline

两者都会产生O(n)的临时字符串。 - Tom Hawtin - tackline

我明白如何使用分治法来减少递归树的深度，但是那种替代编写if语句的方式让我需要更加仔细地观察和集中注意力。哈哈 - binarycreations

第二种方法在reversed+forward.charAt(0)这一部分有错误，应该是forward.charAt(0) + reversed。然而，这样很容易导致OutOfMemoryError: Java heap space错误。 - jordom

Answer 4

这是我的递归反转函数，它能够正常工作。

public static String rev(String instr){
    if(instr.length()<=1){
        return instr;
    } else {
       return (instr.charAt(instr.length()-1)+rev(instr.substring(0,instr.length()-1)) );
    }       
}

- senthil

Answer 5

为了好玩，这里提供一个使用 StringBuilder 的尾递归方法（通常建议使用 StringBuilder 而不是操作 String）。

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了，但这应该是正确的。

- ephemient

---

我喜欢它，非常酷 :-) 当然，我们都可以懒惰地使用StringBuilder的反转方法，但那里有递归呢？！哈哈 - binarycreations

如果（常见的）StringBuilder使用off+len（或类似方法）而不仅仅是len，它会更有效。此外，我不明白你的返回值的意义所在。 - Tom Hawtin - tackline

@Tom：假装这些方法返回新对象而不是原地变异会让它感觉更加函数式 ;) - ephemient

Answer 6

如果你在写真正的代码（而不是学习递归），请使用StringBuilder的reverse()方法。Java教程给出了以下示例：

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

- Jim Ferrans

Answer 7

在Java中，由于String是不可变的，所以字符串连接比看起来更复杂。每次连接都会创建一个新的字符串，复制原始字符串的内容，导致线性复杂度O(n)，其中n是字符串的长度，因此对于m个这样的操作，它是O(m*n)，我们可以说它是二次复杂度O(n^2)。我们可以使用StringBuilder，每个append的复杂度为O(1)。下面是使用StringBuilder的递归程序。它只使用n/2个堆栈帧，因此它比正常的递归调用具有更少的空间复杂度，正常的递归调用将类似于s.charAt(s.length-1) + reverse(s.subString(0, s.length-2);

public class StringReverseRecursive {
    public static void main(String[] args) {
        String s = "lasrever gnirts fo noitatnemelpmi evisrucer a si sihT";
        StringBuilder sb = new StringBuilder(s);
        reverse(s, sb, 0, sb.length() - 1);
        System.out.println(sb.toString());
    }

    public static void reverse(String s, StringBuilder sb, int low, int high) {
        if (low > high)
            return;
        sb.setCharAt(low, s.charAt(high));
        sb.setCharAt(high, s.charAt(low));
        reverse(s, sb, ++low, --high);
    }
}

- Joe

Answer 8

这取决于你对“更好”的定义。 :-) 但是，严肃地说；你的解决方案基本上使用了递归的最大深度；如果堆栈大小是你对“更好”的定义的关注点，那么最好使用类似这样的东西：

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

- Paul Sonier

---

啊，我明白了。将问题基本上分成两半并对问题的每一半应用基本情况的方法是“从递归中获得最佳结果”的常见方式吗？ - binarycreations

就像我所说的那样，“更好”是如何定义的。这种方法并没有显著提高速度，但是使用此方法达到的最大递归深度（因此是最大堆栈）为log(s.length())，而使用原始建议的方法，您可以达到的最大递归深度为s.length()。这种做法将节省一点堆栈大小。 - Paul Sonier

看起来你的代码里有一个-1，缺少子字符串以及其他一些问题。而且对于空字符串也无法正常工作。 - Tom Hawtin - tackline

@tom：这只是伪代码。我没有为OP编写解决方案，只是提供建议并快速说明我的想法。 - Paul Sonier

Answer 9

这是我发现能够工作并使用递归的方法。您可以将 str.length() 作为 strLength 参数传递。

private static String reverse(String str, int strLength) {
    String result = "";
    if(strLength > 0)
        result = str.charAt(strLength - 1) + reverse(str, strLength - 1);
    return result;
}

- Randy Turner

Answer 10

public class StringUtility {

public static void main(String[] args) {
    StringUtility stringUtility = new StringUtility();

    String input = "santosh123";
    int middle = input.length() / 2;
    middle = middle - 1;
    System.out.println(stringUtility.stringReverse(input, middle));
}

public String stringReverse(String input, int middle) {

    if (middle == -1) {

        System.out.println("if");
        return input;

    } else {

        System.out.println("else");
        input = swapChar(input, middle);
        middle = middle - 1;
        return stringReverse(input, middle);

    }

}

private String swapChar(String input, int middle) {
    StringBuilder str = new StringBuilder(input);
    char begin = str.charAt(middle);
    int endIndex = input.length() - middle - 1;
    char end = str.charAt(endIndex);
    str.setCharAt(middle, end);
    str.setCharAt(endIndex, begin);
    System.out.println(str + "  " + middle + "  " + endIndex);
    return str.toString();
}

}

- Santosh