关于内存使用的递归与迭代

Question

假设我有一个递归和迭代解决方案(使用堆栈)来解决某些问题,例如二叉树的预序遍历.对于当前的计算机,在内存方面,在迭代版本上使用递归解决方案是有优势的,反之亦然,对于非常大的树？

我知道对于某些子问题重复的递归解决方案,如果使用递归,则会有额外的时间和内存成本.假设这不是这种情况.例如,

preOrder(Node n){
    if (n == null) return;
    print(n);
    preOrder(n.left);
    preOrder(n.right);
}

VS

preOrder(Node n){
    stack s;
    s.push(n);
    while(!s.empty()){
        Node node = s.pop();
        print(node);
        s.push(node.right);
        s.push(node.left);
    }
}

Answer 1

如果存在堆栈溢出的风险(在这种情况下,因为树不能保证甚至是半平衡的),那么健壮的程序将避免递归并使用显式堆栈.

显式堆栈可以使用更少的内存,因为堆栈帧往往比维护递归调用的上下文所必需的更大.(例如,堆栈帧至少包含一个返回地址以及局部变量.)

但是,如果已知递归深度有限,则不必动态分配可以节省空间和时间,以及程序员时间.例如,走平衡二叉树只需要递归到树的深度,这是节点数的log ₂ ; 这不可能是一个非常大的数字.

正如评论员所建议的那样,一种可能的情况是已知该树是右倾的.在这种情况下,您可以递归左侧分支而不必担心堆栈溢出(只要您完全确定树是右倾斜的).由于第二个递归调用位于尾部位置,因此可以将其重写为循环:

void preOrder(Node n) {
    for (; n; n = n.right) {
        print(n);
        preOrder(n.left);
        n = n.right;
}

类似的技术通常(并且应该总是)应用于快速排序:在分区之后,该函数在较小的分区上进行递归,然后循环以处理较大的分区.由于较小的分区必须小于原始数组大小的一半,这将保证递归深度小于原始数组大小的log ₂,这肯定小于50个堆栈帧,并且可能少得多.