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


当前回答

循环可以提高程序的性能。递归可以为程序员带来性能上的提升。在你的情况下,选择哪个更重要!

其他回答

递归可能会更昂贵,这取决于递归函数是否是尾部递归(最后一行是递归调用)。尾递归应该被编译器识别,并优化为迭代的对应部分(同时保持代码中简洁、清晰的实现)。

我将以最有意义的方式编写算法,并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题,那就分析你的代码,然后,只有在那之后,你才能通过迭代实现来进行优化。您可能需要研究一下内存和动态编程。

在很多情况下,它提供了比迭代方法更优雅的解决方案,常见的例子是遍历二叉树,所以它不一定更难维护。一般来说,迭代版本通常更快一些(在优化过程中可能会取代递归版本),但递归版本更容易理解和正确实现。

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

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

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

If the iterations are atomic and orders of magnitude more expensive than pushing a new stack frame and creating a new thread and you have multiple cores and your runtime environment can use all of them, then a recursive approach could yield a huge performance boost when combined with multithreading. If the average number of iterations is not predictable then it might be a good idea to use a thread pool which will control thread allocation and prevent your process from creating too many threads and hogging the system.

例如,在某些语言中,存在递归多线程归并排序实现。

但同样,多线程可以与循环而不是递归一起使用,因此这种组合的工作效果取决于更多因素,包括操作系统及其线程分配机制。