递归函数中是否应使用StringBuilder？哪种实现更高效？

先直接给结论：要看你怎么用StringBuilder——用对了能大幅提升效率，用错了和直接拼接没差甚至更差。

先看你给出的代码1：

public String recursive(int n) { 
    String retStr = "s"; 
    if (n==0) { 
        return retStr; 
    } else { 
        return retStr + recursive(n-1); 
    } 
}

这个实现的问题很明显：Java的String是不可变的，每次执行retStr + recursive(n-1)时，都会把retStr和递归返回的字符串复制到一个新的String对象里再返回。当递归深度n很大时，会生成O(n)个临时String对象，这些对象很快就会变成垃圾，不仅占用内存，还会让GC频繁工作，性能会随着n的增大直线下降。

再来说StringBuilder的用法，你没写完代码2，我分两种常见情况拆解：

情况1：每次递归创建新的StringBuilder #

比如这种写法：

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

这种写法其实和代码1没本质区别——每次递归都会创建一个新的StringBuilder，append完之后又调用toString()生成新的String对象，临时对象的数量还是O(n)，甚至因为多了StringBuilder的创建和销毁开销，性能可能还不如代码1，完全没必要这么写。

情况2：传递同一个StringBuilder实例（正确姿势） #

真正能提升效率的写法是用一个辅助递归方法，把同一个StringBuilder实例传递进去，全程只在这个对象里拼接：

public String recursive(int n) {
    StringBuilder sb = new StringBuilder();
    helper(n, sb);
    return sb.toString();
}

private void helper(int n, StringBuilder sb) {
    sb.append("s");
    if (n == 0) {
        return;
    }
    helper(n-1, sb);
}

这种写法的优势在于：整个递归过程只创建了一个StringBuilder对象，所有的append操作都是在这个对象的内部数组里进行的（数组满了才会扩容，扩容也是低频率操作），不会产生任何临时String对象。当n很大的时候，这种写法的内存占用和执行速度都会比代码1好太多——你可以理解成把递归里的拼接变成了类似循环里的高效操作，完美发挥了StringBuilder的优势。

总结一下 #

• 如果你只是在递归里每次新建StringBuilder再拼接，那完全不值得，效率和直接字符串拼接差不多甚至更差；
• 但如果是通过辅助方法复用同一个StringBuilder实例，那这种优化非常值得，尤其是递归深度较大时，性能提升会很明显。

内容的提问来源于stack exchange，提问作者Zaya