stackoverflowerror на рекурсивном методе с массивом

Question

Я вижу исключение в потоке "main" java.lang.StackOverflowError.Я надеюсь узнать, что не так с кодом ниже.

public void addWord(String word){
    addWord(word,root,0);
}

private void addWord(String word,Node root,int pos)
{
    for(Node c:root.children)
    {
        if(word.charAt(pos)==c.letter)
        {
            addWord(word,c,pos++);
        }
    }
    Node temp = new Node();
    temp.letter=word.charAt(pos);
    temp.children=new ArrayList<Node>();
    root.children.add(temp);
    if(pos==word.length()-1)
    {
        temp.terminus=true;
        return;
    }
    if(pos<word.length()-1)
    {
        addWord(word,temp,pos++);
    }
}

Answer 1

По сути, переполнение стека происходит из-за того, что ваш метод продолжает вызываться рекурсивно и рекурсия никогда не заканчивается.

Одной из возможных проблем является этот вызов:

addWord(word,temp,pos++);

Это эквивалентно

addWord(word,temp,pos);
pos = pos + 1;

Вы, вероятно, имеете в виду:

addWord(word,temp,++pos);

, что эквивалентно

pos = pos + 1;
addWord(word,temp,pos);

Answer 2

Я написал более простую версию addWord():

private void addWord(String word, Node aRoot, int pos) {

    if (pos == word.length())
        return;

    for (Node c : aRoot.children) {
        if (word.charAt(pos) == c.letter) {
            addWord(word, c, pos+1);
            return;
        }
    }

    Node temp = new Node();
    temp.letter = word.charAt(pos);
    temp.children = new ArrayList<Node>();
    temp.terminus = pos == word.length() - 1;

    aRoot.children.add(temp);
    addWord(word, temp, pos+1);

}

Исходная версия в вашем коде имела несколько проблем с базовыми сценариями и с рекурсивными вызовами.Как правило, вам следует избегать изменения значений параметров метода (часть pos++).

Я предполагаю, что вы создаете структуру данных Trie , а яожидайте, что у вас будут проблемы с этим атрибутом terminus.Подумайте об этом, если вы добавите несколько слов с общими префиксами, какой будет конечный узел?Вы намерены добавить несколько узлов с одинаковым letter на одном уровне или хотите совместно использовать узлы на одном уровне с одной и той же буквой?в последнем случае какое значение будет иметь атрибут terminus?

Чтобы прояснить мою точку зрения, нарисуйте диаграмму, показывающую, как бы вы хотели, чтобы ваш Trie выглядел после выполнения следующего кода (оплатаобратите внимание на значение terminus в каждом узле) и посмотрите, дает ли приведенная выше реализация ожидаемый результат.

Test t = new Test();
t.addWord("a");
t.addWord("abc");
t.addWord("ab");