如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
这取决于“递归深度”。 这取决于函数调用开销对总执行时间的影响程度。
例如,用递归的方式计算经典阶乘是非常低效的,因为: —数据溢出风险 -栈溢出风险 —函数调用开销占执行时间的80%
同时开发一种最小-最大算法用于国际象棋游戏中的位置分析,该算法将分析后续的N步棋,可以在“分析深度”上以递归方式实现(正如我正在做的^_^)
其他回答
据我所知,Perl没有优化尾递归调用,但是您可以伪造它。
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
第一次调用时,它将在堆栈上分配空间。然后它将改变它的参数,并重新启动子例程,而不向堆栈添加任何东西。因此,它会假装从未调用过自己,将其转变为一个迭代过程。
注意,没有“my @_;”或“local @_;”,如果你这样做,它将不再工作。
递归和迭代取决于您想要实现的业务逻辑,尽管在大多数情况下可以互换使用。大多数开发人员选择递归,因为它更容易理解。
这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。
递归在某些情况下非常有用。例如,考虑查找阶乘的代码
int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}
现在用递归函数来考虑这个问题
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
通过观察这两个,我们可以看到递归很容易理解。 但如果不小心使用,它也会很容易出错。 假设如果我们错过了if (input == 0),那么代码将执行一段时间,并以堆栈溢出结束。
在许多情况下,由于缓存提高了性能,递归更快。例如,这是一个使用传统归并例程的归并排序的迭代版本。它将比递归实现运行得慢,因为缓存改进了性能。
迭代实现
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上的算法课程上讲的。