recursion或迭代？
如果我们使用循环代替recursion，反之亦然，在两者都可以达到相同目的的algorithm中，性能是否会受到影响？ 例如：检查给定的string是否是回文。 我已经看到许多程序员使用recursion作为一种手段来炫耀，当一个简单的迭代algorithm可以适应账单。 编译器在决定使用什么时起到至关重要的作用？
recursion可能会更加昂贵，这取决于recursion函数是否是recursion函数（最后一行是recursion调用）。 尾recursion应该被编译器识别，并且对迭代对象进行优化（同时保持代码中简洁清晰的实现）。
我会以最有意义的方式编写algorithm，对于那些不得不在几个月或几年内维护代码的穷人（无论是你自己还是其他人）来说，这是最明确的。 如果遇到性能问题，那么对代码进行剖析，然后只有通过转向迭代实现来查看优化。 您可能想要查看记忆和dynamic编程 。
循环可能会为您的程序获得性能提升。 recursion可能会为您的程序员带来性能上的提升。 select哪一个在你的情况下更重要！
比较recursion和迭代就像比较一把十字螺丝刀和一个平头螺丝刀。 大多数情况下，您可以用扁头去除任何菲利普斯头螺钉，但如果您使用专为该螺钉devise的螺丝刀，它会更容易？
一些algorithm因为它们被devise的方式（斐波那契数列，遍历树状结构等等）而适用于recursion。 recursion使algorithm更简洁，更容易理解（因此可共享和可重用）。
此外，一些recursionalgorithm使用“懒惰评估”，使他们比他们的迭代兄弟更有效率。 这意味着他们只需要在需要时进行昂贵的计算，而不是每次循环运行。
这应该足以让你开始。 我会为你挖掘一些文章和例子。
链接1： Haskel与PHP（recursion与迭代）
这是一个程序员必须使用PHP来处理大型数据集的例子。 他显示了使用recursion在Haskel中处理是多么容易，但是由于PHP没有简单的方法来完成相同的方法，他不得不使用迭代来得到结果。
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
链接2：掌握recursion
大多数recursion的不良声誉来自命令式语言的高成本和低效率。 本文的作者讨论了如何优化recursionalgorithm，使其更快，更高效。 他还介绍了如何将传统的循环转换为recursion函数以及使用尾端recursion的好处。 他的结语真的总结了我的一些重点：
“recursion编程为程序员提供了一种更好的方式来组织代码，这种方式既可维护又逻辑一致。”
http://www.ibm.com/developerworks/linux/library/l-recurs/index.html
链接3：recursion比循环更快吗？ （回答）
这里是一个链接到一个类似于你的一个stackoverflow问题的答案。 作者指出，许多与recursion或循环相关的基准都是非常特定于语言的。 命令式语言通常使用循环更快，recursion速度更慢，function语言反之亦然。 我认为从这个环节中得出的主要观点是，在语言不可知或情境盲目的情况下回答这个问题是非常困难的。
recursion比循环更快吗？
recursion在内存中成本更高，因为每次recursion调用通常需要将内存地址推送到堆栈，以便稍后程序可以返回到该点。
尽pipe如此，很多情况下recursion比循环更加自然和可读，就像处理树时一样。 在这些情况下，我会build议坚持recursion。
通常，人们会认为性能损失是在另一个方向上。 recursion调用可能会导致构build额外的堆栈帧; 对此的惩罚各不相同。 另外，在一些像Python这样的语言中（更准确的说，在某些语言的某些实现中…），对于可以recursion指定的任务（例如在树数据结构中查找最大值），可以轻松地运行堆栈限制。 在这些情况下，你真的想坚持循环。
编写好的recursion函数可以在某种程度上减less性能损失，假设你有一个编译器来优化尾recursion等等。（同时仔细检查一下，确保函数真的是尾recursion – 这是许多人犯错的东西之一上。）
除了“边缘”情况（高性能计算，非常大的recursion深度等）外，最好采用最清晰expression意图，devise良好，可维护的方法。 只有在确定需求之后才进行优化。
对于可以分解成多个小块的问题，recursion优于迭代。
例如，要制作recursionFibonnacialgorithm，可以将fib（n）分解为fib（n-1）和fib（n-2）并计算这两个部分。 迭代只允许你重复一遍又一遍的单个函数。
然而，斐波那契实际上是一个破碎的例子，我认为迭代实际上更有效率。 注意fib（n）= fib（n-1）+ fib（n-2）和fib（n-1）= fib（n-2）+ fib（n-3）。 fib（n-1）计算两次！
一个更好的例子是树的recursionalgorithm。 分析父节点的问题可以分解成多个分析每个子节点的较小问题。 与斐波那契的例子不同，较小的问题是彼此独立的。
所以耶 – recursion比迭代可以分解成多个，更小，独立，相似的问题更好。
使用recursion时，性能会下降，因为调用任何语言的方法都意味着大量的准备工作：调用代码发布返回地址，调用参数，其他一些上下文信息（如处理器寄存器）可能会保存在某个地方，所谓的方法发布一个返回值，然后由调用者检索，并且之前保存的任何上下文信息将被恢复。 迭代和recursion方法之间的性能差异在于这些操作所花费的时间。
从实现的angular度来看，当处理调用上下文所花费的时间与您的方法执行所花费的时间相差无几时，您才会开始注意到差异。 如果你的recursion方法需要更长的时间来执行，然后调用上下文pipe理部分，去recursion的方式，因为代码通常更易读易懂，你不会注意到性能的损失。 否则为了效率的原因进行迭代。
我相信在java中的尾recursion目前还没有优化。 在关于LtU和相关链接的讨论中，详细描述了这些细节。 这可能是即将到来的版本7中的一个特征，但是显然，当与堆叠检查结合使用时会出现某些困难，因为某些帧将会丢失。 从Java 2开始，堆栈检查已经被用来实现他们的细粒度的安全模型。
有很多情况下，它提供了一个比迭代方法更优雅的解决scheme，常见的例子是遍历二叉树，所以不一定更难以维护。 一般而言，迭代版本通常要快一些（在优化过程中可能会取代recursion版本），但recursion版本更易于正确理解和实现。
recursion在一些情况下是非常有用的。 例如，考虑用于查找阶乘的代码
int factorial ( int input ) { int x, fact = 1; for ( x = input; x > 1; x--) fact *= x; return fact; }
现在通过使用recursion函数来考虑它
int factorial ( int input ) { if (input == 0) { return 1; } return input * factorial(input - 1); }
通过观察这两个，我们可以看到recursion很容易理解。 但是，如果不小心使用它，也可能会有太多的错误。 假设如果我们错过if (input == 0) ，那么代码将被执行一段时间，并通常以堆栈溢出结束。
在很多情况下，由于caching，recursion速度更快，这可以提高性能。 例如，以下是使用传统合并例程的合并sorting的迭代版本。 由于caching提高了性能，它将比recursion实现慢。
迭代实现
public static void sort(Comparable[] a) { int N = a.length; aux = new Comparable[N]; for (int sz = 1; sz < N; sz = sz+sz) for (int lo = 0; lo < N-sz; lo += sz+sz) merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1)); }
recursion实现
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { if (hi <= lo) return; int mid = lo + (hi - lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid+1, hi); merge(a, aux, lo, mid, hi); }
PS – 这就是Kevin Wayne教授（普林斯顿大学）在Coursera上介绍的algorithm的过程。
使用recursion，每个“迭代”都会产生函数调用的代价，而在循环中，通常你所付出的唯一一个增量/减量。 所以，如果循环的代码比recursion解决scheme的代码复杂得多，循环通常优于recursion。
recursion和迭代取决于您要实现的业务逻辑，尽pipe在大多数情况下它可以互换使用。 大多数开发人员都会进行recursion，因为它更容易理解。
这取决于语言。 在Java中你应该使用循环。 function语言优化recursion。
如果你只是遍历一个列表，那么确定，迭代。
其他一些答案提到了（深度优先）树遍历。 这真是一个很好的例子，因为对一个非常普通的数据结构来说，这是一件很平常的事情。 recursion对于这个问题是非常直观的。
看看这里的“查找”方法： http : //penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
recursion比任何可能的迭代定义都更简单（因此更为基础）。 你可以用一对组合器来定义一个图灵完整系统（是的，即使是recursion本身也是这样一个系统中的派生概念）。 Lambda微积分是一个同样强大的基本系统，具有recursionfunction。 但是如果你想正确地定义一个迭代，你需要更多的基元来开始。
至于代码 – 否，recursion代码实际上比纯粹的迭代代码更容易理解和维护，因为大多数数据结构是recursion的。 当然，为了正确使用，至less需要一种支持高阶函数和闭包的语言 – 以一种整洁的方式获得所有标准的组合器和迭代器。 在C ++中，当然，复杂的recursion解决scheme看起来有点难看，除非你是FC ++的核心用户。
我会认为在（非尾）recursion中，每次函数被调用时（依赖于语言当然），将会有一个分配新栈的性能命中。
这取决于“recursion深度”。 这取决于函数调用开销多less会影响总执行时间。
例如，以recursion方式计算经典因子是非常低效的，因为： – 数据溢出的风险 – 堆栈溢出的风险 – 函数调用开销占用执行时间的80％
而在国际象棋博弈中开发一个用于位置分析的min-maxalgorithm，将分析后续的N次移动，可以在“分析深度”上进行recursion实现（就像我正在做的那样）
recursion？ 我从哪里开始，wiki会告诉你“这是一个自相似的方式重复项目的过程”
早在我做C的时候，C ++recursion就是上帝派来的东西，比如“尾recursion”。 你也会发现许多sortingalgorithm使用recursion。 快速sorting示例： http ： //alienryderflex.com/quicksort/
recursion就像其他任何对特定问题有用的algorithm。 也许你可能不会马上或经常地find一个用途，但会有问题，你会很高兴它可用。
在C ++中，如果recursion函数是模板化的，那么编译器就有更多的机会对其进行优化，因为所有的types演绎和函数实例都将在编译时发生。 如果可能，现代编译器也可以内联函数。 所以如果在g++使用像-O3或-O2这样的优化标志，那么recursion就有可能比迭代更快。 在迭代代码中，编译器得到更less的优化机会，因为它已经处于或多或less的最佳状态（如果写得够好的话）。
在我的情况下，我试图通过使用Armadillomatrix对象的recursion和迭代方式实现matrix求幂。 algorithm可以在这里find… https://en.wikipedia.org/wiki/Exponentiation_by_squaring 。 我的function是模板化的，我已经计算了1,000,000 12x12matrix。 我得到以下结果：
iterative + optimisation flag -O3 -> 2.79.. sec recursive + optimisation flag -O3 -> 1.32.. sec iterative + No-optimisation flag -> 2.83.. sec recursive + No-optimisation flag -> 4.15.. sec
使用带有c ++ 11标志的gcc-4.8（ -std=c++11 ）和带有Intel mkl的Armadillo 6.1获得了这个结果。 英特尔编译器也显示类似的结果
迈克是对的。 尾recursion没有被Java编译器或JVM优化。 你总是会得到像这样的堆栈溢出：
int count(int i) { return i >= 100000000 ? i : count(i+1); }
你必须记住，利用太深的recursion，你会遇到堆栈溢出，取决于允许的堆栈大小。 为了防止这种情况，请确保提供一些结束recursion的基本情况。
recursion有一个缺点，即使用recursion编写的algorithm具有O（n）空间复杂性。 虽然迭代方法的空间复杂度为O（1），这是对迭代使用迭代的好处。 那么为什么我们使用recursion？
见下文。
有时使用recursion编写algorithm会比较容易，但使用迭代编写相同的algorithm会稍微困难。在这种情况下，如果您select遵循迭代方法，则必须自己处理堆栈。
据我所知，Perl不会优化尾recursion调用，但是可以伪造它。
sub f{ my($l,$r) = @_; if( $l >= $r ){ return $l; } else { # return f( $l+1, $r ); @_ = ( $l+1, $r ); goto &f; } }
当第一次调用它将分配堆栈上的空间。 然后它将改变它的参数，并重新启动子程序，而不需要再向堆栈添加任何东西。 因此，它会假装它从来没有把自己称作自我，而是把它变成一个反复的过程。
请注意，没有“ my @_; ”或“ local @_; ”，如果你这样做，将不再有效。
我将通过“归纳”devise一个Haskell数据结构来回答你的问题，这是一种recursion的“双重”。 然后我将展示这种二元性如何导致好的事情。
我们介绍一个简单的树的types：
data Tree a = Branch (Tree a) (Tree a) | Leaf a deriving (Eq)
我们可以把这个定义看作“树是分支（包含两棵树）还是叶（包含数据值）”。 所以叶是一种最小的情况。 如果一棵树不是一片叶子，那么它必定是一棵包含两棵树的复合树。 这是唯一的情况。
我们来做一棵树吧：
example :: Tree Int example = Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))
现在，假设我们要为树中的每个值添加1。 我们可以通过调用：
addOne :: Tree Int -> Tree Int addOne (Branch ab) = Branch (addOne a) (addOne b) addOne (Leaf a) = Leaf (a + 1)
首先请注意，这实际上是一个recursion的定义。 它将数据构造函数Branch和Leaf作为个案（因为Leaf是最小的，而且这些是唯一可能的情况），我们确信函数将会终止。
用迭代的方式写addOne会怎样？ 什么会循环到任意数量的分支看起来像？
此外，这种recursion通常可以用“函子”来表示。 我们可以通过定义：
instance Functor Tree where fmap f (Leaf a) = Leaf (fa) fmap f (Branch ab) = Branch (fmap fa) (fmap fb)
并定义：
addOne' = fmap (+1)
我们可以列出其他recursionscheme，例如代数数据types的变形（或折叠）。 使用变形，我们可以写：
addOne'' = cata go where go (Leaf a) = Leaf (a + 1) go (Branch ab) = Branch ab
如果迭代是primefaces级的，比推新的栈帧和创build一个新的线程更昂贵， 并且你有多个内核， 并且你的运行时环境可以使用所有这些，那么recursion方法可以产生巨大的性能提升multithreading。 如果平均迭代次数不可预测，那么使用一个线程池来控制线程分配并防止你的进程创build太多的线程并占用系统是一个好主意。
例如，在某些语言中，有recursionmultithreading合并sorting实现。
但是，multithreading可以循环使用，而不是recursion，所以这个组合将如何工作取决于更多的因素，包括操作系统及其线程分配机制。
只使用Chrome 45.0.2454.85米，recursion似乎是一个更好的数额。
这里是代码：
(function recursionVsForLoop(global) { "use strict"; // Perf test function perfTest() {} perfTest.prototype.do = function(ns, fn) { console.time(ns); fn(); console.timeEnd(ns); }; // Recursion method (function recur() { var count = 0; global.recurFn = function recurFn(fn, cycles) { fn(); count = count + 1; if (count !== cycles) recurFn(fn, cycles); }; })(); // Looped method function loopFn(fn, cycles) { for (var i = 0; i < cycles; i++) { fn(); } } // Tests var curTest = new perfTest(), testsToRun = 100; curTest.do('recursion', function() { recurFn(function() { console.log('a recur run.'); }, testsToRun); }); curTest.do('loop', function() { loopFn(function() { console.log('a loop run.'); }, testsToRun); }); })(window);
结果
// 100使用循环标准运行
100倍循环运行。 完成时间： 7.683ms
/ / 100运行使用functionrecursion方法W /尾recursion
100倍recursion运行。 完成时间： 4.841ms
在下面的截图中，recursion每次testing运行300个循环时会再次获得更大的优势
