我知道递归有时比循环要简洁得多，我不是在问什么时候应该用递归而不是迭代，我知道已经有很多关于这个的问题了。
我问的是，递归比循环快吗?在我看来，你总是能够细化一个循环，让它比递归函数执行得更快，因为循环是不存在的，不断地建立新的堆栈帧。
我特别在寻找在递归是正确处理数据的方法的应用程序中递归是否更快，例如在一些排序函数中，在二叉树中等等。
当前回答
尾递归和循环一样快。许多函数式语言都实现了尾部递归。
其他回答
这只是猜测。一般来说，如果两者都使用了非常好的算法(不考虑实现难度)，那么在规模相当大的问题上，递归可能不会经常击败循环，如果使用带有尾部调用递归的语言(以及带有循环的尾部递归算法，也是语言的一部分)，情况可能会有所不同——它们可能非常相似，甚至有时更喜欢递归。
一般来说，不，在任何具有两种形式的可行实现的实际使用中，递归不会比循环快。我的意思是，当然，你可以编写出花费很长时间的循环，但是有更好的方法来实现相同的循环，可以通过递归来实现相同的问题。
关于原因，你一针见血;创建和销毁堆栈帧比简单的跳转代价更大。
但是，请注意我所说的“在两种形式中都有可行的实现”。对于像许多排序算法这样的事情，往往没有一种非常可行的方法来实现它们，因为它不能有效地建立自己的堆栈版本，因为生成子“任务”是这个过程固有的一部分。因此，递归可能和试图通过循环实现算法一样快。
编辑:这个答案是假设非函数式语言，其中大多数基本数据类型是可变的。它不适用于函数式语言。
尾递归和循环一样快。许多函数式语言都实现了尾部递归。
考虑每个迭代和递归都必须做什么。
迭代:跳转到循环的开始 递归:跳转到被调用函数的开头
你看，这里没有多少分歧的余地。
(我假设递归是尾部调用，编译器知道这种优化)。
在任何现实的系统中，不，创建一个堆栈框架总是比创建INC和JMP更昂贵。这就是为什么真正好的编译器会自动将尾递归转换为对同一帧的调用，也就是说，没有开销，所以你会得到更可读的源版本和更有效的编译版本。一个非常非常好的编译器甚至应该能够在可能的情况下将普通的递归转换为尾部递归。
