如果我们使用循环而不是递归,或者反之,在两者都可以达到相同目的的算法中,性能是否会受到影响?检查给定的字符串是否是回文。 我见过许多程序员使用递归作为一种炫耀的手段,当一个简单的迭代算法可以满足要求。 编译器在决定使用什么时起着至关重要的作用吗?
当前回答
递归比迭代的任何可能定义都更简单(因此也更基本)。你可以只用一对组合子定义一个图灵完备系统(是的,在这样的系统中,甚至递归本身也是一个衍生概念)。Lambda演算是一个同样强大的基本系统,具有递归函数。但是如果你想正确地定义一个迭代,你需要更多的原语来开始。
至于代码——不,递归代码实际上比纯迭代代码更容易理解和维护,因为大多数数据结构都是递归的。当然,为了正确使用它,至少需要一种支持高阶函数和闭包的语言,以简洁的方式获得所有标准的组合子和迭代器。当然,在c++中,复杂的递归解决方案可能看起来有点丑,除非你是fc++的铁杆用户。
其他回答
递归和迭代取决于您想要实现的业务逻辑,尽管在大多数情况下可以互换使用。大多数开发人员选择递归,因为它更容易理解。
递归可能会更昂贵,这取决于递归函数是否是尾部递归(最后一行是递归调用)。尾递归应该被编译器识别,并优化为迭代的对应部分(同时保持代码中简洁、清晰的实现)。
我将以最有意义的方式编写算法,并且对那些不得不在几个月或几年内维护代码的可怜的傻瓜(无论是你自己还是其他人)来说是最清楚的。如果你遇到了性能问题,那就分析你的代码,然后,只有在那之后,你才能通过迭代实现来进行优化。您可能需要研究一下内存和动态编程。
递归?从哪里开始呢,维基会告诉你"这是以一种自相似的方式重复项目的过程"
在我做C语言的时候,c++的递归是上帝的恩赐,就像“尾递归”。您还会发现许多排序算法使用递归。快速排序示例:http://alienryderflex.com/quicksort/
递归就像任何其他算法一样,适用于特定的问题。也许你不能马上或经常找到一个用途,但会有问题,你会很高兴它可用。
迈克说得对。Java编译器或JVM没有优化尾部递归。你总是会得到这样的堆栈溢出:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
递归比迭代的任何可能定义都更简单(因此也更基本)。你可以只用一对组合子定义一个图灵完备系统(是的,在这样的系统中,甚至递归本身也是一个衍生概念)。Lambda演算是一个同样强大的基本系统,具有递归函数。但是如果你想正确地定义一个迭代,你需要更多的原语来开始。
至于代码——不,递归代码实际上比纯迭代代码更容易理解和维护,因为大多数数据结构都是递归的。当然,为了正确使用它,至少需要一种支持高阶函数和闭包的语言,以简洁的方式获得所有标准的组合子和迭代器。当然,在c++中,复杂的递归解决方案可能看起来有点丑,除非你是fc++的铁杆用户。