这里大部分答案都是错误的。正确答案是视情况而定。例如，这里有两个遍历树的C函数。首先是递归的:

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

下面是使用迭代实现的相同函数:

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}

理解代码的细节并不重要。p是节点，P_FOR_EACH_CHILD执行遍历。在迭代版本中，我们需要一个显式的堆栈st，其中节点被推入，然后弹出和操作。

递归函数比迭代函数运行得快得多。原因是在后者中，对于每一项，都需要调用函数st_push，然后调用函数st_pop。

在前者中，每个节点只有递归的CALL。

另外，访问调用堆栈上的变量非常快。这意味着您正在从内存中读取，而内存可能总是在最里面的缓存中。另一方面，显式堆栈必须由来自堆的malloc:ed内存支持，而这要慢得多。

通过仔细的优化，例如内联st_push和st_pop，我可以大致达到与递归方法相同的效果。但至少在我的计算机上，访问堆内存的开销要大于递归调用的开销。

但是这个讨论基本上是没有意义的，因为递归树遍历是不正确的。如果你有一个足够大的树，你会用完调用堆栈空间，这就是为什么必须使用迭代算法。

考虑每个迭代和递归都必须做什么。

迭代:跳转到循环的开始 递归:跳转到被调用函数的开头

你看，这里没有多少分歧的余地。

(我假设递归是尾部调用，编译器知道这种优化)。

这里大部分答案都是错误的。正确答案是视情况而定。例如，这里有两个遍历树的C函数。首先是递归的:

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

下面是使用迭代实现的相同函数:

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}

理解代码的细节并不重要。p是节点，P_FOR_EACH_CHILD执行遍历。在迭代版本中，我们需要一个显式的堆栈st，其中节点被推入，然后弹出和操作。

递归函数比迭代函数运行得快得多。原因是在后者中，对于每一项，都需要调用函数st_push，然后调用函数st_pop。

在前者中，每个节点只有递归的CALL。

另外，访问调用堆栈上的变量非常快。这意味着您正在从内存中读取，而内存可能总是在最里面的缓存中。另一方面，显式堆栈必须由来自堆的malloc:ed内存支持，而这要慢得多。

通过仔细的优化，例如内联st_push和st_pop，我可以大致达到与递归方法相同的效果。但至少在我的计算机上，访问堆内存的开销要大于递归调用的开销。

但是这个讨论基本上是没有意义的，因为递归树遍历是不正确的。如果你有一个足够大的树，你会用完调用堆栈空间，这就是为什么必须使用迭代算法。

这只是猜测。一般来说，如果两者都使用了非常好的算法(不考虑实现难度)，那么在规模相当大的问题上，递归可能不会经常击败循环，如果使用带有尾部调用递归的语言(以及带有循环的尾部递归算法，也是语言的一部分)，情况可能会有所不同——它们可能非常相似，甚至有时更喜欢递归。

Most answers here forget the obvious culprit why recursion is often slower than iterative solutions. It's linked with the build up and tear down of stack frames but is not exactly that. It's generally a big difference in the storage of the auto variable for each recursion. In an iterative algorithm with a loop, the variables are often held in registers and even if they spill, they will reside in the Level 1 cache. In a recursive algorithm, all intermediary states of the variable are stored on the stack, meaning they will generate many more spills to memory. This means that even if it makes the same amount of operations, it will have a lot memory accesses in the hot loop and what makes it worse, these memory operations have a lousy reuse rate making the caches less effective.

递归算法的缓存行为通常比迭代算法差。

递归在显式管理堆栈的情况下可能更快，就像你提到的排序或二叉树算法一样。

我曾经遇到过这样的情况，用Java重写递归算法会让它变慢。

因此，正确的方法是首先以最自然的方式编写它，只在分析显示它至关重要时进行优化，然后衡量假定的改进。