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

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

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

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

函数式编程更多的是关于“是什么”而不是“如何”。

语言实现者会找到一种方法来优化代码在底层的工作方式，如果我们不试图让它比它需要的更优化的话。递归也可以在支持尾部调用优化的语言中进行优化。

从程序员的角度来看，更重要的是可读性和可维护性，而不是首先进行优化。再次强调，“过早优化是万恶之源”。

从理论上讲，两者是一样的。 具有相同O()复杂度的递归和循环将以相同的理论速度工作，但当然，实际速度取决于语言、编译器和处理器。 数幂例可用O(ln(n))迭代编码:

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }

尾递归和循环一样快。许多函数式语言都实现了尾部递归。

这里大部分答案都是错误的。正确答案是视情况而定。例如，这里有两个遍历树的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，我可以大致达到与递归方法相同的效果。但至少在我的计算机上，访问堆内存的开销要大于递归调用的开销。

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

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

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

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

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