Java not returning from inside a recursive if/else statement-CodePudding

I have an if/else statement that calls itself recursively to look up a value in a binary search tree.

  public BST<E> lookup(BST T, Comparable data) {
 
    
    if (T.getData() == null) {
      return null;
    }
    else if (T.getData().equals(data)) {
      return T;
    }
    else {
      if (data.compareTo(T.getData()) < 0) {
        T = T.getLeft();
        lookup(T, data);
      }
      else {
        T = T.getRight();
        lookup(T.getRight(), T.getData());
      }
    } 
  
  }

When I try to compile the program, it gets upset that there isn't a return statement at the end. The program should eventually hit a return statement, but to make it compile I added a return statement at the end. But then the program always returns from that statement - even when it's in the else-if statement that says to return T. I know that it reaches that statement, but I don't know why it doesn't return from within that statement.

CodePudding user response：

The method doesn't hit return at all. Recursion isn't magical.

lookup(T.getRight(), T.getData()) means just that. It's no different just because it's your own method. Perhaps you think: Great, this will completely abort this method invocation and eliminate it from existence, restarting from the top, and IT now controls the returning of values.

Nope. Methods are reentrant: That just.. invokes a lookup method (which happens to be the same method, but that's irrelevant), will run it until it returns something, and then code jumps back to where you invoked lookup and continue on its merry way.

Hence why recursion that never ends results in StackoverflowErrors - the system is remembering all those lookup methods, as they are all still running (all of them, except for one, waiting for another lookup method to finish first, of course. It's not multiple threads, just multiple in-progress invocations).

Remember, no different from normal method invocations. If you write this code:

int foo() {
  return  scanner.nextInt();
}

Then, when the JVM executes this method, it'll then invoke the nextInt() method on the object that the scanner variable is pointing at, will wait for it to finish, and will then take what it returned and return, itself, using this value.

Recursion is no different.

I'm pretty sure all you want here is to return whatever your recursive call returns, so, all you need is to replace lookup(T, data) with `return lookup(T, data).

Note that your else class first replaces T with its right fork, and then again picks the right fork. I bet you didn't want that.

Also, naming a variable T is just about the worst possible imaginable name. Capital single letters are reserved for type params. The right naming convention for a method parameter isSomethingLikeThis (camelcase, where the first letter is lowercase).