recursion比循环更快吗？
我知道recursion有时候比循环更清洁，而且我不会问什么时候应该使用recursion迭代，我知道还有很多问题。
我问的是，recursion比循环更快吗？ 对我来说，似乎总是可以改进一个循环，并使其比recursion函数更快地执行，因为循环没有经常设置新的堆栈帧。
我特别关注recursion是否是处理数据的正确方法，例如在二叉树中的某些sorting函数中，recursion是否更快。
这取决于正在使用的语言。 你写了'语言不可知'，所以我会举一些例子。
在Java，C和Python中，与迭代（通常）相比，recursion相当昂贵，因为它需要分配一个新的栈帧。 在一些C编译器中，可以使用编译器标志来消除这种开销，它将某些types的recursion（实际上，某些types的尾调用）转换为跳转而不是函数调用。
在函数式编程语言实现中，有时迭代可能非常昂贵，recursion可能非常便宜。 在许多情况下，recursion转化为简单的跳转，但是改变循环variables（这是可变的） 有时需要一些相对较重的操作，特别是在支持multithreading执行的实现上。 由于mutator和垃圾收集器之间的交互，如果两者都可能同时运行，那么在这些环境中的一些突变是昂贵的。
我知道在一些Scheme实现中，recursion通常比循环更快。
总之，答案取决于代码和实现。 使用任何你喜欢的风格。 如果您使用的是function语言，recursion可能会更快。 如果你使用命令式语言，迭代可能会更快。 在某些环境中，两种方法都会导致生成相同的程序集（将其放在pipe道中并冒烟）。
附录：在某些环境中，最好的select是既不是recursion也不是迭代，而是高阶函数。 这些包括“地图”，“filter”和“减less”（也被称为“折叠”）。 这不仅是首选的样式，它们不仅更清晰，而且在某些环境中，这些函数是自动并行化的第一个（或者是唯一的）推动力，因此它们可以比迭代或recursion快得多。 数据并行Haskell就是这样一个环境的一个例子。
列表推导是另一种select，但这些通常只是用于迭代，recursion或更高阶函数的语法糖。
recursion比循环更快吗？
不，迭代总是比recursion更快。 （在冯·诺依曼体系结构中）
说明：
如果从零开始构build通用计算机的最小操作，则“迭代”首先作为构build块，并且比“recursion”的资源密集度要低，但是ergo更快。
从头构build一个伪计算机器：
自问 ：你需要什么来计算一个值，即遵循一个algorithm，并达到一个结果？
我们将build立一个概念层次结构，从头开始，首先定义基本的核心概念，然后再build立二级概念，等等。
-
第一个概念： 内存单元，存储，状态 。 要做一些事情，你需要存储最终和中间结果值的地方。 假设我们有一个无限的“整数”单元arrays，称为存储器 ，M [0..Infinite]。
-
说明：做点什么 – 改造一个细胞，改变它的价值。 改变状态 。 每个有趣的指令都会进行转换。 基本说明是：
a） 设置并移动内存单元
- 将值存储到内存中，例如： store 5 m [4]
- 将一个值复制到另一个位置：例如： store m [4] m [8]
b） 逻辑和算术
- 和，或，异或，不
- 加，分，多，分。 例如添加m [7] m [8]
-
执行代理 ：现代CPU中的核心 。 “代理”是可以执行指令的东西。 代理人也可以是在纸上遵循algorithm的人。
-
步骤顺序：一系列的指令 ：即：先做这个，然后做这个，等等。一个命令的顺序。 即使是一行expression式也是“一个必要的指令序列”。 如果你有一个特定的“评估顺序”expression式，那么你有步骤 。 这意味着即使是一个单一的组合expression式都有隐含的“步骤”，也有一个隐式的局部variables（我们称之为“结果”）。 例如：
4 + 3 * 2 - 5 (- (+ (* 3 2) 4 ) 5) (sub (add (mul 3 2) 4 ) 5)上面的expression意味着隐含的“结果”variables的3个步骤。
// pseudocode 1. result = (mul 3 2) 2. result = (add 4 result) 3. result = (sub result 5)所以，即使中缀expression式，因为你有一个特定的评估顺序，是一个迫切的指令序列 。 expression式意味着要按特定顺序进行一系列操作，并且由于有步骤 ，所以还有一个隐含的“结果”中间variables。
-
指令指针 ：如果你有一系列的步骤，你也有一个隐含的“指令指针”。 指令指针标记下一条指令，并在指令读取之后但在指令执行之前前进。
在这个伪计算机中，指令指针是存储器的一部分。 （注意：通常指令指针是一个CPU内核中的“特殊寄存器”，但这里我们将简化这些概念并假定所有的数据（包括寄存器）都是“Memory”的一部分）
-
跳转 – 一旦你有一个有序的步数和一个指令指针 ，你可以应用“ 存储 ”指令来改变指令指针本身的值。 我们将用一个新的名称来调用这个存储指令的具体用法： 跳转 。 我们用一个新的名字，因为更容易把它看作一个新的概念。 通过更改指令指针，我们正在指示代理程序“转到步骤x”。
-
无限迭代 ：通过跳回来，现在可以让代理“重复”一定数量的步骤。 在这一点上，我们有无限的迭代。
1. mov 1000 m[30] 2. sub m[30] 1 3. jmp-to 2 // infinite loop -
有条件的 – 有条件地执行指令。 使用“条件”子句，可以根据当前状态（可以使用前面的指令设置）有条件地执行几条指令之一。
-
适当的迭代 ：现在使用条件子句，我们可以避开跳回指令的无限循环。 我们现在有一个条件循环 ，然后进行适当的迭代
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. -
命名 ：给名字保存数据或者保存一个步骤 。 这只是一个“方便”。 我们没有增加任何新的说明，因为有能力为内存位置定义“名称”。 “命名”不是代理人的指令，这只是给我们一个方便。 命名使代码（在这一点上）更容易阅读，更容易改变。
#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 -
一级子程序 ：假设你需要经常执行一系列步骤。 您可以将步骤存储在内存中的指定位置，然后在需要执行（呼叫）时跳转到该位置。 在序列结束时，您需要返回到调用点继续执行。 有了这个机制，你就可以通过编写核心指令来创build新的指令 （子程序）。
实施:(不需要新的概念）
- 将当前的指令存储在预定义的存储位置
- 跳转到子程序
- 在子程序结束时，您从预定义的内存位置检索指令指针，有效地跳回到原始调用的以下指令
单层实现的问题：不能从子例程中调用另一个子例程。 如果你这样做，你会覆盖返回的地址（全局variables），所以你不能嵌套调用。
为了更好的实现子程序：你需要一个堆栈
-
堆栈 ：你定义一个内存空间来作为一个“堆栈”，你可以在堆栈上“推”数值，也可以“popup”最后一个“推”数值。 要实现一个堆栈，你需要一个堆栈指针 （类似于指令指针），它指向堆栈的实际“头部”。 当您“推”一个值时，堆栈指针递减，并存储该值。 当你“popup”，你得到实际的堆栈指针的值，然后堆栈指针递增。
-
子程序现在我们有了一个堆栈，我们可以实现允许嵌套调用的正确的子程序。 实现是类似的，但是不是将指令指针存储在预定义的存储位置，而是将IP的值“推”到堆栈中 。 在子程序结束时，我们只是从堆栈中“popup”值，在原始调用之后有效地跳回到指令。 这个具有“堆栈”的实现允许从另一个子程序调用子程序。 通过这个实现，我们可以通过使用核心指令或其他子程序作为构build块来定义新的指令作为子程序时创build几个抽象层次。
-
recursion ：子程序自我调用时会发生什么？ 这被称为“recursion”。
问题：覆盖本地中间结果，子程序可以存储在内存中。 由于您正在调用/重复使用相同的步骤， 如果中间结果存储在预定义的内存位置（全局variables）中，它们将在嵌套调用上被覆盖。
解决scheme：为了允许recursion，子程序应该将本地中间结果存储在堆栈中 ，因此，在每次recursion调用 （直接或间接）时，中间结果都存储在不同的存储单元中。
…
已经达到recursion我们停在这里。
结论：
在冯·诺依曼架构中，显然“迭代”是比“recursion”更简单/基本的概念，我们在第7级有一个“迭代”的forms，而“recursion”在概念层次的第14级。
在机器代码中迭代总是会更快，因为它意味着更less的指令，因此CPU周期更less。
哪一个更好”？
-
当你处理简单的，顺序的数据结构时，你应该使用“迭代”，并且在任何地方都可以使用“简单循环”。
-
当需要处理recursion数据结构（我喜欢称之为“分形数据结构”）时，或者当recursion解决scheme明显更“优雅”时，应该使用“recursion”。
build议 ：使用最好的工具进行工作，但要明白每个工具的内部工作原理。
最后，请注意，您有很多使用recursion的机会。 您现在正在使用recursion数据结构 ，现在正在查看：支持您正在阅读的DOM的部分是RDS，JSONexpression式是RDS，计算机中的分层文件系统是RDS，即：包含文件和目录的根目录，包含文件和目录的每个目录，包含文件和目录的每个目录…
在替代方法是显式pipe理堆栈时，recursion可能会更快，就像您提到的sorting或二叉树algorithm一样。
我有一个情况，在Java中重写recursionalgorithm使其变慢。
所以正确的做法是首先以最自然的方式写出来，只有在剖析显示它很关键时才进行优化，然后测量所期望的改进。
考虑每个迭代和recursion必须完成的事情。
- 迭代：跳转到循环开始
- recursion：跳转到被调用函数的开始
你看，这里的差异没有太大的空间。
（我认为recursion是一个尾巴调用，编译器意识到这种优化）。
尾recursion和循环一样快。 许多函数式语言都在其中实现了尾recursion。
这里的大部分答案都是错误的 。 正确的答案是取决于 。 例如，这里有两个遍历树的C函数。 首先是recursion的：
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); } }); }
这里是使用迭代实现的相同function：
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节点按下，然后popup和操作。
recursion函数的运行速度比迭代函数快得多。 原因是在后者中，对于每个项目，都需要一个到函数st_push的CALL ，然后是另一个到st_pop 。
在前者中，每个节点只有recursionCALL 。
另外，在callstack上访问variables的速度非常快。 这意味着你正在从内存中读取，这可能总是在最内层的caching中。 另一方面，显式堆栈必须由堆中的malloc ：ed内存支持，访问速度要慢得多。
通过仔细优化，比如内联st_push和st_pop ，我可以达到与recursion方法大致相同的效果。 但至less在我的电脑上，访问堆内存的成本比recursion调用的成本要大。
但是这个讨论大多是没有意义的，因为recursion树行走是不正确的 。 如果你有足够大的树，你将用完堆栈空间，这就是为什么必须使用迭代algorithm。
这里的大多数答案都忘记了为什么recursion往往比迭代解决scheme慢的明显罪魁祸首。 它与堆栈框架的build立和拆卸有关，但并不完全一样。 对于每个recursion，自动variables的存储通常是一个很大的区别。 在使用循环的迭代algorithm中，variables通常保存在寄存器中，即使溢出，它们也会驻留在1级caching中。 在recursionalgorithm中，variables的所有中间状态都存储在堆栈中，这意味着它们会导致更多的溢出到内存中。 这意味着即使执行了相同的操作，在热循环中也会有大量的内存访问，而且更糟糕的是，这些内存操作的重用率很低，使得caching效率下降。
TL; DRrecursionalgorithm通常比迭代algorithm具有更差的caching行为。
在任何现实的系统中，不，创build堆栈框架总是比INC和JMP更昂贵。 这就是为什么真正优秀的编译器自动将尾recursion转换为对同一帧的调用，即没有开销，所以你得到更可读的源版本和更高效的编译版本。 一个真正好的编译器甚至可以把正常的recursion转换成可能的尾recursion。
函数式编程更多的是关于“ 什么 ”而不是“ 如何 ”。
语言实现者将find一种方法来优化代码如何在底层工作，如果我们不尝试使其更好地优化。 recursion也可以在支持尾部呼叫优化的语言中进行优化。
从程序员的angular度来看，更重要的是可读性和可维护性，而不是首先进行优化。 再次，“不成熟的优化是万恶的根源”。
这是一个猜测。 一般来说，如果两个程序都使用了非常好的algorithm（不包括实现难度），那么recursion可能不会经常循环或经常遇到大小合适的问题，如果使用语言w / tail调用recursion （和尾recursionalgorithm和循环也作为语言的一部分） – 这可能会非常相似，甚至可能更喜欢一些时间recursion。
一般来说，recursion不会比任何实际使用中的循环都快，这两种forms都有可行的实现。 我的意思是，当然，你可以编码循环，这是永恒的，但是会有更好的方法来实现同样的循环，可以超越任何通过recursion实现相同的问题。
原因是你打了头， 创build和销毁堆栈帧比简单的跳跃更昂贵。
但是，请注意，我说“有可行的两种forms的实现”。 对于像许多sortingalgorithm这样的事情来说，实现这些algorithm的方法往往不是一个可行的方法，因为子任务本身就是这个过程的一部分，所以没有有效地build立自己的版本。 因此，recursion可能与试图通过循环实现algorithm一样快。
编辑：这个答案是假设非function语言，大多数基本数据types是可变的。 它不适用于function语言。
根据理论它是相同的东西。 具有相同O（）复杂度的recursion和循环将以相同的理论速度工作，但实际速度当然取决于语言，编译器和处理器。 可以用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; }
