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


当前回答

In C++ if the recursive function is a templated one, then the compiler has more chance to optimize it, as all the type deduction and function instantiations will occur in compile time. Modern compilers can also inline the function if possible. So if one uses optimization flags like -O3 or -O2 in g++, then recursions may have the chance to be faster than iterations. In iterative codes, the compiler gets less chance to optimize it, as it is already in the more or less optimal state (if written well enough).

在我的例子中,我试图通过使用Armadillo矩阵对象,以递归和迭代的方式来实现矩阵求幂。算法可以在这里找到…https://en.wikipedia.org/wiki/Exponentiation_by_squaring。 我的函数是模板化的,我已经计算了1,000,000个12x12矩阵的10次方。我得到了以下结果:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

这些结果是使用gcc-4.8与c++11标志(-std=c++11)和Armadillo 6.1与Intel mkl获得的。英特尔编译器也显示了类似的结果。

其他回答

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

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

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

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

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

递归比循环快吗?

通常情况下,人们会期望性能损失在另一个方向上。递归调用会导致构建额外的堆栈帧;对此的惩罚各不相同。此外,在一些语言中,如Python(更准确地说,是在某些语言的某些实现中……),对于递归指定的任务,您可能很容易遇到堆栈限制,例如在树状数据结构中查找最大值。在这些情况下,你应该坚持使用循环。

编写好的递归函数可以在一定程度上降低性能损失,前提是你有一个优化尾部递归的编译器,等等(还要再次检查,确保函数真的是尾部递归——这是许多人都会犯的错误之一)。

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

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

你必须记住,使用太深的递归,你会遇到堆栈溢出,这取决于允许的堆栈大小。为了防止这种情况,请确保提供一些基本情况,以结束递归。

In C++ if the recursive function is a templated one, then the compiler has more chance to optimize it, as all the type deduction and function instantiations will occur in compile time. Modern compilers can also inline the function if possible. So if one uses optimization flags like -O3 or -O2 in g++, then recursions may have the chance to be faster than iterations. In iterative codes, the compiler gets less chance to optimize it, as it is already in the more or less optimal state (if written well enough).

在我的例子中,我试图通过使用Armadillo矩阵对象,以递归和迭代的方式来实现矩阵求幂。算法可以在这里找到…https://en.wikipedia.org/wiki/Exponentiation_by_squaring。 我的函数是模板化的,我已经计算了1,000,000个12x12矩阵的10次方。我得到了以下结果:

iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec

iterative + No-optimisation flag  -> 2.83.. sec
recursive + No-optimisation flag  -> 4.15.. sec

这些结果是使用gcc-4.8与c++11标志(-std=c++11)和Armadillo 6.1与Intel mkl获得的。英特尔编译器也显示了类似的结果。