小编Mar*_*arc的帖子

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

递归非常快(可能是因为它不需要在堆上分配任何东西)但可能会导致某些"罕见"输入上的堆栈溢出(在树的例子中,它将出现在任何不平衡的树上).显式版本较慢但不太可能导致堆栈溢出.

默认情况下使用递归实现是否安全,并通过执行显式实现从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) { …

这是一小段汇编代码(我使用gnu汇编程序的语法).

.extern cos
.section .data
pi: .double 3.14
.section .text
.global slowcos
.global fastcos

fastcos:
  fldl pi         
  subl $8, %esp   # makes some space for a double on the stack
  fstpl 0(%esp)   # copy pi on top of the stack
  call cos
  addl $8, %esp
  ret

slowcos:
  pushl pi+4      # push the last 4 bytes of pi on top of the stack
  pushl pi        # push the first 4 bytes of pi on top of the stack
  call cos
  addl …