递归比循环快吗?

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

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

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

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

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

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

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

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

在函数式编程语言实现中，有时迭代可能非常昂贵，而递归可能非常便宜。在许多情况下，递归被转换为简单的跳转，但改变循环变量有时(它是可变的)需要一些相对繁重的操作，特别是在支持多线程执行的实现上。在其中一些环境中，由于突变器和垃圾收集器之间的交互(如果两者可能同时运行)，突变的代价很高。

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

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

附录:在某些环境中，最好的替代方法既不是递归也不是迭代，而是高阶函数。其中包括“映射”、“过滤”和“减少”(也称为“折叠”)。这些不仅是首选的样式，而且通常更简洁，而且在某些环境中，这些函数是第一个(或唯一一个)从自动并行化中得到提升的——因此它们可以明显比迭代或递归更快。Data Parallel Haskell就是这种环境的一个例子。

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

这只是猜测。一般来说，在规模相当大的问题上，如果两者都使用非常好的算法(不考虑实现难度)，递归可能不会经常胜过循环，如果与带有尾部调用递归的语言(以及尾递归算法，并且循环也是语言的一部分)一起使用可能会有所不同——它们可能非常相似，甚至有时更喜欢递归。

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

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

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

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

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

递归在显式管理堆栈的情况下可能更快，就像你提到的排序或二叉树算法一样。

我曾经遇到过这样的情况，用Java重写递归算法会让它变慢。

因此，正确的方法是首先以最自然的方式编写它，只在分析显示它至关重要时进行优化，然后衡量假定的改进。

这里的大多数答案都忘记了一个明显的罪魁祸首，即为什么递归往往比迭代解慢。它与堆栈框架的建立和拆除相关联，但并不是完全那样。对于每次递归，auto变量的存储通常有很大的不同。在带有循环的迭代算法中，变量通常保存在寄存器中，即使溢出，它们也将驻留在1级缓存中。在递归算法中，变量的所有中间状态都存储在堆栈上，这意味着它们将生成更多的溢出到内存中。这意味着即使它执行相同数量的操作，在热循环中也会有大量的内存访问，更糟糕的是，这些内存操作的重用率很低，使得缓存的效率较低。

递归算法的缓存行为通常比迭代算法差。

递归比循环快吗?

< em >, < / em >迭代总是比递归快。(冯·诺依曼架构)

解释:

如果你从头开始构建一个通用计算机的最小操作，“迭代”首先作为一个构建块，比“递归”更少的资源密集型，因此更快。

从头开始建造一台伪计算机:

问题自己:你需要< em > < / em >计算一个值，即遵循一个算法并达到一个结果?

我们将建立一个概念层次结构，从头开始，首先定义基本的核心概念，然后用这些概念构建第二级概念，以此类推。

1. 第一个概念:内存单元，存储，状态。要执行某些操作，您需要places来存储最终结果值和中间结果值。让我们假设我们有一个无限的“整数”单元格数组，称为Memory， M[0.. infinite]。

