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


当前回答

递归可能会更昂贵,这取决于递归函数是否是尾部递归(最后一行是递归调用)。尾递归应该被编译器识别,并优化为迭代的对应部分(同时保持代码中简洁、清晰的实现)。

我将以最有意义的方式编写算法,并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题,那就分析你的代码,然后,只有在那之后,你才能通过迭代实现来进行优化。您可能需要研究一下内存和动态编程。

其他回答

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

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

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

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

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

递归比循环快吗?

递归和迭代取决于您想要实现的业务逻辑,尽管在大多数情况下可以互换使用。大多数开发人员选择递归,因为它更容易理解。

递归的内存开销更大,因为每次递归调用通常都需要将一个内存地址推入堆栈,以便稍后程序可以返回到那个地址。

尽管如此,在许多情况下,递归比循环更自然、更可读——比如在处理树的时候。在这些情况下,我建议坚持使用递归。

对于可以分解成多个更小的部分的问题,递归比迭代更好。

例如,要制作一个递归斐波那契算法,您将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)被计算了两次!

一个更好的例子是树的递归算法。分析父节点的问题可以分解为分析每个子节点的多个更小的问题。与斐波那契例子不同,较小的问题是相互独立的。

所以,对于那些可以分解成多个、更小、独立、相似问题的问题,递归比迭代更好。

递归?从哪里开始呢,维基会告诉你"这是以一种自相似的方式重复项目的过程"

在我做C语言的时候,c++的递归是上帝的恩赐,就像“尾递归”。您还会发现许多排序算法使用递归。快速排序示例:http://alienryderflex.com/quicksort/

递归就像任何其他算法一样,适用于特定的问题。也许你不能马上或经常找到一个用途,但会有问题,你会很高兴它可用。