7 Replies Latest reply: Mar 15, 2007 7:24 PM by 807606

# returning boolean in a recursive method - binary search tree

Ok, I know that this won't work as it is because java can't reason about the program properly and doesn't think that this will always return a boolean: it will though! This method is recursing through a binary search tree and it will always either find the "word" it is looking for, else cur will equal null. This means that the method will terminate and return a boolean. However java can't spot this and I wouldn't expect it to tbh. If anyone can think of a way to make this work, then please tell me :D

By the way this is my first post here, and I hope I can start to help others soon!
``````
/** Recursively searches the tree to see if the word is present */
private boolean presentRec(String word, HashTableNode cur) {
countNodes++; // increase the number of times a node has been compared
if (cur == null) {
// if we have reached the bottom of the tree and the word is not
// found then return false
return false;
} else if (cur.getWord().equals(word)) {
// if we have found the word, then it is in the dictionary so return
// true
return true;
} else if (cur.getWord().compareTo(word) < 0) {
// if the current node is less than the word, then go to the right
presentRec(word, cur.right);
} else {
// otherwise the current node must be greater than the word so we
// need to go to the left
presentRec(word, cur.left);
}
}``````
Message was edited by:
oliverj4455

Message was edited by:
oliverj4455
• ###### 1. Re: returning boolean in a recursive method - binary search tree
Ok, I know that this won't work as it is because java
can't reason about the program properly and doesn't
think that this will always return a boolean: it will
though!
No, it won't.

Your final else doesn't return anything.

Edit: Nor does the else if right before it.

Message was edited by:
jverd
• ###### 2. Re: returning boolean in a recursive method - binary search tree
Ok I know that, but my final else has a recursive call back to the same method, therefore it will actually always return something in the end, always! I just wanted to know if there was any way of telling java this :D or if there is any way of keeping track of the boolean somewhere then returning it right at the end or something. Btw. don't really want to use a global variable for this, but I suppose I could.
• ###### 3. Re: returning boolean in a recursive method - binary search tree
Ok I know that, but my final else has a recursive
call back to the same method, therefore it will
actually always return something in the end, always!
No, it won't.

Your else calls a method. That method returns something. Then you're back to right after invoking that method.
``````boolean foo(int x) {
if (x = 0) {
return 0;
}
else {
foo (x - 1);
// After foo(x - 1), we are here.  We don't automagically return
// what the previous method call returned. The fact
// that that method was also foo is irrelevant.
}
} ``````
The fact that that method happens to be the same method you're in now is irrelevant. The multiple recursive invocations are independent. The fact that a deeper call returns something doesn't automagically make all the prior invocations return that thing.

• ###### 4. Re: returning boolean in a recursive method - binary search tree
Ok I feel totally stupid, thanks for pointing that out for me :D. I just forgot that the return didn't just exit all the methods. For anyone who was interested here is my working code:
``````     /** Recursively searches the tree to see if the word is present */
private boolean presentRec(String word, HashTableNode cur) {
countNodes++; // increase the number of times a node has been compared
if (cur == null) {
// if we have reached the bottom of the tree and the word is not
// found then return false
return false;
} else if (cur.getWord().equals(word)) {
// if we have found the word, then it is in the dictionary so return
// true
return true;
} else if (cur.getWord().compareTo(word) < 0) {
// if the current node is less than the word, then go to the right
return presentRec(word, cur.right);
} else {
// otherwise the current node must be greater than the word so we
// need to go to the left
return presentRec(word, cur.left);
}
}``````
• ###### 5. Re: returning boolean in a recursive method - binary search tree
btw i like the word automagically :D
• ###### 6. Re: returning boolean in a recursive method - binary search tree
Good work!

On the lightbulb coming on, that is. I haven't actually read your code, so no comments there. :-)
• ###### 7. Re: returning boolean in a recursive method - binary search tree
I am writing a spell checking program, this is part of a hash table that contains the dictionary. Thought I would use a binary search tree because it is faster than an ordinary linked list for the bucket, well i have finished now, and it is quite efficient.