如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。
其他回答
递归的内存开销更大,因为每次递归调用通常都需要将一个内存地址推入堆栈,以便稍后程序可以返回到那个地址。
尽管如此,在许多情况下,递归比循环更自然、更可读——比如在处理树的时候。在这些情况下,我建议坚持使用递归。
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.
例如,在某些语言中,存在递归多线程归并排序实现。
但同样,多线程可以与循环而不是递归一起使用,因此这种组合的工作效果取决于更多因素,包括操作系统及其线程分配机制。
这取决于语言。在Java中,你应该使用循环。函数式语言优化递归。
使用递归,每次“迭代”都会产生函数调用的成本,而使用循环,你通常只需要支付递增/递减的代价。因此,如果循环的代码并不比递归解决方案的代码复杂多少,循环通常会优于递归。
递归比迭代的任何可能定义都更简单(因此也更基本)。你可以只用一对组合子定义一个图灵完备系统(是的,在这样的系统中,甚至递归本身也是一个衍生概念)。Lambda演算是一个同样强大的基本系统,具有递归函数。但是如果你想正确地定义一个迭代,你需要更多的原语来开始。
至于代码——不,递归代码实际上比纯迭代代码更容易理解和维护,因为大多数数据结构都是递归的。当然,为了正确使用它,至少需要一种支持高阶函数和闭包的语言,以简洁的方式获得所有标准的组合子和迭代器。当然,在c++中,复杂的递归解决方案可能看起来有点丑,除非你是fc++的铁杆用户。