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

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

提问by binarycreations

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

我今天一直在搞递归。通常是一种未充分使用的编程技术。

I set out to recursively reverse a string. Here's 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?

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

采纳答案by Mehrdad Afshari

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

最好的方法是不使用递归。这些东西通常用于教学生递归概念，而不是实际的最佳实践。所以你这样做的方式很好。只是不要在 Java 中对现实世界的应用程序中的这些东西使用递归；)

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.charAt(0);
}

回答by mqp

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.

编辑：如果你明白我的意思，对字符数组进行操作并在递归链中传递一个“截止”长度可能更有效，而不是制作子字符串。然而，这并不值得吹毛求疵，因为它首先并不是一种非常有效的技术。

回答by Stephan202

As Mehrdadnoted, 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,

正如Mehrdad 所指出的，最好不要使用递归。但是，如果您确实使用它，则最好保留每次调用的第一个和最后一个字符，从而将递归调用的数量减半。那是，

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

这也处理空字符串的情况。也许传递具有适当容量的 StringBuilder 会加快速度，但这留给读者作为练习；)

回答by kdgregory

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

回答by Tom Hawtin - tackline

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.)

（未测试 - 这是 stackoverflow。）

String.concatinstead of +would improve performance at the expense of clarity.

String.concat而不是+会以牺牲清晰度为代价来提高性能。

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.

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

回答by ephemient

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

只是为了它，这里有一个尾递归方法使用StringBuilder（通常建议使用它而不是操纵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.

未经测试，我已经很多年没有接触过 Java，但这应该是正确的。

回答by Paul Sonier

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

回答by Adam Jaskiewicz

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.

这是未经测试的，完全是意识流。它可能在某处有一个 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);
  }

回答by Jim Ferrans

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

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

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

回答by JBoy

You can try with an external variable, and add 1 by 1 all chars:

您可以尝试使用外部变量，并将所有字符 1 x 1 添加：

    public static String back="";

public static String reverseString(String str){


    if(str.length()==0){

        return back;

    }else {

        back+=str.charAt(str.length()-1);

        lees(str.substring(0,str.length()-1));


        return back;

    }

}

}