为什么递归优先于迭代？

迭代比递归更高效,对吧？那么为什么有些人认为递归比迭代更好(用他们的话来说更优雅)？我真的不明白为什么像Haskell这样的语言不允许迭代并鼓励递归？鼓励表现不佳的东西是不是很荒谬(当更高性能的选项即递归可用时也是如此)？请详细说明一下.谢谢.

1> nos..：

---

迭代比递归更高效,对吧？

不必要.这个概念来自许多类C语言,其中调用函数,递归与否,具有很大的开销并为每个调用创建一个新的堆栈帧.

对于许多语言而言并非如此,并且递归与迭代版本相同或更高性能.这些天,即使是一些C编译器也会将一些递归构造重写为迭代版本,或者重复使用堆栈帧进行尾递归调用.

---

在真机上,迭代更好.有些语言是为真正的机器编写的,有些语言是你为假想的机器编写的,而不是真的,然后翻译你的代码以获得背后真实机器的好处,将递归转换为迭代.除非有时翻译不完美,然后你会注意到,因为你的表现有所下降.:)

---

+1:不,迭代不会轻易获得更高的性能.

2> danben..：

---

尝试递归和迭代地实现深度优先搜索并告诉我哪一个给你一个更容易的时间.或合并排序.对于很多问题,它归结为显式维护自己的堆栈而不是将数据留在函数堆栈上.

我不能和Haskell说话,因为我从未使用它,但这是为了解决你标题中提出的问题的更一般部分.

---

+1用于将手动管理的堆栈与函数调用堆栈进行比较.我从来没有这么想过.

3> kennytm..：

---

Haskell不允许迭代,因为迭代涉及可变状态(索引).

---

@James McMahon - 不,那绝对不是可变状态.堆栈帧不共享数据; 他们每个人都有自己的副本.

---

这是假设haskell为递归调用构建堆栈帧.

---

@James McMahon:与线程没什么关系.堆栈帧是语言本身的实现细节.它更简单:你的代码不能改变状态.

---

@James McMahon:不,即使在一个帖子中它也是不可变的.请记住,单个线程可以有许多堆栈帧(每个函数调用一个尚未返回).它们中的每一个都有自己的一组数据,这些数据无法从任何其他函数的主体访问.

4> RHSeeger..：

---

正如其他人所说的那样,递归的本质上没有什么特别之处.有些语言会慢一些,但这不是一个普遍的规则.

话虽如此,对我而言,递归是一种工具,在有意义时使用.有些算法更好地表示为递归(正如一些通过迭代更好).

例证:

fib 0 = 0
fib 1 = 1
fib n = fib(n-1) + fib(n-2)

我无法想象一个迭代解决方案可能会使意图更清晰.

---

真？Downvoted是因为创建示例以显示递归如何更清晰是低效的？哇.我想我会指出,至少有些语言会在引擎盖下自动进行记忆,特别是那些递归是预期的做事方式的功能.

---

除非你在引擎盖下有一些记忆,否则这是一个指数时间算法.没有多少清晰度和可读性可以为这种极端低效率提供借口.

5> John Boker..：

---

这里有一些关于c中递归和迭代的优缺点的信息:

http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html

对我来说主要是递归有时比迭代更容易理解.