Avoiding recursion!

[David Phluphy]

Hi! I've been struggling to avoid recursion in this method, but with no luck... Any ideas?
If you need a more detailed description of the problem, let me know, but the method is fully functional right now.. I just want to speed it up

public static FIList positions(String word, int index, Node rootNode){
		
		FIList positionList = new FIList();
		char charAtIndex = word.charAt(index);
		int lastCharIndexInWord = word.length()-1;

		if (charAtIndex == '?'){
			if (index == lastCharIndexInWord) {
				for(int i = 0; i < 26; i++){
					if (rootNode.children[i] != null)
						positionList.addAll(rootNode.children[i].positions);
				}
			}
			else{
				for(int i = 0; i < 26; i++){
					if (rootNode.children[i] != null)
						positionList.addAll(positions(word, index+1, rootNode.children[(i)]));
				}
			}
			return positionList;
		}//end if '?'

		Node nextNode = rootNode.children[(charAtIndex-97)];
		if (nextNode == null){
			return new FIList();
		}
		if (index == lastCharIndexInWord){
			return nextNode.positions;
		}
		return positions(word, index+1, nextNode);
	}

[Lester Burnham]

Avoiding recursion for the sake of avoiding recursion is not a good goal. Why do you think that's necessary? (And yes, a description of what the code is supposed to do would be rather helpful.)

[James Elsey]

What about merging those two for loops into one statement? It appears they do the same thing other than an extra arguement being passed to positionList. That would certainly cut down on a few lines of code and make it easier to read

[David Phluphy]

Lester Burnham wrote:Avoiding recursion for the sake of avoiding recursion is not a good goal. Why do you think that's necessary? (And yes, a description of what the code is supposed to do would be rather helpful.)

For speed, and for learning
The assignment was to solve it with recursion, but I thought I could do it without.. It's proving hard though, I've been working all day without really getting anywhere.

Assignment:
The method positions (word, index, node) must return the positions of all hits on "word" in the tree with root "node". "index" keeps track of where we are in "word".
To find these positions you can use recursion. A call the function itself is a recursive call. Recursion is usually used to divide a problem into smaller parts, then you assemble the solutions. When you see "?" call positions once for all possible replacements for "?".
This three is built from "ha ha mons har en hund med moms hun er en hunn"




Example output:
ha: 0 3
mjau: no such word
m?d: 23
e?: 15 36 39

[James Elsey]

Seems a little confusing on first read, but it appears that depending on a word passed in, you need to navigate down that tree structure, and obtain an output number if there is one.

Before you started coding, did you work it out all on paper etc?

Since you're dealing with chars, I would probably be tempted to have some switch statements. Try to split your code up into small chunks, so each method serves a particular purpose, and doesn't try to solve world hunger

[Campbell Ritchie]

And welcome to JavaRanch

[David Phluphy]

James Elsey wrote:Seems a little confusing on first read, but it appears that depending on a word passed in, you need to navigate down that tree structure, and obtain an output number if there is one.

Before you started coding, did you work it out all on paper etc?

Since you're dealing with chars, I would probably be tempted to have some switch statements. Try to split your code up into small chunks, so each method serves a particular purpose, and doesn't try to solve world hunger

Yea, I had to, or I wouldn't have managed to do it. I'm still confused as to how it's supposed to work myself, which is why I'm having trouble optimizing this. I don't see how a switch would help me, but I'll try some more today

@Campbell Ritchie
Thanks