从理论上讲，两者是一样的。 具有相同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;
  }

这取决于使用的语言。你写了'language-agnostic'，所以我会举一些例子。

在Java、C和Python中，与迭代相比，递归是相当昂贵的(通常)，因为它需要分配一个新的堆栈框架。在一些C编译器中，可以使用编译器标志来消除这种开销，它将某些类型的递归(实际上是某些类型的尾部调用)转换为跳转而不是函数调用。

In functional programming language implementations, sometimes, iteration can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.

我知道在某些Scheme实现中，递归通常比循环快。

简而言之，答案取决于代码和实现。你喜欢什么风格就用什么风格。如果使用函数式语言，递归可能更快。如果使用命令式语言，迭代可能更快。在某些环境中，这两种方法将生成相同的程序集(将其放入管道中并吸食)。

Addendum: In some environments, the best alternative is neither recursion nor iteration but instead higher order functions. These include "map", "filter", and "reduce" (which is also called "fold"). Not only are these the preferred style, not only are they often cleaner, but in some environments these functions are the first (or only) to get a boost from automatic parallelization — so they can be significantly faster than either iteration or recursion. Data Parallel Haskell is an example of such an environment.

列表推导式是另一种选择，但它们通常只是用于迭代、递归或更高阶函数的语法糖。

在任何现实的系统中，不，创建一个堆栈框架总是比创建INC和JMP更昂贵。这就是为什么真正好的编译器会自动将尾递归转换为对同一帧的调用，也就是说，没有开销，所以你会得到更可读的源版本和更有效的编译版本。一个非常非常好的编译器甚至应该能够在可能的情况下将普通的递归转换为尾部递归。

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

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

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

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

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

一般来说，不，在任何具有两种形式的可行实现的实际使用中，递归不会比循环快。我的意思是，当然，你可以编写出花费很长时间的循环，但是有更好的方法来实现相同的循环，可以通过递归来实现相同的问题。

关于原因，你一针见血;创建和销毁堆栈帧比简单的跳转代价更大。

但是，请注意我所说的“在两种形式中都有可行的实现”。对于像许多排序算法这样的事情，往往没有一种非常可行的方法来实现它们，因为它不能有效地建立自己的堆栈版本，因为生成子“任务”是这个过程固有的一部分。因此，递归可能和试图通过循环实现算法一样快。

编辑:这个答案是假设非函数式语言，其中大多数基本数据类型是可变的。它不适用于函数式语言。