递归或迭代？

如果我们在算法中使用循环而不是递归,反之亦然,那么两者是否可以起到同样的作用？例如:检查给定的字符串是否为回文.我已经看到许多程序员使用递归作为一种手段来展示一个简单的迭代算法可以适应账单.编译器在决定使用什么方面起着至关重要的作用吗？

循环可以为您的程序带来性能提升.递归可以为程序员带来性能提升.选择哪种更适合您的情况!

递归可能会更加昂贵,具体取决于递归函数是否为尾递归(最后一行是递归调用).尾部递归应该被编译器识别并针对其迭代对应物进行优化(同时保持代码中简洁明了的实现).

我会以最有意义的方式编写算法,并且对于那些必须在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)都是最清楚的.如果遇到性能问题,那么对代码进行概要分析,然后通过转移到迭代实现来查看优化.您可能希望查看memoization和动态编程.

将递归与迭代进行比较就像将十字头螺丝刀与平头螺丝刀进行比较一样.在大多数情况下,您可以卸下任何带平头的十字头螺钉,但如果您使用专为该螺钉设计的螺丝刀,那么它会更容易吗？

有些算法只是因为它们的设计方式(Fibonacci序列,遍历树状结构等)而适合递归.递归使算法更简洁,更易于理解(因此可共享和可重用).

此外,一些递归算法使用"懒惰评估",这使得它们比迭代兄弟更有效.这意味着它们只在需要时进行昂贵的计算,而不是每次循环运行时进行.

这应该足以让你开始.我也会为你挖掘一些文章和例子.

链接1: Haskel与PHP(递归与迭代)

下面是程序员必须使用PHP处理大型数据集的示例.他展示了使用递归在Haskel中处理是多么容易,但由于PHP没有简单的方法来完成相同的方法,他被迫使用迭代来获得结果.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

链接2:掌握递归

大多数递归的不良声誉来自命令式语言的高成本和低效率.本文作者讨论了如何优化递归算法以使其更快更有效.他还介绍了如何将传统循环转换为递归函数以及使用尾端递归的好处.他的结束语真的总结了我认为的一些关键点:

"递归编程为程序员提供了一种以可维护和逻辑一致的方式组织代码的更好方法."

http://www.ibm.com/developerworks/linux/library/l-recurs/index.html

链接3:递归是否比循环更快？(回答)

这是一个与您的类似的stackoverflow问题的答案的链接.作者指出,很多有两种递归或循环相关的基准是非常特定语言.使用循环的命令式语言通常更快,而递归则更慢,反之亦然.我想从这个链接中得出的主要观点是,在语言不可知/情境盲目的情况下回答这个问题非常困难.

递归比循环更快吗？

递归在内存中成本更高,因为每次递归调用通常都需要将内存地址推送到堆栈 - 以便稍后程序可以返回到该点.

尽管如此,在许多情况下递归比循环更自然和可读 - 就像使用树时一样.在这些情况下,我建议坚持递归.

通常,人们会期望性能损失处于另一个方向.递归调用可以导致额外堆栈帧的构建; 对此的处罚有所不同.此外,在某些语言(如Python(更准确地说,在某些语言的某些实现中))中,您可以轻松地对可能以递归方式指定的任务运行堆栈限制,例如在树数据结构中查找最大值.在这些情况下,你真的想坚持循环.

编写好的递归函数可以在一定程度上降低性能损失,假设你有一个优化尾递归的编译器等.(还要仔细检查以确保函数真的是尾递归的 - 这是许多人犯错的事情之一上.)

除了"边缘"情况(高性能计算,非常大的递归深度等)之外,最好采用最清楚地表达您的意图,设计良好且可维护的方法.仅在确定需求后才进行优化.

对于可以分解为多个较小块的问题,递归优于迭代.

例如,要制作递归Fibonnaci算法,将fib(n)分解为fib(n-1)和fib(n-2)并计算两个部分.迭代只允许您一遍又一遍地重复单个函数.

然而,Fibonacci实际上是一个破碎的例子,我认为迭代实际上更有效.注意,fib(n)= fib(n-1)+ fib(n-2)和fib(n-1)= fib(n-2)+ fib(n-3).fib(n-1)计算两次!

一个更好的例子是树的递归算法.分析父节点的问题可以分解为分析每个子节点的多个较小问题.与Fibonacci示例不同,较小的问题彼此独立.

所以是的 - 对于可以分解为多个,更小,独立,类似问题的问题,递归优于迭代.

使用递归时性能会下降,因为调用任何语言的方法都需要进行大量准备:调用代码发布返回地址,调用参数,其他一些上下文信息(如处理器寄存器)可能会保存在某处,并且在返回时被调用的方法发布一个返回值,然后由调用者检索该返回值,并且将恢复先前保存的任何上下文信息.迭代和递归方法之间的性能差异在于这些操作所花费的时间.

从实现的角度来看,当处理调用上下文所花费的时间与您的方法执行所花费的时间相当时,您真正开始注意到差异.如果您的递归方法需要更长的时间来执行,那么调用上下文管理部分,采用递归方式,因为代码通常更易读且易于理解,您不会注意到性能损失.否则,出于效率原因进行迭代.

我相信java中的尾递归目前尚未优化.细节贯穿洒这在LTU和相关链接的讨论.它可能是即将发布的版本7中的一个功能,但显然当与Stack Inspection结合使用时会出现某些困难,因为某些帧会丢失.自Java 2以来,Stack Inspection已被用于实现其细粒度的安全模型.

http://lambda-the-ultimate.org/node/1333

在许多情况下,它为迭代方法提供了更优雅的解决方案,常见的例子是遍历二叉树,因此维护不一定更困难.通常,迭代版本通常更快一些(并且在优化期间可能很好地替换递归版本),但递归版本更容易理解和正确实现.

在某些情况下,递归非常有用.例如,考虑寻找阶乘的代码

int factorial ( int input )
{
  int x, fact = 1;
  for ( x = input; x > 1; x--)
     fact *= x;
  return fact;
}

int factorial ( int input )
{
  if (input == 0)
  {
     return 1;
  }
  return input * factorial(input - 1);
}

public static void sort(Comparable[] a)
{
    int N = a.length;
    aux = new Comparable[N];
    for (int sz = 1; sz < N; sz = sz+sz)
        for (int lo = 0; lo < N-sz; lo += sz+sz)
            merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid+1, hi);
    merge(a, aux, lo, mid, hi);
}