java - 在 Java 中捕获 StackOverflowError 是否安全？

Question

我有两种不同的函数实现(例如树的大小)，一种是递归的，另一种是使用显式堆栈的。

递归非常快(可能是因为它不需要在堆上分配任何东西)但可能会导致一些“稀有”输入的堆栈溢出(在树的示例中，它会在任何不平衡的树上)。显式版本速度较慢，但​​不太可能导致堆栈溢出。

默认情况下使用递归实现并通过执行显式实现从 StackOverflowError 异常中恢复有多安全？

这被认为是不好的做法吗？

这是一个小代码示例:

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

我建议在您的 sizeRecursive 方法中维护一个堆栈深度计数器，如果您超过指定级别，请切换到 sizeStackUsingHeap 方法。不要依赖 StackOverflow 异常 - 这是不好的做法。您不应使用异常来定义您的算法。

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);
}