递归或迭代？

我喜欢递归.我认为它简化了很多事情.另一个可能不同意; 我认为这也使代码更容易阅读.但是,我注意到递归在C#等语言中并没有像在LISP中那样被使用(顺便提一下,这是我最喜欢的语言).

有没有人知道是否有任何好的理由不使用C#等语言的递归？它比迭代更昂贵吗？

1> 1800 INFORMA..：

---

它们比迭代更昂贵吗？

对,他们是.许多Lisp变体支持"尾调用优化"的思想,它允许将递归函数调用的许多用法转换为迭代函数(这简化了一点).如果不支持tail-call,则递归函数调用将逐渐使用堆栈上的更多内存.

2> Aaron Maenpa..：

---

它们比迭代更昂贵吗？

对,他们是.递归需要创建一个新的堆栈帧以及调用和返回,而迭代通常只需要一个比较和分支,使其大大加快; 但是,编译器可以对某些递归调用(即尾调用)执行尾调用优化,这允许它们重用堆栈帧,使递归调用更便宜并有效地将它们转换为迭代.Scheme实际上要求方案编译器实现尾调用优化.

3> Scott Weinst..：

---

诸如Lisp和F#之类的函数语言可以在内部实现许多尾递归函数作为循环,并且能够避免函数调用的堆栈开销.虽然F#有,但C#不支持尾递归.

---

C＃没有指定它，但是底层的CLR包含尾部调用指令，因此这是一个合理的优化。注意：从.NET 2.0开始，尾部调用的速度比常规调用慢。

4> Robert Gould..：

---

编译器和现代CPU的体系结构可以通过迭代进行大量优化,而这些优化不能用于递归.例如,处理器执行乐观计算的能力.当处理器找到迭代空间时,它知道需要多长时间.从一开始,就没有必要在开始下一个循环之前每次检查.因此,他们管理运营.由于大多数CPU可以同时执行多个操作(通过流水线操作),因此可以在比递归更短的时间内解决迭代空间.这甚至是尾部优化,因为CPU实际上一次处理大约4个循环(对于x4性能增益).此增益取决于CPU的体系结构.该体系结构可能是增益的重要组成部分,下一代CPU将进一步推动增益.

递归的真正问题在于我们的硬件是基于VonNeumann的(图灵机可实现的变体),而不是Lisp机器,虽然有一些专门的Lisp硬件,你找不到任何桌面用它:)

---

我们需要获得有史以来最长的句子奖.;)

---

......最长的*可理解的*句子,至少.

---

我显然是一个文学怪人,完全展开那句话,哇.

5> Jeremy Edwar..：

---

使用递归有很多优点和缺点.绝对代码简单性是最大的一个,它也有助于提高代码的可维护性和减少错误.

递归的最大危险是边缘情况,算法旋转失控以打破函数堆栈限制.某些语言,Progress的ABL语言为1,具有允许的最高嵌套调用级别的参数.这些通常很低,并且在混合中添加递归可能会使应用程序中断该限制.

简而言之,递归应始终使用紧密终止案例来实现,否则调试非常困难(因为不可预测性)并且可能导致生产代码中的严重问题.

对于内存和速度的关注,除非这是一种方法本身很短(时间明智)被多次调用,所以性能是什么并不重要.

示例:如果使用递归扫描硬盘驱动器的所有文件和文件夹,则递归所产生的性能影响小到达到硬盘驱动器并获取文件系统信息所需的时间.在这种情况下,递归可能优于迭代处理.

另一个例子:如果你扫描树结构的节点,迭代过程可能更有益,因为我们没有涉及功能堆栈,这意味着我们打击更少的内存,可能让硬件使用更多的缓存.有关详细信息,请参阅Robert Gould的回复.

6> mfx..：

---

如果算法可以以递归形式最自然地表达,并且如果堆栈深度很小(在log(N)范围内,即通常<20),则通过任何方式使用递归.(由迭代引起的任何性能增益都是一个小的常数因子).

如果存在堆栈变大的危险,并且如果您的语言/编译器/运行时系统不保证尾调用优化,则应避免使用递归算法.