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


当前回答

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

其他回答

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

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

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

通常情况下,人们会期望性能损失在另一个方向上。递归调用会导致构建额外的堆栈帧;对此的惩罚各不相同。此外,在一些语言中,如Python(更准确地说,是在某些语言的某些实现中……),对于递归指定的任务,您可能很容易遇到堆栈限制,例如在树状数据结构中查找最大值。在这些情况下,你应该坚持使用循环。

编写好的递归函数可以在一定程度上降低性能损失,前提是你有一个优化尾部递归的编译器,等等(还要再次检查,确保函数真的是尾部递归——这是许多人都会犯的错误之一)。

除了“边缘”情况(高性能计算、非常大的递归深度等)之外,最好采用最清楚地表达您的意图、设计良好且可维护的方法。仅在确定需求后进行优化。

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

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

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

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

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

  }
}

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

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

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