Die*_*Epp 338
这取决于使用的语言.你写了'语言不可知',所以我举一些例子.
在Java,C和Python中,与迭代(通常)相比,递归相当昂贵,因为它需要分配新的堆栈帧.在某些C编译器中,可以使用编译器标志来消除此开销,这会将某些类型的递归(实际上是某些类型的尾调用)转换为跳转而不是函数调用.
在函数式编程语言实现中,有时,迭代可能非常昂贵,并且递归可能非常便宜.在许多情况下,递归转换为简单的跳转,但是更改循环变量(这是可变的)有时需要一些相对繁重的操作,尤其是在支持多个执行线程的实现上.由于mutator和垃圾收集器之间的交互(如果两者可能同时运行),在某些环境中突变是昂贵的.
我知道在一些Scheme实现中,递归通常比循环更快.
简而言之,答案取决于代码和实现.使用您喜欢的任何风格.如果您使用的是函数式语言,则递归可能会更快.如果您使用命令式语言,迭代可能会更快.在某些环境中,这两种方法都会导致生成相同的程序集(将其放入管道并对其进行抽吸).
附录:在某些环境中,最好的选择既不是递归也不是迭代,而是高阶函数.这些包括"map","filter"和"reduce"(也称为"fold").这些不仅是首选样式,不仅通常更清晰,而且在某些环境中,这些函数是第一个(或唯一)从自动并行化中获得提升的功能 - 因此它们可以比迭代或递归快得多.Data Parallel Haskell就是这种环境的一个例子.
列表推导是另一种选择,但这些通常只是迭代,递归或更高阶函数的语法糖.
Luc*_*ato 47
递归比循环更快？
不,迭代总是比递归更快.(在冯诺依曼建筑中)
如果从头开始构建通用计算机的最小操作,"迭代"首先作为构建块,并且比"递归"的资源密集程度更低,因此ergo更快.
问自己:你需要什么来计算一个值,即遵循算法并达到结果？
我们将建立一个概念层次结构,从头开始并首先定义基本的核心概念,然后用这些概念构建二级概念,依此类推.
第一个概念:记忆细胞,存储,状态.做一些你需要的地方来存储最终和中间结果值.假设我们有一个无限的"整数"单元格,称为Memory,M [0..Infinite].
说明:做一些事情 - 转换一个单元格,改变它的价值.改变国家.每条有趣的指令都会执行转换.基本说明如下:
a)设置和移动存储单元
b)逻辑和算术
执行代理:现代CPU中的核心."代理"是可以执行指令的东西.一个代理,也可以在纸上的算法以下的人.
步骤顺序:一系列指令:即:首先执行此操作,然后执行此操作,等等.命令序列的指令.甚至一行表达式也是"命令式指令序列".如果您的表达式具有特定的"评估顺序",那么您就有了步骤.这意味着甚至一个组合表达式都有隐含的"步骤",并且还有一个隐式局部变量(让我们称之为"结果").例如:
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)
因此,即使是中缀表达式,因为您有一个特定的评估顺序,也是必不可少的指令序列.表达式意味着要按特定顺序进行一系列操作,并且由于存在步骤,因此还存在隐式"结果"中间变量.
指令指针:如果你有一系列步骤,你还有一个隐含的"指令指针".指令指针标记下一条指令,并在读取指令之后但在执行指令之前前进.
在这个伪计算机器中,指令指针是存储器的一部分.(注意:通常指令指针将是CPU内核中的"特殊寄存器",但在这里我们将简化概念并假设所有数据(包括寄存器)都是"内存"的一部分)
跳转 - 一旦有了有序的步数和指令指针,就可以应用" 存储 "指令来改变指令指针本身的值.我们将使用新名称来调用store指令的这种特定用法:Jump.我们使用一个新名称,因为更容易将其视为一个新概念.通过改变指令指针,我们指示代理"转到步骤x".
无限迭代:通过跳回,现在你可以让代理"重复"一定数量的步骤.此时我们有无限的迭代.
1. mov 1000 m[30]
2. sub m[30] 1
3. jmp-to 2 // infinite loop
条件 - 指令的有条件执行.使用"conditional"子句,您可以根据当前状态(可以使用上一条指令设置)有条件地执行多条指令之一.
正确的迭代:现在使用条件子句,我们可以逃避跳回指令的无限循环.我们现在有一个条件循环然后适当的迭代
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
一级子程序:假设您需要经常执行一系列步骤.您可以将步骤存储在内存中的命名位置,然后在需要执行它们(调用)时跳转到该位置.在序列结束时,您需要返回到调用以继续执行的程度.使用此机制,您可以通过编写核心指令来创建新指令(子例程).
实施:(无需新概念)
问题的一个层面实现:你不能从一个子程序调用另一个子程序.如果这样做,您将覆盖返回的地址(全局变量),因此您无法嵌套调用.
为子程序提供更好的实现:您需要一个堆栈
堆栈:您定义一个内存空间作为"堆栈",您可以"推"堆栈上的值,并"弹出"最后一个"推"值.要实现堆栈,您需要一个堆栈指针(类似于指令指针),它指向堆栈的实际"头部".当您"推"一个值时,堆栈指针会递减并存储该值.当您"弹出"时,您将获得实际堆栈指针处的值,然后堆栈指针会递增.
Subroutines Now that we have a stack we can implement proper subroutines allowing nested calls. The implementation is similar, but instead of storing the Instruction Pointer in a predefined memory position, we "push" the value of the IP in the stack. At the end of the subroutine, we just "pop" the value from the stack, effectively jumping back to the instruction after the original call. This implementation, having a "stack" allows calling a subroutine from another subroutine. With this implementation we can create several levels of abstraction when defining new instructions as subroutines, by using core instructions or other subroutines as building blocks.
递归:当子程序调用自身时会发生什么？这称为"递归".
问题:覆盖本地中间结果,子程序可以存储在内存中.由于您正在调用/重用相同的步骤,如果中间结果存储在预定义的内存位置(全局变量)中,它们将被嵌套调用覆盖.
解决方案:为了允许递归,子程序应将本地中间结果存储在堆栈中,因此,在每次递归调用(直接或间接)上,中间结果存储在不同的存储单元中.
...
到达递归我们就到此为止.
在Von Neumann架构中,显然"迭代"是比"递归"更简单/基本的概念.我们在7级有一个"迭代"形式,而"递归"在概念层次的14级.
迭代在机器代码中总是更快,因为它意味着更少的指令,因此更少的CPU周期.
在处理简单的顺序数据结构时,应该使用"迭代",并且在"简单循环"的任何地方都可以使用"迭代".
当您需要处理递归数据结构时(我喜欢称之为"分形数据结构"),或者当递归解决方案明显更"优雅"时,您应该使用"递归".
建议:使用最好的工具,但要了解每个工具的内部工作方式,以便明智地选择.
最后,请注意您有很多机会使用递归.你到处都有递归数据结构,你现在正在看一个:支持你正在阅读的内容的DOM部分是RDS,JSON表达式是RDS,计算机中的分层文件系统是RDS,即:你有一个根目录,包含文件和目录,每个目录包含文件和目录,每个目录包含文件和目录......
sta*_*lue 34
在替代方法是显式管理堆栈时,递归可能会更快,就像您提到的排序或二叉树算法一样.
我有一个案例,用Java重写递归算法使它变慢.
因此,正确的方法是首先以最自然的方式编写它,只有在分析显示它是关键的时候进行优化,然后测量所谓的改进.
这里的大多数答案都忘记了为什么递归通常比迭代解决方案慢的明显罪魁祸首.它与堆栈帧的构建和拆除相关联,但并非如此.对于每次递归,自动变量的存储通常有很大差异.在具有循环的迭代算法中,变量通常保存在寄存器中,即使它们溢出,它们也将驻留在1级缓存中.在递归算法中,变量的所有中间状态都存储在堆栈中,这意味着它们会在内存中产生更多溢出.这意味着即使它进行相同数量的操作,它也会在热循环中进行大量内存访问,更糟糕的是,这些内存操作的重用率很低,使缓存效率降低.
TL; DR递归算法通常比迭代算法具有更差的缓存行为.
这里的大部分答案都是错误的.正确的答案取决于它.例如,这里有两个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在该堆栈上推送节点然后弹出和操作.
递归函数比迭代函数运行得快得多.原因是因为在后者中,对于每个项目,需要a CALL到函数st_push,然后是另一个st_pop.
在前者中,您只CALL对每个节点进行递归.
另外,访问callstack上的变量非常快.这意味着您正在从内存中读取,这可能始终位于最内层缓存中.另一方面,显式堆栈必须由malloc以下内容支持:来自堆的ed内存,访问速度要慢得多.
经过精心优化,如内联st_push和st_pop,我可以达到与递归方法大致均等.但至少在我的计算机上,访问堆内存的成本要高于递归调用的成本.
但是这种讨论大多没有实际意义,因为递归树行走是不正确的.如果你有足够大的树,你将用完callstack空间,这就是必须使用迭代算法的原因.
一般来说，不，在任何具有两种形式的可行实现的实际用法中，递归不会比循环更快。我的意思是，当然，您可以编写永远需要的循环，但是会有更好的方法来实现相同的循环，该循环可以优于通过递归实现相同问题的任何实现。
关于原因，你一语中的；创建和销毁堆栈帧比简单的跳转更昂贵。
但是，请注意我说“两种形式都有可行的实现”。对于像许多排序算法这样的事情，往往没有一种非常可行的方法来实现它们，而不能有效地建立自己的堆栈版本，因为子“任务”的产生本质上是该过程的一部分。因此，递归可能与尝试通过循环实现算法一样快。