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


当前回答

这取决于“递归深度”。 这取决于函数调用开销对总执行时间的影响程度。

例如,用递归的方式计算经典阶乘是非常低效的,因为: —数据溢出风险 -栈溢出风险 —函数调用开销占执行时间的80%

同时开发一种最小-最大算法用于国际象棋游戏中的位置分析,该算法将分析后续的N步棋,可以在“分析深度”上以递归方式实现(正如我正在做的^_^)

其他回答

这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。

据我所知,Perl没有优化尾递归调用,但是您可以伪造它。

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

第一次调用时,它将在堆栈上分配空间。然后它将改变它的参数,并重新启动子例程,而不向堆栈添加任何东西。因此,它会假装从未调用过自己,将其转变为一个迭代过程。

注意,没有“my @_;”或“local @_;”,如果你这样做,它将不再工作。

使用递归,每次“迭代”都会产生函数调用的成本,而使用循环,你通常只需要支付递增/递减的代价。因此,如果循环的代码并不比递归解决方案的代码复杂多少,循环通常会优于递归。

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

我认为在(非尾)递归中,每当函数被调用时,分配一个新的堆栈等都会受到性能影响(当然取决于语言)。