2. 产品说明: do something - transform一个cell，改变它的值。改变状态。每个有趣的指令都执行一个转换。基本说明如下:

   一)设置,移动存储单元

   • 将一个值存储到内存中，例如:store 5 m[4]
   • 将一个值复制到另一个位置:例如:store m[4] m[8]

   b) 逻辑和算术

   • 或者xor，不是
   • 添加，sub, mul, div，例如add m[7] m[8]
   李< / ul > < / >

   • An execution Agent:现代CPU中core。“代理”是可以执行指令的东西。Agent也可以是在纸上遵循算法的人。

   • 步骤的顺序:一系列的指令:即:先做这个，后做这个，等等。指令的命令式序列。即使只有一行表达式是“指令的命令式序列”。如果你有一个具有特定“求值顺序”的表达式，那么你有< em > < / em >步骤。这意味着即使是单个组合表达式也有隐式的“步骤”和隐式的局部变量(让我们称之为“结果”)。例如:

     4 + 3 * 2 - 5
     (- (+ (* 3 2) 4 ) 5)
     (sub (add (mul 3 2) 4 ) 5)
     

     上面的表达式用一个隐式的“result”变量暗示了3个步骤。

     // pseudocode
     
     
     1. result = (mul 3 2)
     2. result = (add 4 result)
     3. result = (sub result 5)
     

     所以即使是中缀表达式，因为你有一个特定的求值顺序，也是指令的命令式序列。表达式意味着表示按特定顺序进行的一系列操作，并且由于存在步骤，因此还存在一个隐式的“result”中间变量

   • 指令指针:如果你有一个步骤序列，你还有一个隐式的“指令指针”。指令指针标记下一条指令，并在读取指令后执行指令之前前进。

     在这个伪计算机中，指令指针是内存的一部分。(注:通常指令指针将是CPU核心中的“特殊寄存器”，但在这里我们将简化概念，并假设所有数据(包括寄存器)都是“内存”的一部分)

   • Jump -一旦你有了有序的步数和指令指针，你可以应用"store"指令来改变指令指针本身的值。我们将把存储指令命名为跳转。我们使用一个新的名称，因为它更容易被认为是一个新的概念。通过改变指令指针，我们正在指示代理“转到步骤x”。

   • 无限迭代:通过< em >跳回来,< / em >现在你可以让代理“重复”一定数量的步骤。此时我们有无限迭代。

                        1. mov 1000 m[30]
     2. sub m[30] 1
     3. jmp-to 2  // infinite loop
     

   • Conditional - Conditional execution of instructions. With the "conditional" clause, you can conditionally execute one of several instructions based on the current state (which can be set with a previous instruction).

   • Proper Iteration: Now with the conditional clause, we can escape the infinite loop of the jump back instruction. We have now a conditional loop and then proper Iteration

     1. mov 1000 m[30]
     2. sub m[30] 1
     3. (if not-zero) jump 2  // jump only if the previous
     // sub instruction did not result in 0
     
     
     // this loop will be repeated 1000 times
     // here we have proper ***iteration***, a conditional loop.
     

   • Naming: giving names to a specific memory location holding data or holding a step. This is just a "convenience" to have. We do not add any new instructions by having the capacity to define “names” for memory locations. “Naming” is not a instruction for the agent, it’s just a convenience to us. Naming makes code (at this point) easier to read and easier to change.

        #define counter m[30]   // name a memory location
     mov 1000 counter
     loop:                      // name a instruction pointer location
     sub counter 1
     (if not-zero) jmp-to loop
     

   • One-level subroutine: Suppose there’s a series of steps you need to execute frequently. You can store the steps in a named position in memory and then jump to that position when you need to execute them (call). At the end of the sequence you'll need to return to the point of calling to continue execution. With this mechanism, you’re creating new instructions (subroutines) by composing core instructions.

     Implementation: (no new concepts required)

     • Store the current Instruction Pointer in a predefined memory position
     • jump to the subroutine
     • at the end of the subroutine, you retrieve the Instruction Pointer from the predefined memory location, effectively jumping back to the following instruction of the original call

     Problem with the one-level implementation: You cannot call another subroutine from a subroutine. If you do, you'll overwrite the returning address (global variable), so you cannot nest calls.

     To have a better Implementation for subroutines: You need a STACK

   • Stack: You define a memory space to work as a "stack", you can “push” values on the stack, and also “pop” the last “pushed” value. To implement a stack you'll need a Stack Pointer (similar to the Instruction Pointer) which points to the actual “head” of the stack. When you “push” a value, the stack pointer decrements and you store the value. When you “pop”, you get the value at the actual Stack Pointer and then the Stack Pointer is incremented.

   • Subroutines Now that we have a stack we can implement proper subroutines allowing nested calls. The implementation is similar, but instead of storing the Instruction Pointer in a predefined memory position, we "push" the value of the IP in the stack. At the end of the subroutine, we just “pop” the value from the stack, effectively jumping back to the instruction after the original call. This implementation, having a “stack” allows calling a subroutine from another subroutine. With this implementation we can create several levels of abstraction when defining new instructions as subroutines, by using core instructions or other subroutines as building blocks.

   • Recursion: What happens when a subroutine calls itself?. This is called "recursion".

     Problem: Overwriting the local intermediate results a subroutine can be storing in memory. Since you are calling/reusing the same steps, if the intermediate result are stored in predefined memory locations (global variables) they will be overwritten on the nested calls.

     Solution: To allow recursion, subroutines should store local intermediate results in the stack, therefore, on each recursive call (direct or indirect) the intermediate results are stored in different memory locations.

...

having reached recursion we stop here.

Conclusion:

In a Von Neumann Architecture, clearly "Iteration" is a simpler/basic concept than “Recursion". We have a form of "Iteration" at level 7, while "Recursion" is at level 14 of the concepts hierarchy.

Iteration will always be faster in machine code because it implies less instructions therefore less CPU cycles.

Which one is "better"?

• You should use "iteration" when you are processing simple, sequential data structures, and everywhere a “simple loop” will do.

• You should use "recursion" when you need to process a recursive data structure (I like to call them “Fractal Data Structures”), or when the recursive solution is clearly more “elegant”.

Advice: use the best tool for the job, but understand the inner workings of each tool in order to choose wisely.

Finally, note that you have plenty of opportunities to use recursion. You have Recursive Data Structures everywhere, you’re looking at one now: parts of the DOM supporting what you are reading are a RDS, a JSON expression is a RDS, the hierarchical file system in your computer is a RDS, i.e: you have a root directory, containing files and directories, every directory containing files and directories, every one of those directories containing files and directories...

这里的大多数答案都是错误的。正确答案是这取决于。例如，这里有两个遍历树的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需要一个CALL，然后需要另一个st_pop。

在前者中，每个节点只有递归CALL。

另外，访问调用堆栈上的变量非常快。这意味着您正在从内存中读取，而内存可能总是在最里面的缓存中。另一方面，显式堆栈必须由来自堆的malloc:ed内存支持，而这要慢得多。

通过仔细的优化，例如内联st_push和st_pop，我可以大致达到与递归方法相同的效果。但至少在我的计算机上，访问堆内存的开销要大于递归调用的开销。

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

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

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

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

这里有一个例子，在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;
}
}
}

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