Breaking out of a recursion in java

Question

The recursion is sort of a 'divide and conquer' style, it splits up while getting smaller (Tree data structure), and I want it to break completely if a violation is found, meaning break all the recursive paths, and return true. Is this possible?

Answer 1

You could return an error code, or modify some global variable so that each recursive instance knows to "kill itself".

Something of the sort.

int foo(bar){
     int to_the_next;

      if (go_recursive){
            to_the_next = foo(whisky_bar);

            if (to_the_next ==DIE) return DIE;
      }

      if (something_unexpected_happened) return DIE;

      process;//may include some other recursive calls, etc etc
}

Answer 2

You can do something similar by storing a variable that tracks whether the recursions should break or not. You'd have to check it every recursion unfortunately but you can do it.

Answer 3

If it's a single thread doing the recursion you could throw an exception. Bit ugly though - kind of using an exception as a goto.

boolean myPublicWrapperMethod(...) {
    try {
        return myPrivateRecursiveFunction(...);
    } catch (MySpecificException e) {
        return true;
    } 
}

A better approach would be to eliminate the recursion and use a Stack collection holding a class representing what would have been recursive state, iterate in a loop and just return true when you want.

Answer 4

Unless recursive calls are being evaluated in parallel, you probably just need to add some logic to check the first recursive call's value prior to making the second (and subsequent, if not a binary tree structure) recursive call.

public abstract class Tree {

    protected abstract boolean headIsViolation();

    protected abstract boolean isLeaf();

    public Tree getLeft();

    public Tree getRight();

    // Recursive
    public boolean checkViolation() {
        if(this.isLeaf()) {
            return this.headIsViolation();
        }

        // If needed, you could pass some sort of 'calculation state'
        // object through the recursive calls and evaluate the violation
        // through that object if the current node is insufficient
        if(this.headIsViolation()) {
            // Terminate the recursion
            return true;
        }

        // Fortunately, Java short-circuits ||
        // So if the left child is in violation, the right child will
        // not even be checked
        return this.getLeft().checkViolation() || this.getRight().checkViolation();
    }
}

Answer 5

No matter what you do, you are going to have to unwind the stack. This leaves two options:

1. Magic return value (as described by one of the Toms)
2. Throw an exception (as mentioned by thaggie)

If the case where you want things to die is rare, this may be one of those situations where throwing an exception might be a viable choice. And before everyone jumps down my throat on this, remember that one of the most important rules of programming is knowing when it's appropriate to break the rule.

As it turns out, I spent today evaluating the zxing library from google code. They actually use exception throws for a lot of control structures. My first impression when I saw it was horror. They were literally calling methods tens of thousands of times with different parameters until the method doesn't throw an exception.

This certainly looked like a performance problem, so I made some adjustments to change things over to using a magic return value. And you know what? The code was 40% faster when running in a debugger. But when I switched to non-debugging, the code was less than 1% faster.

I'm still not crazy about the decision to use exceptions for flow control in this case (I mean, the exceptions get thrown all the time). But it's certainly not worth my time to re-implement it given the almost immeasurable performance difference.

If your condition that triggers death of the iteration is not a fundamental part of the algorithm, using an exception may make your code a lot cleaner. For me, the point where I'd make this decision is if the entire recursion needs to be unwound, then I'd use an exception. IF only part of the recursion needs to be unwound, use a magic return value.

Answer 6

What you are asking is the definition of recursion.

At some point all recursive paths should break. Otherwise it will be an infinite recursion and stack overflow exception occurs.

So you should design the recursion function like that. An example binary search in a sorted array:

BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
}

Answer 7

I'd recommend an exception handling. That makes clear, that the recursion was aborted because of some violation (or other exception):

public void outer() {
  try {
    int i = recurse(0);
  } catch (OuchException ouch) {
    // handle the exception here
  }
}

private int recurse(int i) throws OuchException {

    // for tree-like structures
    if (thisIsALeaf) {
       return i;
    }

    // the violation test
    if (itHurts)
       throw new OuchException("That really hurts");

    // we also can encapsulate other exceptions
    try {
       someMethod();
    } catch (Exception oops) {
       throw new OuchException(oops);
    }

    // recurse
    return recurse(i++);
}

Sure, it violates the initial requirement to return 'true' upon abortion. But I prefer a clean separation of return values and notification on abnormal behaviour.