为什么recursion比迭代更受欢迎？
迭代比recursion更高效，对吗？ 那么为什么有些人认为recursion比迭代更好（用他们的话来说更优雅）呢？ 我真的不明白为什么像Haskell这样的语言不允许迭代和鼓励recursion？ 鼓励那些性能不好的东西（而且当更多的高性能选项，即recursion可用时）也不是那么荒谬吗？ 请说明一下。 谢谢。
迭代比recursion更高效，对吗？
不必要。 这个概念来自许多类似C的语言，其中调用一个函数，recursion或不是，有一个大的开销，并为每个调用创build一个新的堆栈。
对于许多语言来说，情况并非如此，recursion与迭代版本相比，性能相当或更高。 现在，甚至一些C编译器都会将某些recursion结构重写为迭代版本，或者重复使用堆栈帧进行尾recursion调用。
尝试recursion地和迭代地实现深度优先search，并告诉我哪一个给你更容易的时间。 或合并sorting。 对于很多问题，都需要明确维护自己的堆栈，而不是将数据留在函数堆栈上。
我不能跟Haskell说话，因为我从来没有用过它，但是这是为了解决标题中提出的问题的更一般的部分。
Haskell不允许迭代，因为迭代涉及可变状态（索引）。
正如其他人所说的那样，对于recursion没有任何性能上的不足。 有些语言会比较慢，但这不是一个通用的规则。
这就是说，对我来说，recursion是一个工具，在有意义时使用。 有一些algorithm可以更好地表示为recursion（就像通过迭代更好一些）。
例如：
fib 0 = 0 fib 1 = 1 fib n = fib(n-1) + fib(n-2) 我无法想象一个反复的解决scheme，可能会使意图更清晰。
这里是关于recursion和迭代的优点和缺点的一些信息在c：
http://www.stanford.edu/~blp/writings/clc/recursion-vs-iteration.html
对我来说，recursion有时比迭代更容易理解。
迭代只是recursion的一种特殊forms。
几件事情：
- 迭代不一定更快
- 万恶的根源：仅仅因为它可能适中而鼓励一些东西是不成熟的。 还有其他的考虑。
- recursion往往更简洁明确地传达你的意图
- 一般来说，通过避免可变状态，函数式编程语言更容易推理和debugging，而recursion就是一个例子。
- recursion需要比迭代更多的内存。
我不认为对于recursion有什么本质上的不足 – 至less在抽象的问题上。 recursion是一种特殊的迭代forms。 如果一种语言被devise为很好地支持recursion，那么它就可能和迭代一样好。
一般来说，recursion使得我们可以清楚的知道你在下一次迭代中提出的状态（这是参数）。 这可以使语言处理器更容易并行执行。 至less这是语言devise者试图利用的一个方向。
在Java中，recursion解决scheme通常优于非recursion解决scheme。 在C中，它往往是相反的。 我认为这适用于自适应编译语言和提前编译语言。
编辑：“一般”我的意思是像60/40分裂。 这非常依赖于语言处理方法调用的效率。 我认为JIT编译有利于recursion，因为它可以select如何处理内联并在优化中使用运行时数据。 尽pipe如此，它依赖于algorithm和编译器。 特别是Java继续处理recursion更聪明。
用Java定量研究结果（PDF链接） 。 请注意，这些大多是sortingalgorithm，并使用较旧的Java虚拟机（1.5.x，如果我正确读取）。 通过使用recursion实现，他们有时可以获得2：1或4：1的性能提升，很lessrecursion显着变慢。 以我个人的经验来看，这种差异往往不是那么明显，但是当我明智地使用recursion时，常常有50％的提高。
recursion是理论上看起来优雅或高效的事情之一，但实际上效率不高（除非编译器或dynamic重新编译器）正在改变代码的function。 一般来说，导致不必要的子程序调用的任何事情都会变慢，特别是当超过1个参数被推/拉时。 任何你可以做的，以消除处理器周期，即处理器必须咀嚼的指令是公平的游戏。 一般来说，编译器可以做的很好，但是知道如何手工编写高效的代码总是很好的。
我认为这有助于理解什么是性能。 这个链接显示了一个完全合理编码的应用程序实际上有很大的优化空间， 即43的因素！ 这与迭代和recursion没有任何关系。
当一个应用程序已经调整到这个程度 ，它达到了迭代所节省的循环，而不是recursion可能实际上有所作为。
作为一个低级ITERATION处理CXregistry来计算循环，当然还有数据registry。 RECURSION不仅处理它还增加了对堆栈指针的引用，以保持之前调用的引用，然后如何返回。
我的大学老师告诉我，无论你用recursion做什么都可以用迭代和反之亦然，但是有时用迭代来做比迭代更简单（更优雅），但是在性能水平上最好使用迭代。
recursion是迭代的典型实现。 这只是一个较低的抽象级别（至less在Python中）：
class iterator(object): def __init__(self, max): self.count = 0 self.max = max def __iter__(self): return self # I believe this changes to __next__ in Python 3000 def next(self): if self.count == self.max: raise StopIteration else: self.count += 1 return self.count - 1 # At this level, iteration is the name of the game, but # in the implementation, recursion is clearly what's happening. for i in iterator(50): print(i)
我会比较recursion和爆炸：你可以很快达到很大的结果。 但是，如果你使用它没有注意，结果可能是灾难性的。
在这里计算斐波纳契数字的recursioncertificate了复杂性，给我留下了非常深刻的印象。 在这种情况下recursion的复杂度为O（（3/2）^ n），而迭代只是O（n）。 用c＃写的recursion计算n = 46需要半分钟！ 哇…
恕我直言recursion应该只用于实体适合recursion的性质（树，语法分析，…），而不是因为审美。 任何“神圣”的recursion代码的性能和资源消耗都需要仔细检查。
我觉得很难说一个人总是比另一个更好。
我正在开发一个需要在用户文件系统上进行后台工作的移动应用程序。 其中一个后台线程需要不时扫描整个文件系统，以便将更新后的数据保存到用户。 所以担心堆栈溢出，我写了一个迭代algorithm。 今天，我写了一个recursion的，为同一个工作。 令我惊讶的是，迭代algorithm更快：recursion – > 37s，迭代 – > 34s（处理完全相同的文件结构）。
recursion：
private long recursive(File rootFile, long counter) { long duration = 0; sendScanUpdateSignal(rootFile.getAbsolutePath()); if(rootFile.isDirectory()) { File[] files = getChildren(rootFile, MUSIC_FILE_FILTER); for(int i = 0; i < files.length; i++) { duration += recursive(files[i], counter); } if(duration != 0) { dhm.put(rootFile.getAbsolutePath(), duration); updateDurationInUI(rootFile.getAbsolutePath(), duration); } } else if(!rootFile.isDirectory() && checkExtension(rootFile.getAbsolutePath())) { duration = getDuration(rootFile); dhm.put(rootFile.getAbsolutePath(), getDuration(rootFile)); updateDurationInUI(rootFile.getAbsolutePath(), duration); } return counter + duration; }
迭代： – 迭代深度优先search，recursion回溯
private void traversal(File file) { int pointer = 0; File[] files; boolean hadMusic = false; long parentTimeCounter = 0; while(file != null) { sendScanUpdateSignal(file.getAbsolutePath()); try { Thread.sleep(Constants.THREADS_SLEEP_CONSTANTS.TRAVERSAL); } catch (InterruptedException e) { e.printStackTrace(); } files = getChildren(file, MUSIC_FILE_FILTER); if(!file.isDirectory() && checkExtension(file.getAbsolutePath())) { hadMusic = true; long duration = getDuration(file); parentTimeCounter = parentTimeCounter + duration; dhm.put(file.getAbsolutePath(), duration); updateDurationInUI(file.getAbsolutePath(), duration); } if(files != null && pointer < files.length) { file = getChildren(file,MUSIC_FILE_FILTER)[pointer]; } else if(files != null && pointer+1 < files.length) { file = files[pointer+1]; pointer++; } else { pointer=0; file = getNextSybling(file, hadMusic, parentTimeCounter); hadMusic = false; parentTimeCounter = 0; } } } private File getNextSybling(File file, boolean hadMusic, long timeCounter) { File result= null; //se o file é /mnt, para if(file.getAbsolutePath().compareTo(userSDBasePointer.getParentFile().getAbsolutePath()) == 0) { return result; } File parent = file.getParentFile(); long parentDuration = 0; if(hadMusic) { if(dhm.containsKey(parent.getAbsolutePath())) { long savedValue = dhm.get(parent.getAbsolutePath()); parentDuration = savedValue + timeCounter; } else { parentDuration = timeCounter; } dhm.put(parent.getAbsolutePath(), parentDuration); updateDurationInUI(parent.getAbsolutePath(), parentDuration); } //procura irmao seguinte File[] syblings = getChildren(parent,MUSIC_FILE_FILTER); for(int i = 0; i < syblings.length; i++) { if(syblings[i].getAbsolutePath().compareTo(file.getAbsolutePath())==0) { if(i+1 < syblings.length) { result = syblings[i+1]; } break; } } //backtracking - adiciona pai, se tiver filhos musica if(result == null) { result = getNextSybling(parent, hadMusic, parentDuration); } return result; }
当然这个迭代不是很优雅，但是尽pipe它的实现方式不够完善，但它仍然比recursion更快。 而且我更好地控制它，因为我不希望它全速运行，并且会让垃圾收集器更频繁地工作。
无论如何，我不会理所当然地认为一种方法比另一种方法更好，并且会回顾当前recursion的其他algorithm。 但至less从上面的两个algorithm中，迭代的将是最终产品中的一个。
迭代比recursion更高效，对吗？
是。
但是， 当您遇到一个完美映射到recursion数据结构的问题时，更好的解决scheme总是recursion的 。
如果你假装用迭代来解决这个问题，那么最终你会重新创build堆栈，并创build一个更加复杂和丑陋的代码，与优雅的recursion版本的代码相比。
也就是说， 迭代总是比recursion更快。 （在冯·诺依曼体系结构中），所以如果你总是使用recursion，那么即使在循环足够的情况下，你也要付出一定的代价。
recursion比循环更快吗？
“迭代比recursion更高效”实际上是语言和/或编译器特有的。 想到的情况是当编译器进行循环展开的时候。 如果你在这种情况下实现了一个recursion的解决scheme，那会比较慢。
这就是成为一个科学家（testing假设）和知道你的工具的成本。
在ntfs UNC最大path为32K
C：\ A \ B \ X \ C ….可以创build超过16K的文件夹…
但是你甚至不能用任何recursion方法来计算文件夹的数量，迟早都会给堆栈溢出。
只有一个良好的轻量级迭代代码应该用于专业扫描文件夹。
信不信，最顶级的杀毒软件无法扫描UNC文件夹的最大深度。
