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立二级概念,等等。

  1. 第一个概念: 内存单元,存储,状态 。 要做一些事情,你需要存储最终和中间结果值的地方。 假设我们有一个无限的“整数”单元arrays,称为存储器 ,M [0..Infinite]。

  2. 说明:做点什么 – 改造一个细胞,改变它的价值。 改变状态 。 每个有趣的指令都会进行转换。 基本说明是:

    a) 设置并移动内存单元

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

    b) 逻辑和算术

    • 和,或,异或,不
    • 加,分,多,分。 例如添加m [7] m [8]
  3. 执行代理 :现代CPU中的核心 。 “代理”是可以执行指令的东西。 代理人也可以是在纸上遵循algorithm的人。

  4. 步骤顺序:一系列的指令 :即:先做这个,然后做这个,等等。一个命令的顺序。 即使是一行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。

  5. 指令指针 :如果你有一系列的步骤,你也有一个隐含的“指令指针”。 指令指针标记下一条指令,并在指令读取之后但在指令执行之前前进。

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

  6. 跳转 – 一旦你有一个有序的步数和一个指令指针 ,你可以应用“ 存储 ”指令来改变指令指针本身的值。 我们将用一个新的名称来调用这个存储指令的具体用法: 跳转 。 我们用一个新的名字,因为更容易把它看作一个新的概念。 通过更改指令指针,我们正在指示代理程序“转到步骤x”。

  7. 无限迭代 :通过跳回来,现在可以让代理“重复”一定数量的步骤。 在这一点上,我们有无限的迭代。

      1. mov 1000 m[30] 2. sub m[30] 1 3. jmp-to 2 // infinite loop 
  8. 有条件的 – 有条件地执行指令。 使用“条件”子句,可以根据当前状态(可以使用前面的指令设置)有条件地执行几条指令之一。

  9. 适当的迭代 :现在使用条件子句,我们可以避开跳回指令的无限循环。 我们现在有一个条件循环 ,然后进行适当的迭代

     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. 
  10. 命名 :给名字保存数据或者保存一个步骤 。 这只是一个“方便”。 我们没有增加任何新的说明,因为有能力为内存位置定义“名称”。 “命名”不是代理人的指令,这只是给我们一个方便。 命名使代码(在这一点上)更容易阅读,更容易改变。

      #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 
  11. 一级子程序 :假设你需要经常执行一系列步骤。 您可以将步骤存储在内存中的指定位置,然后在需要执行(呼叫)时跳转到该位置。 在序列结束时,您需要返回调用点继续执行。 有了这个机制,你就可以通过编写核心指令来创build新的指令 (子程序)。

    实施:(不需要新的概念)

    • 将当前的指令存储在预定义的存储位置
    • 跳转到子程序
    • 在子程序结束时,您从预定义的内存位置检索指令指针,有效地跳回到原始调用的以下指令

    单层实现的问题:不能从子例程中调用另一个子例程。 如果你这样做,你会覆盖返回的地址(全局variables),所以你不能嵌套调用。

    为了更好的实现子程序:你需要一个堆栈

  12. 堆栈 :你定义一个内存空间来作为一个“堆栈”,你可以在堆栈上“推”数值,也可以“popup”最后一个“推”数值。 要实现一个堆栈,你需要一个堆栈指针 (类似于指令指针),它指向堆栈的实际“头部”。 当您“推”一个值时,堆栈指针递减,并存储该值。 当你“popup”,你得到实际的堆栈指针的值,然后堆栈指针递增。

  13. 子程序现在我们有了一个堆栈,我们可以实现允许嵌套调用的正确的子程序。 实现是类似的,但是不是将指令指针存储在预定义的存储位置,而是将IP的值“推”到堆栈中 。 在子程序结束时,我们只是从堆栈中“popup”值,在原始调用之后有效地跳回到指令。 这个具有“堆栈”的实现允许从另一个子程序调用子程序。 通过这个实现,我们可以通过使用核心指令或其他子程序作为构build块来定义新的指令作为子程序时创build几个抽象层次。

  14. 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_pushCALL ,然后是另一个到st_pop

在前者中,每个节点只有recursionCALL

另外,在callstack上访问variables的速度非常快。 这意味着你正在从内存中读取,这可能总是在最内层的caching中。 另一方面,显式堆栈必须由堆中的malloc :ed内存支持,访问速度要慢得多。

通过仔细优化,比如内联st_pushst_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; }