java - 这个堆栈溢出的原因是什么？

Question

我正在用 Java 为 Android 应用程序编写一个函数，该应用程序使用 StringBuilder 生成字符串的所有排列。

每当函数运行时，程序立即终止，DDMS(Dalvic 虚拟机调试工具)声称我的函数发生堆栈溢出。

private void reorder(String reorder_this, StringBuilder in_this){

    for(int i = 0; i < reorder_this.length(); i++)
    {
        if(i == reorder_this.length())
        {
            in_this.append(System.getProperty("line.separator"));
        }
        else
        {
            in_this.append(reorder_this.charAt(i));
            reorder(reorder_this.substring(0, i) + reorder_this.substring(i), in_this);
        }
    }
}

你可以看到我对这个问题采用了递归方法，我相信这最终会用输入字符串的所有可能排列填充字符串生成器，每个排列后跟换行符。

有没有人知道可能导致堆栈溢出的原因？

Answer 1

简而言之，除非您的字符串长度为 0，否则您的函数无法终止。

您的方法首先将 i 设置为 0 并测试 i 是否小于您的第一个参数的长度。如果是(除了空字符串之外的所有字符串都是这种情况)，你会立即递归，因为你不能严格小于长度 和 等于长度。在您的递归调用中，您传入一个长度完全相同的字符串(实际上，正如 Thilo 指出的那样，是完全相同的字符串)。这表明该算法存在第二个问题:递归算法应该对每个递归调用的“较小”参数进行操作。

这里用不了多久就会得到一个StackOverflowException。每个递归调用都会推送一个新的堆栈框架。