递归是否比循环更快？

Question

递归是否比循环更快？

performanceloopsrecursioniteration

374

我知道递归有时比循环更简洁，而且我不问什么时候应该使用递归而不是迭代，因为已经有很多关于这个问题的答案了。

我想问的是，在任何情况下，递归是否比循环更快？在我看来，你总是能够改进循环并使其比递归函数更快，因为循环不需要不断地设置新的堆栈帧。

我特别想知道，在处理数据的正确方式是递归的应用程序中，例如某些排序函数、二叉树等，递归是否更快。

- Carson Myers

5

有时候，针对某些递归公式的迭代过程或闭合型公式可能需要数个世纪才能出现。我认为只有在这种情况下，递归才更快 :) 哈哈 - Pratik Deoghare

54

就我个人而言，我更喜欢迭代。;-) - Iterator

可能是递归还是迭代？的重复问题。 - nawfal

4

递归是否比循环更快？ - ctrl-alt-delor

1

@PratikDeoghare 不，问题不是选择完全不同的算法。您始终可以将递归函数转换为使用循环的完全相同的方法。例如，此答案具有递归和循环格式中相同的算法。通常，您将递归函数的参数元组放入堆栈中，推送到堆栈以调用，从堆栈中丢弃以从函数返回。 - TamaMcGlinn

13个回答

81

递归比循环更快吗？

不是的，（在冯·诺依曼架构中）迭代总是比递归快。

解释：

如果你从头开始构建一个通用计算机的最小操作，“迭代”是第一个构建块，且比“递归”所需资源少，因此更快。

从零开始构建伪计算机：

反问自己：你需要什么才能计算出一个值，即按照算法并达到结果？

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

第一概念：存储器单元、存储、状态。要执行某项任务，需要位置来存储最终和中间结果值。假设我们有一个无穷的整数单元数组，称为存储器，M [0..Infinite]。
指令：执行某个操作——转换一个单元，改变其值。改变状态。每个有趣的指令都执行一种转换。基本指令包括：

a）存储和移动存储单元
- 将一个值存储到存储器中，例如：store 5 m [4]
- 将值复制到另一个位置：例如：store m [4] m [8]
b）逻辑和算术
- and、or、xor、not
- add、sub、mul、div，例如：add m [7] m [8]
执行代理：现代CPU中的核心。一个“代理”是可以执行指令的东西。一个代理也可以是一个人在纸上按照算法进行操作。
步骤顺序：即：先做这个，再做那个等。有着命令式指令序列。即使是一个表达式也是“命令式指令序列”。如果你有一个带有特定“求值顺序”的表达式，那么你就有了步骤。这意味着一个组合表达式即使有隐含的“步骤”，也有一个隐含的局部变量（让我们称之为“结果”）。例如：
```
4 + 3 * 2 - 5
(- (+ (* 3 2) 4 ) 5)
(sub (add (mul 3 2) 4 ) 5)  
```
上述表达式暗示了三个步骤，其中有一个隐含的“result”变量。
```
// pseudocode

       1. result = (mul 3 2)
       2. result = (add 4 result)
       3. result = (sub result 5)
```
即使是中缀表达式，由于你有一个特定的评估顺序，因此它们是一系列命令的命令序列。表达式意味着要按特定顺序执行一系列操作，因为有步骤，所以还存在一个隐含的“结果”中间变量。

指令指针：如果您有一系列步骤，则还有一个隐含的“指令指针”。指令指针标记下一条指令，并在读取指令但在执行指令之前推进。

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

跳跃 - 一旦您有一定顺序的步骤和一个指令指针，您可以应用“存储”指令来改变指令指针本身的值。我们将使用一个新名称来称呼这个存储指令的特定用途：跳跃。我们使用一个新名称是因为更容易将其视为新概念。通过改变指令指针，我们正在指示代理“去到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

一级子程序：假设有一系列需要频繁执行的步骤。您可以将这些步骤存储在内存中的命名位置，当需要执行它们（调用）时，可以跳转到该位置。在序列的末尾，您需要返回到调用点以继续执行。通过此机制，您可以通过组合核心指令来创建新指令（子程序）。

