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