Что является причиной этого переполнения стека?

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 длины вашего первого аргумента. Если это так (что будет иметь место для всех, кроме пустых строк), вы немедленно вернетесь, потому что вы не можете быть строго меньше, чем длина и равна длине. В вашем рекурсивном вызове вы передаете строку точно такой же длины (в действительности, ту же самую точную строку, как указывает Тило). Это указывает на вторую проблему с алгоритмом: рекурсивные алгоритмы должны работать с «меньшими» аргументами для каждого рекурсивного вызова.

Это не займет много времени, чтобы получить StackOverflowException здесь. Каждый рекурсивный вызов добавляет новый кадр стека.

Answer 2

Причиной любого переполнения стека в Java является бесконечная рекурсия.

private void reorder(String reorder_this, StringBuilder in_this){
    for(int i = 0; i < reorder_this.length(); i++)
    {
        if(i == reorder_this.length())
        {

Этот блок недоступен по построению. Таким образом, ваше условие прекращения никогда не выполняется.

Answer 3

Я думаю, что проблема в этой строке:

reorder(reorder_this.substring(0, i) + reorder_this.substring(i), in_this);

reorder_this.substring(0, i) + reorder_this.substring(i) произведет строку, эквивалентную reorder-this