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


当前回答

堆栈溢出只会发生在编程语言没有内置内存管理....否则,请确保在函数(或函数调用、STDLbs等)中有一些内容。如果没有递归,就不可能有这样的东西……谷歌或SQL,或任何地方一个人必须有效地排序大型数据结构(类)或数据库。

如果你想要遍历文件,递归是一种方法,我敢肯定这就是find * | ?grep *的工作方式。有点像双重递归,特别是管道(但不要像很多人那样做一堆系统调用,如果你要把它放在那里供别人使用的话)。

高级语言,甚至clang/cpp也可以在后台实现相同的功能。

其他回答

我相信java中的尾递归目前还没有优化。关于LtU和相关链接的详细讨论贯穿始终。它可能是即将到来的版本7中的一个功能,但显然,当与堆栈检查结合使用时,它会出现一些困难,因为某些帧会丢失。自Java 2以来,堆栈检查一直用于实现他们的细粒度安全模型。

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

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

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

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

循环可以提高程序的性能。递归可以为程序员带来性能上的提升。在你的情况下,选择哪个更重要!

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

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

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

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

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

递归比循环快吗?

我将通过“归纳”设计一个Haskell数据结构来回答你的问题,这是递归的一种“对偶”。然后我会展示这种对偶性是如何带来好的结果的。

我们为简单树引入一个类型:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

我们可以把这个定义理解为“一棵树是一个分支(包含两棵树)或一个叶子(包含一个数据值)”。叶结点是一种最小的情况。如果树不是叶子,那么它一定是包含两棵树的复合树。这些是唯一的例子。

让我们做一个树:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

现在,让我们假设我们想给树中的每个值加1。我们可以通过调用:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

首先,请注意这实际上是一个递归定义。它将数据构造函数Branch和Leaf作为case(因为Leaf是最小值的,这是唯一可能的case),我们可以确定函数将终止。

用迭代风格编写addOne需要什么?循环进入任意数量的分支会是什么样子?

此外,这种递归通常可以用“函子”来分解。我们可以通过定义将树变成函子:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

和定义:

addOne' = fmap (+1)

我们可以提出其他递归方案,例如代数数据类型的变形(或折叠)。使用变形法,我们可以这样写:

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b