为了账号安全,请及时绑定邮箱和手机立即绑定

递归比循环更快吗?

/ 猿问

递归比循环更快吗?

慕工程0101907 2019-07-29 10:15:12

递归比循环更快吗?

我知道递归有时比循环更清晰,而且我不会询问何时应该使用递归迭代,我知道有很多问题已经存在。

我要问的是,递归是否比循环更快?对我来说,似乎总是能够改进循环并让它比递归函数更快地执行,因为循环不会不断地设置新的堆栈帧。

我特别关注在递归是处理数据的正确方法的应用程序中递归是否更快,例如在一些排序函数,二叉树等中。


查看完整描述

3 回答

?
慕尼黑的夜晚无繁华

这取决于使用的语言。你写了'语言不可知',所以我举一些例子。

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

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

我知道在一些Scheme实现中,递归通常比循环更快。

简而言之,答案取决于代码和实现。使用您喜欢的任何风格。如果您使用的是函数式语言,则递归可能会更快。如果您使用命令式语言,迭代可能会更快。在某些环境中,这两种方法都会导致生成相同的程序集(将其放入管道并对其进行抽吸)。

附录:在某些环境中,最好的选择既不是递归也不是迭代,而是高阶函数。这些包括“map”,“filter”和“reduce”(也称为“fold”)。这些不仅是首选样式,不仅通常更清晰,而且在某些环境中,这些函数是第一个(或唯一)从自动并行化中获得提升的功能 - 因此它们可以比迭代或递归快得多。Data Parallel Haskell就是这种环境的一个例子。

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


查看完整回答
反对 回复 2019-07-29
?
呼唤远方

递归比循环更快?

不,迭代总是比递归更快。(在冯诺依曼建筑中)

说明:

如果从头开始构建通用计算机的最小操作,“迭代”首先作为构建块,并且比“递归”的资源密集程度更低,因此ergo更快。

从头开始构建伪计算机:

问自己:你需要什么来计算一个值,即遵循算法并达到结果?

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

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

  2. 说明:做一些事情 - 转换一个单元格,改变它的价值。改变国家。每条有趣的指令都会执行转换。基本说明如下:

    a)设置和移动存储单元

    b)逻辑和算术

    • 而且,或者,xor,不是

    • add,sub,mul,div。例如加m [7] m [8]

    • 将值存储到内存中,例如:store 5 m [4]

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

  3. 执行代理:现代CPU中的核心。“代理”是可以执行指令的东西。一个代理,也可以在纸上的算法以下的人。

  4. 步骤顺序:一系列指令:即:首先执行此操作,然后执行此操作,等等。命令序列的指令。甚至一行表达式也是“命令式指令序列”。如果您的表达式具有特定的“评估顺序”,那么您就有了步骤。这意味着甚至一个组合表达式都有隐含的“步骤”,并且还有一个隐式局部变量(让我们称之为“结果”)。例如:

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

    上面的表达式暗示了具有隐式“结果”变量的3个步骤。

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

    因此,即使是中缀表达式,因为您有一个特定的评估顺序,也是一个必要的指令序列。表达式意味着要按特定顺序进行一系列操作,并且由于存在步骤,因此还存在隐式“结果”中间变量。

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

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

  6. 跳转 - 一旦有了有序的步数和指令指针,就可以应用“ 存储 ”指令来改变指令指针本身的值。我们将使用新名称来调用store指令的这种特定用法:Jump。我们使用一个新名称,因为更容易将其视为一个新概念。通过改变指令指针,我们指示代理“转到步骤x”。

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

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

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

    1. mov 1000 m[30]2. sub m[30] 13. (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 counterloop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop
  11. 一级子程序:假设您需要经常执行一系列步骤。您可以将步骤存储在内存中的命名位置,然后在需要执行它们(调用)时跳转到该位置。在序列结束时,您需要返回调用以继续执行的程度。使用此机制,您可以通过编写核心指令来创建新指令(子例程)。

    实施:(无需新概念)

    问题的一个层面实现:你不能从一个子程序调用另一个子程序。如果这样做,您将覆盖返回的地址(全局变量),因此您无法嵌套调用。

    为子程序提供更好的实现:您需要一个堆栈

    • 将当前指令指针存储在预定义的存储位置

    • 跳转到子程序

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

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

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

  14. 递归:当子程序调用自身时会发生什么?这称为“递归”。

    问题:覆盖本地中间结果,子程序可以存储在内存中。由于您正在调用/重用相同的步骤,如果中间结果存储在预定义的内存位置(全局变量)中,它们将被嵌套调用覆盖。

    解决方案:为了允许递归,子程序应将本地中间结果存储在堆栈中,因此,在每次递归调用(直接或间接)上,中间结果存储在不同的存储单元中。

...

到达递归我们就到此为止。

结论:

在Von Neumann架构中,显然“迭代”是比“递归”更简单/基本的概念。我们在7级有一个“迭代”形式,而“递归”在概念层次的14级。

迭代在机器代码中总是更快,因为它意味着更少的指令,因此更少的CPU周期。

哪一个更好”?

  • 在处理简单的顺序数据结构时,应该使用“迭代”,并且在“简单循环”的任何地方都可以使用“迭代”。

  • 当您需要处理递归数据结构时(我喜欢称之为“分形数据结构”),或者当递归解决方案明显更“优雅”时,您应该使用“递归”。

建议:使用最好的工具,但要了解每个工具的内部工作方式,以便明智地选择。

最后,请注意您有很多机会使用递归。你到处都有递归数据结构,你现在正在看一个:支持你正在阅读的内容的DOM部分是RDS,JSON表达式是RDS,计算机中的分层文件系统是RDS,即:你有一个根目录,包含文件和目录,每个目录包含文件和目录,每个目录包含文件和目录......


查看完整回答
反对 回复 2019-07-29
?
万千封印

如果替代方法是显式管理堆栈,递归可能会更快,就像您提到的排序或二叉树算法一样。

我有一个案例,用Java重写递归算法使它变慢。

因此,正确的方法是首先以最自然的方式编写它,只有在分析显示它是关键的时候进行优化,然后测量所谓的改进。


查看完整回答
反对 回复 2019-07-29

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信