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

Question

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

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

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

对比

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 个堆栈帧，可能会少很多。