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

这里有一个例子，在Java中递归比循环运行得快。这是一个对两个数组执行冒泡排序的程序。recBubbleSort(....)方法使用递归对数组arr排序，bbSort(....)方法仅使用循环对数组narr排序。两个数组中的数据是相同的。

public class BBSort_App {
    public static void main(String args[]) {
        int[] arr = {231,414235,23,543,245,6,324,-32552,-4};

        long time = System.nanoTime();
        recBubbleSort(arr, arr.length-1, 0);
        time = System.nanoTime() - time;

        System.out.println("Time Elapsed: "+time+"nanos");
        disp(arr);

        int[] narr = {231,414235,23,543,245,6,324,-32552,-4};
    
        time = System.nanoTime();
        bbSort(narr);
        time = System.nanoTime()-time;
        System.out.println("Time Elapsed: "+time+"nanos");
        disp(narr);
    }

    static void disp(int[] origin) {
        System.out.print("[");
        for(int b: origin)
            System.out.print(b+", ");
        System.out.println("\b\b \b]");
    }
    static void recBubbleSort(int[] origin, int i, int j) {
        if(i>0)
            if(j!=i) {
                if(origin[i]<origin[j]) {
                    int temp = origin[i];
                    origin[i] = origin[j];
                    origin[j] = temp;
                }
                recBubbleSort(origin, i, j+1);
            }
            else
                recBubbleSort(origin, i-1, 0);
    }

    static void bbSort(int[] origin) {
        for(int out=origin.length-1;out>0;out--)
            for(int in=0;in<out;in++)
                if(origin[out]<origin[in]) {
                    int temp = origin[out];
                    origin[out] = origin[in];
                    origin[in] = temp;
                }
    }
}

即使运行该测试50次，也会得到几乎相同的结果:

对这个问题的回答是令人满意的，但没有简单的例子。有人能给出为什么这个递归更快的原因吗?

这取决于使用的语言。你写了'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.

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

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

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

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

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