Is it safe to catch StackOverflowError in Java?

Question

I have two different implementations of a function (eg. the size of the tree) one which is recursive and one which uses an explicit stack.

The recursive is very fast (probably because it does not need to allocate anything on the heap) but may cause a stack overflow on some "rare" inputs (in the example of tree, it would be on any unbalanced tree). The explicit version is slower but is unlikely to cause a stack overflow.

How safe is using the recursive implementation by default and recover from the StackOverflowError exception by executing the explicit one ?

Is it considered bad practice ?

Here is a small example of code:

interface Node {
  List<? extends Node> getSons();
}

static int sizeRec (Node root) {
  int result = 1;
  for (Node son : root.getSons()) {
    result += sizeRec(son);
  }
  return result;
}

static int sizeStack (Node root) {
  Stack<Node> stack = new Stack<Node>();
  stack.add(root);
  int size = 0;
  while (! stack.isEmpty()) {
    Node x = stack.pop();
    size ++;
    for (Node son : x.getSons()) {
       stack.push(son);
    }
  }
  return size;
}

static int size (Node root) {
  try {
    return sizeRec(root);
  } catch (StackOverflowError e) {
    return sizeStack(root);
  }
} 

Answer 1

I would suggest that in your sizeRecursive method you maintain a stack-depth counter and if you exceed a specified level switch to the sizeStackUsingHeap method. Do not rely on the StackOverflow Exception - this is bad practice. You should not use exceptions to define your algorithm.

interface Node {

    List<? extends Node> getSons();
}

// Switch to a heap stack if the stack ever hits this level.
private static final int STACKLIMIT = 1000;

private static int sizeRecursive(Node root) {
    // Start the stack depth at 0.
    return sizeRecursive(root, 0);
}

// Recursive implementation.
private static int sizeRecursive(Node root, int depth) {
    int result = 1;
    for (Node son : root.getSons()) {
        if (depth < STACKLIMIT) {
            result += sizeRecursive(son, depth + 1);
        } else {
            // Too deep - switch to heap.
            result += sizeUsingHeap(son);
        }
    }
    return result;
}

// Use this when the stack gets realy deep. It maintains the stack in the heap.
private static int sizeUsingHeap(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.add(root);
    int size = 0;
    while (!stack.isEmpty()) {
        // I am assuming this algorithm works.
        Node x = stack.pop();
        size++;
        for (Node son : x.getSons()) {
            stack.push(son);
        }
    }
    return size;
}

// Always use sizeRecursive to begin with.
public static int size(Node root) {
    return sizeRecursive(root);
}

Answer 2

Well, this is a matter of opinion. But, I don't believe you should ever do that. Firstly, your logic is twisting the meaning of exception handling (exceptions for "exceptions" not for logic), other programmers will have problems interpreting your code.

Besides that you should not catch "Erros" which indicate run-time problems on the environment. You should ask yourself if its worth it to forget a bit the good practices. Maybe, you could try to adjust the runtime configuration to fit the application or put extra verification logic...your call there..but as safety is regarded, you cannot actually say you are fine, as we don't how the stack state is now, and different JRE implementations may differ there..

Finally, for the question on the bottom: it is a bad practice and it is not safe.

A quote from https://softwareengineering.stackexchange.com/questions/209099/is-it-ever-okay-to-catch-stackoverflowerror-in-java:

surely there are situations where a stack overflow might leave an application inconsistent just like a memory exhaustion. Just imagine that some object is constructed and then initialized with the help of nested internal method calls - if one of them throws, the object may very well be in a state not supposed to be possible, just as if an allocation had failed. But that doesn't mean that your solution couldn't still be the best one

It has a reason to be called Error and not Exception...

From docs:

public abstract class VirtualMachineError extends Error: Thrown to indicate that the Java Virtual Machine is broken or has run out of resources necessary for it to continue operating

public class Error extends Throwable: An Error is a subclass of Throwable that indicates serious problems that a reasonable application should not try to catch. Most such errors are abnormal conditions. The ThreadDeath error, though a "normal" condition, is also a subclass of Error because most applications should not try to catch it. A method is not required to declare in its throws clause any subclasses of Error that might be thrown during the execution of the method but not caught, since these errors are abnormal conditions that should never occur. That is, Error and its subclasses are regarded as unchecked exceptions for the purposes of compile-time checking of exceptions.