如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
我认为在(非尾)递归中,每当函数被调用时,分配一个新的堆栈等都会受到性能影响(当然取决于语言)。
其他回答
对于可以分解成多个更小的部分的问题,递归比迭代更好。
例如,要制作一个递归斐波那契算法,您将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)被计算了两次!
一个更好的例子是树的递归算法。分析父节点的问题可以分解为分析每个子节点的多个更小的问题。与斐波那契例子不同,较小的问题是相互独立的。
所以,对于那些可以分解成多个、更小、独立、相似问题的问题,递归比迭代更好。
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获得的。英特尔编译器也显示了类似的结果。
你必须记住,使用太深的递归,你会遇到堆栈溢出,这取决于允许的堆栈大小。为了防止这种情况,请确保提供一些基本情况,以结束递归。
通常情况下,人们会期望性能损失在另一个方向上。递归调用会导致构建额外的堆栈帧;对此的惩罚各不相同。此外,在一些语言中,如Python(更准确地说,是在某些语言的某些实现中……),对于递归指定的任务,您可能很容易遇到堆栈限制,例如在树状数据结构中查找最大值。在这些情况下,你应该坚持使用循环。
编写好的递归函数可以在一定程度上降低性能损失,前提是你有一个优化尾部递归的编译器,等等(还要再次检查,确保函数真的是尾部递归——这是许多人都会犯的错误之一)。
除了“边缘”情况(高性能计算、非常大的递归深度等)之外,最好采用最清楚地表达您的意图、设计良好且可维护的方法。仅在确定需求后进行优化。
我将通过“归纳”设计一个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