实现：（不需要新概念）
- 将当前指令指针存储在预定义的内存位置中
- 跳转到子例程
- 在子例程结束时，从预定义的内存位置检索指令指针，有效地跳回到原始调用的下一个指令。
一级实现的问题：您无法从子例程中调用另一个子例程。如果这样做，您将覆盖返回地址（全局变量），因此无法嵌套调用。

更好的子程序实现：需要堆栈
堆栈：您定义一个内存空间作为“堆栈”，可以将值“推入”堆栈，并且还可以“弹出”最后“推入”的值。要实现堆栈，您将需要一个堆栈指针（类似于指令指针），它指向堆栈的实际“头”。当您“推入”一个值时，堆栈指针会减少，并且您将存储该值。当您“弹出”时，可以获取实际堆栈指针处的值，然后将堆栈指针递增。
子程序：既然我们有了堆栈，我们就可以实现适当的子程序允许嵌套调用。实现类似，但是不是存储指令指针在预定义的内存位置上，而是将IP的值“推入”堆栈中。在子例程结束时，我们只需从堆栈中“弹出”该值，有效地跳回到原始调用之后的指令。这种实现方式使用“堆栈”，因此允许从另一个子例程调用子例程。通过使用核心指令或其他子例程作为构建块，使用此实现方式，我们可以创建多层抽象来定义新指令作为子例程。
递归：当子例程调用自身时会发生什么？这称为“递归”。

问题：覆盖子例程可以存储在内存中的本地中间结果。由于您正在调用/重用相同的步骤，如果中间结果存储在预定义的内存位置（全局变量）中，则将在嵌套调用上进行覆盖。

解决方案：

存储在堆栈中

递归调用

...

到达递归后我们停止。

结论：

在冯·诺依曼体系结构中，显然“迭代”比“递归”更简单/基础。我们在第7级拥有一种“迭代”形式，而“递归”则在第14级概念层次结构中。

迭代在机器代码中始终会更快，因为它意味着更少的指令，因此需要更少的 CPU 周期。

哪一个更好？

当您处理简单、顺序的数据结构以及任何“简单循环”可以完成时，应使用“迭代”
当您需要处理递归数据结构（我喜欢称之为“分形数据结构”）或递归解决方案明显更加“优雅”时，应使用“递归”。

建议：使用最适合工作的工具，但要了解每个工具的内部工作原理，以明智选择。

最后，请注意您有大量机会使用递归。到处都有递归数据结构，你现在正在查看其中之一：支持你所读内容的DOM的某些部分就是一个RDS，JSON表达式是一个RDS，计算机中的分层文件系统是一个RDS，即：你有一个根目录，包含文件和目录，每个目录都包含文件和目录，每个目录都包含文件和目录...

- Lucio M. Tato

6

你假设你的进展是1）必要的，且2）停留在你所做的地方。但是，1）它并不是必要的（例如，递归可以转化为跳跃，如被接受的答案所解释，因此不需要堆栈），而且2）它不必在那里停止（例如，最终你将达到并发处理阶段，如果你有可变状态就可能需要锁定，如你在第二步中引入的，这会使一切变慢；而像函数式/递归这样的不可变解决方案则可以避免锁定，因此可能更快/更并行）。 - hmijail

3

“recursion can be turned into a jump”是错误的。真正有用的递归不能被转换为跳跃。尾调用“递归”是一个特殊情况，你可以通过编译器将其中可以被简化为循环的部分“作为递归”编码。此外，你混淆了“不可变性”和“递归”，这些概念是独立的。 - Lucio M. Tato

"真正有用的递归不能被转化为跳跃" -> 所以尾调用优化有点无用？此外，不可变和递归可能是正交的，但您确实将循环与可变计数器联系起来 - 看看您的第9步。在我看来，您认为循环和递归是根本不同的概念；它们并不是。https://dev59.com/sHE85IYBdhLWcg3wtVxT#28033212?noredirect=1#comment2667303_2651200 - hmijail

@hmijail 我认为比“有用”更好的词是“真实”。尾递归并不是真正的递归，因为它只是使用函数调用语法来伪装无条件分支，即迭代。真正的递归为我们提供了回溯堆栈。然而，尾递归仍然具有表达性，这使它很有用。当使用尾调用表达式表示迭代代码时，使其易于分析代码正确性的递归属性被赋予迭代代码。虽然在尾版本中可能会有额外的参数等额外复杂性，但有时会稍微抵消这一点。 - Kaz

