Java StackOverFlowError - Bad Recursive Call?

Question

I'm given a set of strings called "dictionary", stored as a field, which represents a dictionary of words.

I am to write a method which accepts a String parameter ("phrase") and returns a set containing all the words in the dictionary set that can be made from rearranging the characters in the given phrase. Basically I'm searching the dictionary for anagrams.

Here is my code:

public Set<String> getWords(String phrase) {
    Set<String> anagrams = new TreeSet<String>();
    String chosen = "";
    anagrams.addAll(getWords(phrase, chosen));
    return anagrams;
}

public Set<String> getWords(String phrase, String chosen) {
    if (phrase == null) {
        throw new IllegalArgumentException();
    } 
    Set<String> anagrams = new TreeSet<String>();
    if (dictionary.contains(chosen)) {
        anagrams.add(chosen);
        anagrams.addAll(getWords(phrase, chosen));
    } else {
        for (int i = 0; i < phrase.length(); i++) {
            String ch = phrase.substring(i, i + 1);         
            String temp = phrase.substring(0, i) + phrase.substring(i + 1);
            anagrams.addAll(getWords(temp, chosen + ch));
        }
    }
    return anagrams;
}

So my approach is to: 1. Check the dictionary for the possibility passed in this thread, represented by the variable "chosen."

If the dictionary does contain the possibility, add it to the set called "anagrams" which is returned at the end of the call. Then pass the possibility again to try to make other combinations out of it.

3.. If the dictionary does not contain the possibility, modify the string to try other possibilities, which are then tested recursively.

The code above produces a "stack overflow error", which my research indicates means I'm doing infinite recursion, or passing the same string over and over again infinitely. I can't see where I'm doing this, though. Can you?

It is recursive to have a StackOverFlowError on StackOverFlow, in a sense... — D.N.
– D.N., Commented Feb 22, 2011 at 1:32

Anon. · Accepted Answer · 2011-02-22 00:58:22Z

8

public Set<String> getWords(String phrase, String chosen) {
    //...
    if (dictionary.contains(chosen)) {
        anagrams.add(chosen);
        anagrams.addAll(getWords(phrase, chosen)); //<--here we are

You're making recursive call with exactly the same parameters. And you don't do anything that would make the condition return false next time.

answered Feb 22, 2011 at 0:58

Anon.

60.2k9 gold badges84 silver badges86 bronze badges

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

4 Comments

corsiKa Over a year ago

Don't sweat it man - we've all seen (and done) this and dumber, promise!

Captain Spectacular Over a year ago

So now I've gotten it to work, but my runtime is simply obscene, takes minutes to solve for a String more than five characters long. I take it I'm running a lot of unnecessary recursive calls?

Anon. Over a year ago

@Captain Spectacular: You probably are, yes. Personally, I wouldn't use recursion to solve this problem - generating all possible permutations is straightforward to do in an iterative manner.

Captain Spectacular Over a year ago

unfortunately i am required to use recursive backtracking for this method

Collectives™ on Stack Overflow

Java StackOverFlowError - Bad Recursive Call?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related