递归比循环快吗?

这取决于所使用的语言。你写了“语言不可知论”,所以我举几个例子。

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

有时 需要一些相对繁重的操作,特别是在支持多线程执行的实现上。在其中一些环境中,由于mutator和垃圾收集器之间的交互作用(如果两者可能同时运行的话),所以变异是昂贵的。

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

可以 快点。如果您使用的是命令式语言,那么迭代就是 可能 更快。在某些环境中,这两种方法都会生成相同的程序集(将其放入管道并冒烟)。

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

列表理解是另一种选择,但它们通常只是迭代、递归或更高阶函数的语法糖。

递归比循环快吗?

迭代总是比递归快(在冯·诺依曼建筑中)

如果你从零开始构建一个通用计算机的最小操作,“迭代”首先作为一个构建块出现,并且比“递归”占用更少的资源,因此ergo更快。

从头开始构建伪计算机:

扪心自问 :您需要做什么 计算 一个值,即遵循一个算法并得到一个结果?

我们将建立一个概念层次,从零开始,首先定义基本的、核心的概念,然后用这些概念建立第二层次的概念,以此类推。

1. 第一个概念: . 做你需要的事 存储最终和中间结果值。假设我们有一个“整数”单元的无限数组,称为 记忆 ,M[0..Infinite]。

2. 说明: . 每个有趣的指令都执行一个转换。基本说明如下:

   设置(&A);移动存储单元

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

   (二)

   • 添加、sub、mul、div.例如。 加m[7]m[8]

3. 执行代理人 核心 代理人 也可以是一个人按照纸上的算法。

4. 步骤顺序:一系列指令 步骤 . 这意味着,即使是单个组合表达式,也有隐式的步骤和隐式的局部变量(我们称之为result)。例如。:

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

   上面的表达式用一个隐式的“result”变量表示3个步骤。

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

   所以即使是中缀表达式,因为有一个特定的求值顺序,也是 . 表达式 暗示 按特定顺序进行的一系列操作,因为 步骤 ,还有一个隐式的“result”中间变量。

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

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

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. 一级子程序 :假设需要频繁执行一系列步骤。您可以将这些步骤存储在内存中的指定位置,然后 跳到 到了 继续执行。有了这个机制,你 创建新指令 (子程序)通过编写核心指令。

    • 将当前指令指针存储在预定义的内存位置
    • 跳
    • 在子例程结束时,从预定义的内存位置检索指令指针,有效地跳回原始的以下指令 呼叫

    问题在于 一级

    有一个

12. 堆叠 堆栈指针 (类似于指令指针),它指向堆栈的实际头部。当您按下一个值时,堆栈指针递减,然后您存储该值。当您弹出时,您将在实际堆栈指针处获得值,然后堆栈指针将递增。

13. 堆栈 堆栈 呼叫 新指令 作为子例程,使用核心指令或其他子例程作为构建块。

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

    问题: 如果 中间结果存储在预定义的内存位置(全局变量)中,它们将在嵌套调用中被覆盖。

    为了允许递归,子例程应该存储本地中间结果 在堆栈中 递归调用 (直接或间接)中间结果存储在不同的存储位置。

递归

在冯·诺依曼的建筑里,显然 “迭代” “递归” . 我们有一种 “迭代” 位于概念层次结构的14级。

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

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

建议

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

因此,正确的方法是首先以最自然的方式编写它,只有在概要分析显示它是关键的情况下才进行优化,然后度量假定的改进。

Tail recursion 就像循环一样快。许多函数语言都实现了尾部递归。

考虑一下每次迭代和递归都必须做些什么。

• 递归:跳转到被调用函数的开头

你看这里没有多大的分歧余地。

(我假设递归是一个尾部调用,编译器知道这种优化)。

这里的大多数答案都忘记了一个明显的罪魁祸首:为什么递归常常比迭代解慢。它与堆栈帧的建立和分解有关,但并不完全是这样。对于每个递归,自动变量的存储通常有很大的不同。在带有循环的迭代算法中,变量通常保存在寄存器中,即使它们溢出,它们也将驻留在1级缓存中。在递归算法中,变量的所有中间状态都存储在堆栈中,这意味着它们将产生更多溢出到内存中。这意味着即使它进行相同数量的操作,它在热循环中也会有大量的内存访问,更糟糕的是,这些内存操作的重用率很低,使得缓存的效率降低。

热释光;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 将节点推送到这些节点上,然后弹出并操纵它们。

递归函数比迭代函数运行得快得多。原因是在后者中,对于每个项目 CALL 到函数 st_push 是需要的,然后是另一个 st_pop

在前者中,只有递归的 呼叫

另外,访问callstack上的变量速度非常快。这意味着您正在从内存中读取数据,而内存可能总是位于最内部的缓存中。另一方面,显式堆栈必须有 malloc :从堆中删除了访问速度慢得多的内存。

通过仔细的优化,比如内联 推送 和 ,我可以用递归方法大致达到奇偶校验。但至少在我的计算机上,访问堆内存的开销要比递归调用的开销大。

但是这个讨论主要是没有意义的,因为递归树遍历是 . 如果你有一个足够大的树,你将用完callstack空间,这就是为什么必须使用迭代算法。

一般来说,不,递归不会比在两种形式中都有可行实现的任何实际用法中的循环快。我的意思是,当然,你可以编写一个循环,这需要很长时间,但是有更好的方法来实现同一个循环,它可以比任何通过递归实现同一个问题的方法都要好。

不过,请注意,我说过“两种形式都有可行的实现”。对于像许多排序算法这样的事情,往往没有一种非常可行的实现方法,无法有效地设置自己版本的堆栈,因为子“任务”是流程的固有部分。因此,递归可能与尝试通过循环实现算法一样快。

真的,真的

函数式编程更多的是关于 什么 “而不是” ".

语言实现者将找到一种优化代码底层工作方式的方法,如果我们不尝试使其比需要的更优化的话。递归也可以在支持尾部调用优化的语言中进行优化。

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

这只是猜测。一般来说,递归在规模相当的问题上可能不会经常或曾经击败循环,如果两者都使用非常好的算法(不算实现难度),如果与w语言一起使用,则可能会有所不同/ tail call 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;
  }