递归比循环快吗？
我知道递归有时比循环干净得多，而且我没有询问何时应该在迭代上使用递归，我知道已经有很多问题了。
我要问的是，递归比循环快吗？在我看来，你总是能够优化循环并让它比递归函数更快地执行，因为循环不存在不断设置新的堆栈帧。
我特别在寻找递归是否在递归是处理数据的正确方法的应用程序中更快，例如在某些排序函数、二叉树等中。
这取决于所使用的语言。你写了“语言不可知论”，所以我会举一些例子。
在 Java、C 和 Python 中，与迭代（通常）相比，递归相当昂贵，因为它需要分配新的堆栈帧。在某些 C 编译器中，可以使用编译器标志来消除这种开销，它将某些类型的递归（实际上是某些类型的尾调用）转换为跳转而不是函数调用。
在函数式编程语言实现中，有时迭代可能非常昂贵，而递归可能非常便宜。在许多情况下，递归被转换为简单的跳转，但更改循环变量（它是可变的）有时需要一些相对繁重的操作，尤其是在支持多线程执行的实现上。由于mutator和垃圾收集器之间的交互，如果两者可能同时运行，突变在其中一些环境中是昂贵的。
我知道在某些 Scheme 实现中，递归通常比循环更快。
简而言之，答案取决于代码和实现。使用你喜欢的任何风格。如果您使用的是函数式语言，递归可能会更快。如果您使用的是命令式语言，迭代可能会更快。在某些环境中，这两种方法都会生成相同的程序集（将其放入您的管道并抽它）。
附录：在某些环境中，最好的选择既不是递归也不是迭代，而是高阶函数。这些包括“map”、“filter”和“reduce”（也称为“fold”）。这些不仅是首选样式，而且它们通常更简洁，而且在某些环境中，这些函数是第一个（或唯一一个）从自动并行化中获得提升的函数——因此它们可以比迭代或递归快得多。 Data Parallel Haskell 就是这种环境的一个例子。
列表推导是另一种选择，但它们通常只是迭代、递归或高阶函数的语法糖。
递归比循环快吗？
不，迭代总是比递归快。 （在冯诺依曼架构中）
解释：
如果您从头开始构建通用计算机的最小操作，“迭代”首先作为构建块出现，并且比“递归”占用更少的资源，因此更快。
从头开始构建伪计算机：
问问自己：你需要什么来计算一个值，即遵循一个算法并得到一个结果？
我们将建立概念的层次结构，从头开始，首先定义基本的核心概念，然后用这些概念构建第二级概念，依此类推。
第一个概念：存储单元、存储、状态。要执行某些操作，您需要存储最终和中间结果值的地方。假设我们有一个无限的“整数”单元数组，称为内存，M[0..Infinite]。说明：做某事 - 变换一个单元格，改变它的值。改变状态。每条有趣的指令都会执行一次转换。基本指令是： a) 设置和移动内存单元将值存储到内存中，例如：存储 5 m[4] 将值复制到另一个位置：例如：存储 m[4] m[8] b) 逻辑和算术以及， or, xor, not add, sub, mul, div。例如添加 m[7] m[8] 一个执行代理：现代 CPU 中的一个核心。 “代理”是可以执行指令的东西。代理人也可以是遵循纸上算法的人。步骤顺序：指令序列：即：先执行此操作，后执行此操作，等等。命令式指令序列。甚至一行表达式也是“命令式指令序列”。如果您有一个具有特定“评估顺序”的表达式，那么您有步骤。这意味着即使是单个组合表达式也有隐含的“步骤”，也有隐含的局部变量（我们称之为“结果”）。例如：4 + 3 * 2 - 5 (- (+ (* 3 2) 4 ) 5) (sub (add (mul 3 2) 4 ) 5) 上面的表达式暗示了 3 个步骤，其中包含一个隐含的“结果”变量。 // 伪代码 1.result = (mul 3 2) 2.result = (add 4 result) 3.result = (sub result 5) 所以即使是中缀表达式，因为你有一个特定的求值顺序，也是一个命令式的指令序列.该表达式暗示要按特定顺序进行的一系列操作，并且由于有步骤，因此还有一个隐含的“结果”中间变量。指令指针：如果您有一系列步骤，那么您还有一个隐含的“指令指针”。指令指针标记下一条指令，并在读取指令之后但在执行指令之前前进。在这个伪计算机中，指令指针是内存的一部分。 （注意：通常指令指针是 CPU 内核中的一个“特殊寄存器”，但在这里我们将简化概念并假设所有数据（包括寄存器）都是“内存”的一部分） 跳转 - 一旦你有一个有序数量的步骤和指令指针，您可以应用“存储”指令来更改指令指针本身的值。我们将使用一个新名称来调用 store 指令的这种特定用途：Jump。我们使用新名称是因为更容易将其视为一个新概念。通过更改指令指针，我们指示代理“转到第 x 步”。无限迭代：通过向后跳，现在可以让代理“重复”一定数量的步骤。此时我们有无限迭代。 1. mov 1000 m[30] 2. sub m[30] 1 3. jmp-to 2 // 无限循环 Conditional - 有条件地执行指令。使用“条件”子句，您可以根据当前状态（可以使用前一条指令设置）有条件地执行几条指令之一。适当的迭代：现在有了条件子句，我们可以逃脱跳回指令的无限循环。我们现在有一个条件循环，然后是正确的迭代 1. mov 1000 m[30] 2. sub m[30] 1 3.（如果不为零）跳转 2 // 仅当前一个子指令没有结果时才跳转in 0 // 这个循环将重复 1000 次 // 这里我们有适当的 ***iteration***，一个条件循环。命名：为保存数据或保存步骤的特定内存位置命名。这只是一个“方便”。我们不会通过定义内存位置的“名称”来添加任何新指令。 “命名”不是给代理的指令，只是给我们方便。命名使代码（此时）更易于阅读和更改。 #define counter m[30] // 命名内存位置 mov 1000 counter loop: // 命名指令指针位置 sub counter 1（如果不为零） jmp-to loop 一级子程序：假设有一系列步骤需要经常执行。您可以将步骤存储在内存中的指定位置，然后在需要执行它们时跳转到该位置（调用）。在序列结束时，您需要返回调用点以继续执行。使用这种机制，您可以通过组合核心指令来创建新指令（子程序）。实现：（不需要新概念）将当前指令指针存储在预定义的内存位置跳转到子程序结束时，您从预定义的内存位置检索指令指针，有效地跳转回原始指令的以下指令call 单级实现的问题：您不能从子程序调用另一个子程序。如果这样做，您将覆盖返回地址（全局变量），因此您不能嵌套调用。为了更好地实现子程序：您需要一个堆栈堆栈：您定义一个内存空间作为“堆栈”工作，您可以在堆栈上“推送”值，也可以“弹出”最后一个“推送”的值。要实现堆栈，您需要一个堆栈指针（类似于指令指针），它指向堆栈的实际“头”。当你“push”一个值时，堆栈指针递减并且你存储这个值。当您“弹出”时，您会在实际堆栈指针处获得值，然后堆栈指针会递增。子程序 现在我们有了一个堆栈，我们可以实现适当的子程序，允许嵌套调用。实现方式类似，但我们不是将指令指针存储在预定义的内存位置，而是将 IP 的值“压入”堆栈。在子程序结束时，我们只是从堆栈中“弹出”值，有效地跳回到原始调用之后的指令。这种具有“堆栈”的实现允许从另一个子程序调用一个子程序。通过这种实现，我们可以在将新指令定义为子程序时创建多个抽象级别，方法是使用核心指令或其他子程序作为构建块。递归：当子程序调用自身时会发生什么？这称为“递归”。问题：覆盖子程序可以存储在内存中的本地中间结果。由于您正在调用/重用相同的步骤，因此如果中间结果存储在预定义的内存位置（全局变量）中，它们将在嵌套调用中被覆盖。解决方案：为了允许递归，子程序应该将本地中间结果存储在堆栈中，因此，在每次递归调用（直接或间接）时，中间结果都存储在不同的内存位置。
...
达到递归后，我们停在这里。
结论：
在冯诺依曼架构中，显然“迭代”是比“递归”更简单/基本的概念。我们在第 7 级有一种“迭代”形式，而“递归”在概念层次结构的第 14 级。
机器代码的迭代总是更快，因为它意味着更少的指令，因此更少的 CPU 周期。
哪一个更好”？
当您处理简单的顺序数据结构时，您应该使用“迭代”，并且在任何地方都可以使用“简单循环”。
当您需要处理递归数据结构（我喜欢称它们为“分形数据结构”），或者当递归解决方案显然更“优雅”时，您应该使用“递归”。
建议：使用最适合工作的工具，但要了解每个工具的内部工作原理，以便明智地选择。
最后，请注意您有很多机会使用递归。你到处都有递归数据结构，你现在正在看一个：支持你正在阅读的内容的 DOM 部分是 RDS，JSON 表达式是 RDS，计算机中的分层文件系统是 RDS，即：你有一个根目录，包含文件和目录，每个目录都包含文件和目录，每个目录都包含文件和目录...
在替代方案是显式管理堆栈的情况下，递归可能会更快，例如您提到的排序或二叉树算法。
我曾经遇到过用 Java 重写递归算法使其变慢的情况。
所以正确的方法是首先以最自然的方式编写它，只有在分析表明它很关键时才进行优化，然后测量假定的改进。
考虑每个迭代和递归绝对必须做的事情。
迭代：跳转到循环的开头
递归：跳转到被调用函数的开头
您会看到这里没有太大的差异空间。
（我假设递归是尾调用并且编译器知道该优化）。
这里的大多数答案都是错误的。正确的答案是视情况而定。例如，这里有两个遍历树的 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，我可以大致达到与递归方法相当的水平。但至少在我的电脑上，访问堆内存的成本大于递归调用的成本。
但是这个讨论主要是没有实际意义的，因为递归树行走是不正确的。如果您有足够大的树，您将用完调用堆栈空间，这就是必须使用迭代算法的原因。
这里的大多数答案都忘记了为什么递归通常比迭代解决方案慢的明显罪魁祸首。它与堆栈帧的建立和拆除有关，但并非完全如此。每次递归的自动变量的存储通常有很大的不同。在带有循环的迭代算法中，变量通常保存在寄存器中，即使它们溢出，它们也会驻留在 1 级缓存中。在递归算法中，变量的所有中间状态都存储在堆栈中，这意味着它们将产生更多的内存溢出。这意味着即使它进行相同数量的操作，它也会在热循环中进行大量内存访问，更糟糕的是，这些内存操作的重用率很差，从而导致缓存效率降低。
TL;DR 递归算法通常比迭代算法具有更差的缓存行为。
一般来说，不，在任何具有两种形式的可行实现的实际用法中，递归都不会比循环快。我的意思是，当然，您可以编写需要很长时间的循环，但是会有更好的方法来实现相同的循环，通过递归可以胜过相同问题的任何实现。
关于原因，您一针见血；创建和销毁堆栈帧比简单的跳转更昂贵。
但是，请注意我说过“两种形式都有可行的实现”。对于像许多排序算法这样的事情，由于产生了本质上是流程一部分的子“任务”，因此往往没有一种非常可行的方式来实现它们，它不能有效地设置自己的堆栈版本。因此，递归可能与尝试通过循环实现算法一样快。
编辑：这个答案假设非功能语言，其中大多数基本数据类型是可变的。它不适用于函数式语言。
在任何实际系统中，不，创建堆栈帧总是比 INC 和 JMP 更昂贵。这就是为什么真正好的编译器会自动将尾递归转换为对同一帧的调用，即没有开销，因此您可以获得更易读的源代码版本和更高效的编译版本。一个非常非常好的编译器甚至应该能够在可能的情况下将普通递归转换为尾递归。
函数式编程更多的是关于“什么”而不是“如何”。
如果我们不尝试使其比需要的更优化，语言实现者将找到一种方法来优化代码在底层的工作方式。递归也可以在支持尾调用优化的语言中进行优化。
从程序员的角度来看，更重要的是可读性和可维护性，而不是优化。同样，“过早的优化是万恶之源”。
这是一个猜测。一般来说，如果两者都使用非常好的算法（不计算实现难度），递归可能不会经常或永远不会击败循环，如果两者都使用非常好的算法（不计算实现难度），如果使用带有 tail call recursion 的语言（和尾递归算法）可能会有所不同并且循环也作为语言的一部分）——这可能非常相似，有时甚至可能更喜欢递归。
根据理论，它是相同的东西。具有相同 O() 复杂度的递归和循环将以相同的理论速度工作，但实际速度当然取决于语言、编译器和处理器。具有数字幂的示例可以使用 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;
}
O(n)，但对于所有 n，一个可能花费的时间是另一个的 x 倍。
关注公众号
不定期副业成功案例分享