这表明没有等待数据的情况。在现代操作系统中，操作系统调度程序将调度线程以减少缓存未命中。将数据放在堆上并具有大型堆栈可能导致许多缓存未命中，从而导致程序获得较少的CPU时间。因此，虽然从理论上讲是正确的，但在实践中并不那么简单直接。 - jth_92

显示剩余2条评论

51

如果选择显式管理栈（如您提到的排序或二叉树算法）作为替代方案，则递归可能更快。

我曾经有一个情况，将递归算法在Java中重写后变得更慢了。

因此，正确的方法是首先用最自然的方式编写它，仅在分析显示它是关键问题时才进行优化，然后测量所谓的改进。

- starblue

8

对于“_首先以最自然的方式写出来_”这一点给予“+1”，特别是“_只有在性能分析显示它很关键时才进行优化_”。 - TripeHound

8

认可硬件栈可能比软件手动实现的堆栈更快，这点得到加分。有效地表明了所有“否”回答都是不正确的。 - sh1

这假设你编写的算法确实是最快的迭代算法。但是，重构/优化不足也是有可能的。 - jennyfofenny

15

这里大部分的答案都是错误的。正确的答案是取决于情况。例如，这里有两个遍历树的 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，然后再调用 st_pop。

在前者中，你只需为每个节点进行递归调用。

此外，访问调用堆栈上的变量非常快。这意味着你正在从内存中读取，该内存很可能始终在最内部的缓存中。另一方面，显式堆栈必须由堆中的 malloc 分配的内存支持，访问速度要慢得多。

通过仔细优化，如内联 st_push 和 st_pop，我可以达到与递归方法大致相同的效果。但至少在我的电脑上，访问堆内存的代价比递归调用的代价更大。

但这次讨论大多无意义，因为递归遍历树是 不正确的。如果你有一个足够大的树，你将用尽调用堆栈空间，这就是必须使用迭代算法的原因。

- Björn Lindqvist

2

我可以确认我遇到了类似的情况，并且有些情况下递归比手动堆栈更快。特别是当编译器开启优化以避免调用函数的一些开销时。 - while1fork

2

对7个节点的二叉树进行了10^8次预排序遍历。递归25纳秒。显式堆栈(有界检查或非有界检查-没有太大区别)~15纳秒。递归需要做更多的事情(寄存器保存和还原+(通常)更严格的框架对齐)，除了只是推送和跳转。(在动态链接库中使用PLT会更糟。)您不需要为显式堆栈分配堆内存。您可以使用obstack，其第一个框架位于常规调用堆栈上，因此对于不超过第一个块的最常见情况，您不会牺牲缓存局部性。 - Petr Skocik

2

感谢您的回答。我在一道LeetCode树比较题中遇到了这个问题，但是无法理解为什么我的迭代解法比95%的递归解法慢。堆栈内存和多次调用确实很有道理，特别是我使用Java时，由于其混淆的内存管理方式，更加明显。 - ameddin73

也许最令人尴尬的事实是，在（纯）C中，您无法确定何时会溢出调用堆栈。另一个荒谬的事实是，任意小的堆栈都符合ISO C标准，这实际上意味着即使没有任何C函数调用，main函数中的argc也可能会溢出！虽然在实践中永远不应该出现这种情况，但它表明关于调用堆栈的任何限制已经涉及足够的实现细节。因此，在纯C的意义上，我会忽略这些限制，并且两个算法都应该正确，而不需要更详细的实现环境要求。 - FrankHB

我有同样的发现。我所学到的一切都是迭代比递归更好、更快等等。但在实践中（与理论相比），由于缓存未命中，堆上管理的大型堆栈会慢得多。然而，正如你指出的，最终取决于你需要深入多少。经验上，在C/C++中，最快的解决方案是递归，直到发生堆栈溢出，但其他权衡是代码可读性以及随着数据增长可能发生的堆栈溢出。 - jth_92

15

尾递归和循环一样快。许多函数式编程语言都已经在它们中实现了尾递归。

- mkorpela

42

