如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
据我所知,Perl没有优化尾递归调用,但是您可以伪造它。
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
第一次调用时,它将在堆栈上分配空间。然后它将改变它的参数,并重新启动子例程,而不向堆栈添加任何东西。因此,它会假装从未调用过自己,将其转变为一个迭代过程。
注意,没有“my @_;”或“local @_;”,如果你这样做,它将不再工作。
其他回答
递归可能会更昂贵,这取决于递归函数是否是尾部递归(最后一行是递归调用)。尾递归应该被编译器识别,并优化为迭代的对应部分(同时保持代码中简洁、清晰的实现)。
我将以最有意义的方式编写算法,并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题,那就分析你的代码,然后,只有在那之后,你才能通过迭代实现来进行优化。您可能需要研究一下内存和动态编程。
这取决于“递归深度”。 这取决于函数调用开销对总执行时间的影响程度。
例如,用递归的方式计算经典阶乘是非常低效的,因为: —数据溢出风险 -栈溢出风险 —函数调用开销占执行时间的80%
同时开发一种最小-最大算法用于国际象棋游戏中的位置分析,该算法将分析后续的N步棋,可以在“分析深度”上以递归方式实现(正如我正在做的^_^)
我将通过“归纳”设计一个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
在许多情况下,由于缓存提高了性能,递归更快。例如,这是一个使用传统归并例程的归并排序的迭代版本。它将比递归实现运行得慢,因为缓存改进了性能。
迭代实现
public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
递归实现
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
PS -这是Kevin Wayne教授(普林斯顿大学)在Coursera上的算法课程上讲的。
在很多情况下,它提供了比迭代方法更优雅的解决方案,常见的例子是遍历二叉树,所以它不一定更难维护。一般来说,迭代版本通常更快一些(在优化过程中可能会取代递归版本),但递归版本更容易理解和正确实现。