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


当前回答

我将通过“归纳”设计一个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

其他回答

在很多情况下,它提供了比迭代方法更优雅的解决方案,常见的例子是遍历二叉树,所以它不一定更难维护。一般来说,迭代版本通常更快一些(在优化过程中可能会取代递归版本),但递归版本更容易理解和正确实现。

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

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

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

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

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

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

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.

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

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