Adding values to ArrayList via recursion is erasing the list for every new value added?

Question

I am making a java Trie, which I have finally completed, but I'm adding the getWords() function which will return all of the values inside the Trie.

I'm having a problem with that function. Quick background info: Every character has an 'index' which is actually the entire word, including all the parent characters. When you enter the word "soup" the letter p has a value of isWord = true and index = "soup".

Also the 'children' variable you see is a HashMap and this function is inside the TrieNode class so keep that in mind.

The code giving me trouble:

private List<String> wordList = new ArrayList<String>();

public List<String> getWords(){

   /*Iterate through trie for every value in the hash map.
    Find all words with isWord= true and add that index to wordList
    */

   String word;
   for(Character key : children.keySet()){
       children.get(key).getWords();
       if(children.get(key).isWord == true){
           word = (children.get(key).index);
           wordList.add(word);
           System.out.println(wordList);  //prints list here for test
       }
   }
   System.out.println(wordList);  // prints again for test (second print)
   return wordList;
}

The first print statement prints out ONE word, the current word that the hash map was currently on when isWord was true. The next time it prints (when running recursively) it again prints only that one word.

IE: If you add two words to the trie "soup" and "hello" it would print: hello and soup on their own lines, but the wordList apparently loses the first word when printing the entire list the second time around.

I'm not sure why words are being lost out of the wordList. It should print: "hello" the first time and "hello soup" the second time should it not?

Once the function is done it returns wordList which is totally empty and has nothing in it.

EDIT:

Due to the confusion I'm adding a little visual here. (including all the code for the trie would be too unnecessary).

adding the words "hello" "hi" "soup" to the Trie

gives it the following Structure

The entire trie now has two key value pairs. H and S.

H is the key which contains a whole separate Trie inside of it. inside H are the nodes I and E (for hello and hi)

The S node has an O in it and the O has a U etc. etc.

The recursion is necessary because you may iterate through the hash maps keys and only get S and H. I need the keys of THOSE nodes as well so i do this recursively.

At the end of these prefixes will eventually be the words. Once I reach the word I want to add it to the wordList.

In the end I want to eventually return the wordList

What is that call to .getWords() at the start of each loop? — fge
– fge, Commented Jun 17, 2013 at 17:57
it is a call back into this same function. This is the getWords() function. — leigero
– leigero, Commented Jun 17, 2013 at 17:58
Yes but I mean, what is it used for? You ignore its return value — fge
– fge, Commented Jun 17, 2013 at 17:58
Well I have a Trie class, and a TrieNode class. (this is all part of the TrieNode). My intent was to call the getWords function from the Trie class and have it return the word list. But I need the getWords function to be recursive to get all the words, so i have the problem of ignoring the return value until the end. I'm not sure how to get around that. — leigero
– leigero, Commented Jun 17, 2013 at 18:00

laz · Accepted Answer · 2013-06-17 18:28:35Z

1

This isn't really recursion as you are calling getWords on a different instance of the object instead of this. In the comments, fge is correct in pointing out that the results are being ignored. You will essentially end up with separate lists at each level in the graph of objects where an object only has it's immediate descendant's words. One way to correct this is to create the List at the top level and pass it into the method getWords and have each element add its words to that List.

edited Jun 17, 2013 at 18:28

answered Jun 17, 2013 at 18:21

laz

28.7k6 gold badges56 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

leigero Over a year ago

Okay, I'd up-vote you a thousand times if I could. That was an easy fix thanks a ton!!

laz Over a year ago

The first call would pass in an newly created List, then subsequent calls would have access to that same list. The List is only created by the first caller.

Collectives™ on Stack Overflow

Adding values to ArrayList via recursion is erasing the list for every new value added?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related