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


当前回答

堆栈溢出只会发生在编程语言没有内置内存管理....否则,请确保在函数(或函数调用、STDLbs等)中有一些内容。如果没有递归,就不可能有这样的东西……谷歌或SQL,或任何地方一个人必须有效地排序大型数据结构(类)或数据库。

如果你想要遍历文件,递归是一种方法,我敢肯定这就是find * | ?grep *的工作方式。有点像双重递归,特别是管道(但不要像很多人那样做一堆系统调用,如果你要把它放在那里供别人使用的话)。

高级语言,甚至clang/cpp也可以在后台实现相同的功能。

其他回答

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

我相信java中的尾递归目前还没有优化。关于LtU和相关链接的详细讨论贯穿始终。它可能是即将到来的版本7中的一个功能,但显然,当与堆栈检查结合使用时,它会出现一些困难,因为某些帧会丢失。自Java 2以来,堆栈检查一直用于实现他们的细粒度安全模型。

http://lambda-the-ultimate.org/node/1333

递归?从哪里开始呢,维基会告诉你"这是以一种自相似的方式重复项目的过程"

在我做C语言的时候,c++的递归是上帝的恩赐,就像“尾递归”。您还会发现许多排序算法使用递归。快速排序示例:http://alienryderflex.com/quicksort/

递归就像任何其他算法一样,适用于特定的问题。也许你不能马上或经常找到一个用途,但会有问题,你会很高兴它可用。

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

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

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

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

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

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

  }
}

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

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