关于内存使用的递归与迭代 [英] Recursion vs iteration with regards to memory usage

问题描述

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

Suppose I have a recursive as well as an iterative solution (using a stack) to some problem e.g. preorder traversal of a binary tree. With current computers, memory-wise, is there an advantage to using the recursive solution over the iterative version or vice versa for very large trees?

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

I'm aware that for certain recursive solutions where sub-problems repeat, there are additional time and memory costs if recursion is used. Assume that this is not the case here. For example,

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

推荐答案

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

If there is a risk of stack overflow (in this case, because the trees are not guaranteed to be even semi-balanced), then a robust program will avoid recursion and use an explicit stack.

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

The explicit stack may use less memory, because stack frames tend to be larger than is strictly necessary to maintain the context of recursive calls. (For example, the stack frame will contain at least a return address as well as the local variables.)

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

However, if the recursion depth is known to be limited, then not having to dynamically allocate can save space and time, as well as programmer time. For example, walking a balanced binary tree only requires recursion to the depth of the tree, which is log₂ of the number of nodes; that cannot be a very large number.

正如评论员所建议的，一种可能的情况是已知树是右倾斜的.在这种情况下，您可以向下递归左分支而不用担心堆栈溢出(只要您绝对确定树是右倾斜的).由于第二个递归调用在尾部位置，所以可以直接重写为循环:

As suggested by a commentator, one possible scenario is that the tree is known to be right-skewed. In that case, you can recurse down the left branches without worrying about stack overflow (as long as you are absolutely certain that the tree is right-skewed). Since the second recursive call is in the tail position, it can just be rewritten as a loop:

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

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

A similar technique is often (and should always be) applied to quicksort: after partitioning, the function recurses on the smaller partition, and then loops to handle the larger partition. Since the smaller partition must be less than half the size of the original array, that will guarantee the recursion depth to be less than log₂ of the original array size, which is certainly less than 50 stack frames, and probably a lot less.

这篇关于关于内存使用的递归与迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！