应该在递归函数中使用 StringBuilder 吗？

Question

我理解 StringBuilder 的目的（通常）是避免在遍历字符串时在 Java 中反复创建对象，尤其是在循环中。

我想知道在 returns 一个字符串的递归函数中使用它是否值得。换句话说，以下哪个更有效？

public String recursive(int n) {
    String retStr = "s";    

    if (n==0) {
        return retStr;
    }
    else {
        return retStr + recursive(n-1);
    }
}

或

public String recursive(int n) {
    String retStr = "s";
    StringBuilder sb = new StringBuilder();


    if (n==0) {
        return retStr;
    }
    else {
        return sb.append(retStr).append(recursive(n-1)).toString();
    }
}

如果我不得不猜测，第一个似乎不那么复杂，因为无论哪种方式，您都必须每次都创建一个新对象，无论是 String 还是 StringBuilder，但是我可能是错的。

Answer 1

您可以将 StringBuilder 添加到递归方法中：

public String recursive(int n, StringBuilder sb) {
    String retStr = "s";
    if (n==0) {
        return retStr;
    }
    else {
        return sb.append(retStr).append(recursive(n-1, sb)).toString();
    }
}

并调用它

recursive(100, new StringBuilder());

Answer 2

如果您使用的是 java 8，

由于变量在范围内，我认为不需要 StringBuilder。

In summary, Java 8 seems not to introduce new optimizations for String concatenation with the + operator. It means that using StringBuilder manually is still required for specific cases where the compiler or the JIT is not applying magic tricks. For instance, when lot of substrings are concatenated to a String variable defined outside the scope of a loop.

更多内容见pellegrino

和dzone

Answer 3

User7294900 传递 StringBuilder 的想法很好，但他添加的太多了。

public String recursive (int n, StringBuilder sb) {
    String retStr = "s";
    if (n==0) {
        return sb.toString ();
    }
    else {
        return recursive (n-1, sb.append (retStr));
    }
}

而且 - 你应该看看这个，我不确定 - StringBuilder 没有接受提示，它会增长到多大？

recursive (100, new StringBuilder (101));

应该在递归函数中使用 StringBuilder 吗？

Should one use StringBuilder in a recursive function?

java

recursion

space-complexity