如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?


当前回答

If the iterations are atomic and orders of magnitude more expensive than pushing a new stack frame and creating a new thread and you have multiple cores and your runtime environment can use all of them, then a recursive approach could yield a huge performance boost when combined with multithreading. If the average number of iterations is not predictable then it might be a good idea to use a thread pool which will control thread allocation and prevent your process from creating too many threads and hogging the system.

例如,在某些语言中,存在递归多线程归并排序实现。

但同样,多线程可以与循环而不是递归一起使用,因此这种组合的工作效果取决于更多因素,包括操作系统及其线程分配机制。

其他回答

Your performance deteriorates when using recursion because calling a method, in any language, implies a lot of preparation: the calling code posts a return address, call parameters, some other context information such as processor registers might be saved somewhere, and at return time the called method posts a return value which is then retrieved by the caller, and any context information that was previously saved will be restored. the performance diff between an iterative and a recursive approach lies in the time these operations take.

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

这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。

If the iterations are atomic and orders of magnitude more expensive than pushing a new stack frame and creating a new thread and you have multiple cores and your runtime environment can use all of them, then a recursive approach could yield a huge performance boost when combined with multithreading. If the average number of iterations is not predictable then it might be a good idea to use a thread pool which will control thread allocation and prevent your process from creating too many threads and hogging the system.

例如,在某些语言中,存在递归多线程归并排序实现。

但同样,多线程可以与循环而不是递归一起使用,因此这种组合的工作效果取决于更多因素,包括操作系统及其线程分配机制。

使用递归,每次“迭代”都会产生函数调用的成本,而使用循环,你通常只需要支付递增/递减的代价。因此,如果循环的代码并不比递归解决方案的代码复杂多少,循环通常会优于递归。

比较递归和迭代就像比较十字螺丝刀和一字螺丝刀。在大多数情况下,你可以拆卸任何一个平头的十字螺钉,但如果你使用专为该螺钉设计的螺丝刀,那就更容易了,对吧?

有些算法只是适合递归,因为它们的设计方式(斐波那契数列,遍历树状结构等)。递归使算法更简洁,更容易理解(因此可共享和可重用)。

此外,一些递归算法使用“惰性评估”,这使得它们比迭代算法更有效。这意味着它们只在需要的时候执行昂贵的计算,而不是每次循环运行时都执行。

这应该足够让你开始了。我也会给你找一些文章和例子。

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

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

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

链接2:掌握递归

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

递归编程为程序员提供了一种更好的组织方式 以一种既可维护又逻辑一致的方式编写代码。” https://developer.ibm.com/articles/l-recurs/

链接3:递归比循环快吗?(回答)

下面是一个与你的问题类似的stackoverflow问题的答案链接。作者指出,许多与递归或循环相关的基准测试都是特定于语言的。命令式语言通常使用循环更快,使用递归更慢,函数式语言反之亦然。我想从这个链接中得到的主要观点是,在语言不可知论/情境盲目的意义上回答这个问题是非常困难的。

递归比循环快吗?