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

    returning boolean in a recursive method - binary search tree

    807606
      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
          796440
          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
            807606
            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
              796440
              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.

              The solution is forehead-smackingly simple. Think about it a bit.
              • 4. Re: returning boolean in a recursive method - binary search tree
                807606
                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
                  807606
                  btw i like the word automagically :D
                  • 6. Re: returning boolean in a recursive method - binary search tree
                    796440
                    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
                      807606
                      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.