尾递归在实现了尾调用优化的情况下可以和循环一样快：http://c2.com/cgi/wiki?TailCallOptimization - Joachim Sauer

15

这里的大多数答案都忽略了递归通常比迭代解决方案慢的明显原因。它与堆栈帧的建立和撤销有关，但并非完全如此。通常是每个递归的自动变量存储方式存在巨大差异。在具有循环的迭代算法中，变量通常存储在寄存器中，即使溢出，它们也会驻留在一级缓存中。在递归算法中，变量的所有中间状态都存储在堆栈上，这意味着它们将生成更多的内存溢出。这意味着即使执行相同数量的操作，它在热循环中将有很多内存访问，并且更糟糕的是，这些内存操作的重用率很低，使高速缓存的效果不佳。

简而言之，递归算法通常具有比迭代算法更差的高速缓存行为。

- Patrick Schlüter

12

考虑每个迭代和递归必须完成的任务。

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

你会发现这里并没有太多差异。

（我假设递归是尾调用，并且编译器意识到了这种优化。）

- Pasi Savolainen

5

通常情况下，递归在任何实际使用中都不会比循环更快，只要两种形式都有可行的实现方式。我的意思是，当然，你可以编写需要很长时间才能完成的循环，但是有更好的方法来实现相同的循环，并且可以通过这些方法优于任何递归实现相同问题的方式。

你说得很对，创建和销毁堆栈帧的成本比简单跳转更高。

但是，请注意我说的“两种形式都有可行的实现方式”。对于许多排序算法等问题，往往没有非常可行的实现方式，而不是有效地设置其自己版本的堆栈，因为生成的子“任务”本质上是该过程的一部分。因此，递归可能与尝试通过循环实现算法一样快。

注：此答案假定非函数语言，其中大多数基本数据类型都是可变的。它不适用于函数语言。

- Amber

这也是为什么编译器经常在递归频繁使用的语言中优化多个递归案例的原因。例如，在F#中，除了使用.tail操作码完全支持尾递归函数之外，你经常会看到一个递归函数被编译为循环。 - em70

没错。尾递归有时候可以兼顾两全其美——既能够以函数式的“合适”方式实现递归任务，又能够拥有循环的性能优势。 - Amber

1

一般来说，这并不正确。在某些环境中，变异（与GC交互）比尾递归更昂贵，而尾递归在输出中被转换为一个更简单的循环，它不使用额外的堆栈帧。 - Dietrich Epp

3

在任何实际的系统中，创建堆栈帧的成本总是比INC和JMP更高。这就是为什么真正好的编译器会自动将尾递归转换为对同一帧的调用，即无需开销，因此您可以获得更可读的源版本和更有效的编译版本。一个非常优秀的编译器甚至应该能够将普通递归转换为尾递归，如果可能的话。

- Kilian Foth

gcc是那些非常优秀的编译器之一吗？ - Mehdi Charife

1

函数式编程更关注"什么"而不是"如何"。

如果我们不试图使代码比必须更优化，语言实现者会找到一种优化代码工作方式的方法。在支持尾调用优化的语言中，递归也可以进行优化。

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

- koders

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dietrich Epp · Accepted Answer

这取决于所使用的编程语言。你提到了“与语言无关”，因此我将举一些例子。

在Java、C和Python中，通常情况下递归比迭代（循环）开销大，因为它需要分配新的堆栈帧。在一些C编译器中，可以使用编译器标志来消除这种开销，将某些类型的递归（实际上是某些类型的尾调用）转换为跳转而不是函数调用。

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

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

总之，答案取决于代码和实现。使用您喜欢的任何样式。如果使用函数式语言，则递归可能更快。如果使用命令式语言，则迭代可能更快。在某些环境中，两种方法将生成相同的汇编代码（请注意这一点）。

补充说明：在某些环境中，最好的选择既不是递归也不是迭代，而是高阶函数。这些包括“map”、“filter”和“reduce”（也称为“fold”）。它们不仅是首选的样式，而且通常更加简洁，在某些环境中，这些函数是自动并行化的第一个（或唯一一个）获得提升的函数。因此，它们可能比迭代或递归快得多。Data Parallel Haskell就是这样的一个环境。

列表推导是另一种选择，但这些通常只是迭代、递归或高阶函数的语法糖。