堆栈溢出的原因是什么？

Question

我正在用Java编写一个Android应用程序函数,该函数使用a 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这里不会花很长时间.每个递归调用都会推送一个新的堆栈帧.