关于性能：递归还是迭代？

Recursion or Iteration?

如果我们在算法中使用循环而不是递归，反之亦然，那么两者是否可以起到同样的作用？例如：检查给定的字符串是否是回文。
我已经看到许多程序员使用递归作为一种手段来展示一个简单的迭代算法可以适应账单。
编译器在决定使用什么方面起着至关重要的作用吗？

循环可以为您的程序带来性能提升。递归可以为程序员带来性能提升。选择哪种更适合您的情况！

递归可能会更加昂贵，具体取决于递归函数是否为尾递归(最后一行是递归调用)。尾部递归应该被编译器识别并针对其迭代对应物进行优化(同时保持代码中简洁明了的实现)。

我会以最有意义的方式编写算法，并且对于在几个月或几年内必须维护代码的可怜的傻瓜(无论是你自己还是其他人)来说，它是最清晰的。如果遇到性能问题，那么对代码进行概要分析，然后通过转移到迭代实现来查看优化。您可能希望查看memoization和动态编程。

将递归与迭代进行比较就像将十字头螺丝刀与平头螺丝刀进行比较一样。在大多数情况下，您可以卸下任何带平头的十字头螺钉，但如果您使用专为该螺钉设计的螺丝刀，它会更容易吗？

有些算法只是因为它们的设计方式(Fibonacci序列，遍历树状结构等)而适合递归。递归使算法更简洁，更易于理解(因此可共享和可重用)。

此外，一些递归算法使用"懒惰评估"，这使得它们比迭代兄弟更有效。这意味着它们只在需要时进行昂贵的计算，而不是每次循环运行时进行。

这应该足以让你开始。我也会为你挖掘一些文章和例子。

链接1：Haskel与PHP(递归与迭代)

下面是程序员必须使用PHP处理大型数据集的示例。他展示了使用递归在Haskel中处理是多么容易，但由于PHP没有简单的方法来完成相同的方法，他被迫使用迭代来获得结果。

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

链接2：掌握递归

大多数递归的不良声誉来自命令式语言的高成本和低效率。本文作者讨论了如何优化递归算法以使其更快更有效。他还讨论了如何将传统循环转换为递归函数以及使用尾端递归的好处。他的结束语真的总结了我认为的一些关键点：

"recursive programming gives the programmer a better way of organizing
code in a way that is both maintainable and logically consistent."

Mastering recursive programming

链接3：递归是否比循环更快？ (回答)

这是一个与您的类似的stackoverflow问题的答案的链接。作者指出，许多与递归或循环相关的基准测试都是特定于语言的。使用循环的命令式语言通常更快，而递归则更慢，反之亦然。我想从这个链接中得出的主要观点是，在语言不可知/情境盲目的情况下回答这个问题非常困难。

Is recursion ever faster than looping?

递归在内存中成本更高，因为每次递归调用通常都需要将内存地址推送到堆栈 - 以便稍后程序可以返回到该点。

尽管如此，在许多情况下递归比循环更自然和可读 - 就像使用树时一样。在这些情况下，我建议坚持递归。

通常，人们会期望性能损失处于另一个方向。递归调用可以导致额外堆栈帧的构建;对此的处罚有所不同。此外，在某些语言(如Python(更准确地说，在某些语言的某些实现中))中，您可以轻松地对可能以递归方式指定的任务运行堆栈限制，例如在树数据结构中查找最大值。在这些情况下，你真的想坚持循环。

编写好的递归函数可以在某种程度上减少性能损失，假设你有一个优化尾递归等的编译器。(还要仔细检查以确保函数真的是尾递归的 - 这是许多人犯错的事情之一上。)

除了"边缘"情况(高性能计算，非常大的递归深度等)之外，最好采用最清楚地表达您的意图，设计良好且可维护的方法。仅在确定需求后才进行优化。

对于可以分解为多个较小块的问题，递归优于迭代。

例如，要制作递归Fibonnaci算法，将fib(n)分解为fib(n-1)和fib(n-2)并计算两个部分。迭代只允许您一遍又一遍地重复单个函数。

然而，Fibonacci实际上是一个破碎的例子，我认为迭代实际上更有效。注意，fib(n)= fib(n-1)+ fib(n-2)和fib(n-1)= fib(n-2)+ fib(n-3)。 fib(n-1)计算两次！

一个更好的例子是树的递归算法。分析父节点的问题可以分解为分析每个子节点的多个较小问题。与Fibonacci示例不同，较小的问题彼此独立。

所以是 - 对于可以分解为多个，更小，独立，类似问题的问题，递归优于迭代。

使用递归时性能会下降，因为调用任何语言的方法都需要进行大量准备：调用代码发布返回地址，调用参数，其他一些上下文信息(如处理器寄存器)可能会保存在某处，并且在返回时被调用的方法发布一个返回值，然后由调用者检索该返回值，并且将恢复先前保存的任何上下文信息。迭代和递归方法之间的性能差异在于这些操作所花费的时间。

从实现的角度来看，当处理调用上下文所花费的时间与您的方法执行所花费的时间相当时，您真正开始注意到差异。如果您的递归方法需要更长的时间来执行，那么调用上下文管理部分，采用递归方式，因为代码通常更易读且易于理解，您不会注意到性能损失。否则，出于效率原因进行迭代。

我相信java中的尾递归目前尚未优化。关于LtU和相关链接的讨论中详细介绍了这些细节。它可能是即将发布的版本7中的一个功能，但显然当与Stack Inspection结合使用时会出现某些困难，因为某些帧会丢失。自Java 2以来，Stack Inspection已被用于实现其细粒度的安全模型。

http://lambda-the-ultimate.org/node/1333

在某些情况下，递归非常有用。例如，考虑寻找阶乘的代码

1
2
3
4
5
6
7

int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}

现在通过使用递归函数来考虑它

1
2
3
4
5
6
7
8

int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}

通过观察这两个，我们可以看到递归很容易理解。
但如果不小心使用它也会非常容易出错。
假设如果我们错过if (input == 0)，则代码将执行一段时间并以堆栈溢出结束。

在许多情况下，它为迭代方法提供了更优雅的解决方案，常见的例子是遍历二叉树，因此维护不一定更困难。通常，迭代版本通常更快一些(并且在优化期间可以很好地替换递归版本)，但递归版本更容易理解和正确实现。

在许多情况下，由于缓存，递归更快，从而提高了性能。例如，这是使用传统合并例程的合并排序的迭代版本。由于缓存改进的性能，它将比递归实现运行得慢。

迭代实现

1
2
3
4
5
6
7
8

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));
}

递归实现

1
2
3
4
5
6
7
8

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--凯文韦恩教授(普林斯顿大学)就Coursera上提出的算法课程讲述了这一点。

使用递归，每次"迭代"都会产生函数调用的成本，而对于循环，您通常只需要增加/减少。因此，如果循环的代码并不比递归解的代码复杂得多，则循环通常优于递归。

这取决于语言。在Java中，您应该使用循环。功能语言优化递归。

递归和迭代取决于您要实现的业务逻辑，但在大多数情况下，它可以互换使用。大多数开发人员都会进行递归，因为它更容易理解。

递归比任何可能的迭代定义更简单(因此更基本)。您可以使用一对组合器定义图灵完备系统(是的，即使递归本身也是这种系统中的衍生概念)。 Lambda演算是一个同样强大的基本系统，具有递归函数。但是如果你想正确定义一个迭代，你需要更多的原语来开始。

至于代码 - 否，递归代码实际上比纯迭代代码更容易理解和维护，因为大多数数据结构都是递归的。当然，为了使它正确，人们需要一种支持高阶函数和闭包的语言，至少 - 以一种简洁的方式获得所有标准的组合器和迭代器。当然，在C ++中，复杂的递归解决方案看起来有点难看，除非你是FC ++的核心用户。

如果你只是迭代一个列表，那么肯定，迭代。

其他几个答案提到了(深度优先)树遍历。它确实是一个很好的例子，因为它对于一个非常常见的数据结构来说是非常常见的事情。递归对于这个问题非常直观。

在这里查看"查找"方法：
http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

递归？我从哪里开始，维基会告诉你"这是以自我相似的方式重复项目的过程"

回到我做C的那天，C ++递归是一个神派，像"尾递归"之类的东西。您还会发现许多排序算法都使用递归。快速排序示例：http：//alienryderflex.com/quicksort/

递归就像任何其他对特定问题有用的算法一样。也许您可能不会立即或经常使用，但会有问题，您会很高兴它可用。

我认为在(非尾部)递归中，每次调用函数时都会有分配新堆栈的性能损失(当然取决于语言)。

在C ++中，如果递归函数是模板函数，那么编译器有更多机会对其进行优化，因为所有类型推导和函数实例化都将在编译时发生。如果可能，现代编译器也可以内联函数。因此，如果在g++中使用-O3或-O2等优化标志，则递归可能比迭代更快。在迭代代码中，编译器获得优化的机会较少，因为它已经处于或多或少的最佳状态(如果写得足够好)。

在我的例子中，我试图通过使用Armadillo矩阵对象，以递归和迭代的方式实现矩阵求幂。该算法可以在这里找到... https://en.wikipedia.org/wiki/Exponentiation_by_squaring。
我的函数是模板化的，我计算了1,000,000 12x12矩阵，其功率10。我得到了以下结果：

1
2
3
4
5

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标志(-std=c++11)的gcc-4.8和带有Intel mkl的Armadillo 6.1获得的。英特尔编译器也显示类似结果。

它取决于"递归深度"。
它取决于函数调用开销将影响总执行时间的程度。

例如，由于以下原因，以递归方式计算经典因子是非常低效的：
- 数据溢出的风险
- 堆栈溢出的风险
- 函数调用开销占用执行时间的80％

在国际象棋游戏中开发用于位置分析的最小 - 最大算法，将分析随后的N个移动，可以在"分析深度"的递归中实现(正如我正在做的那样^ _ ^)

您必须记住，利用过于递归的深度，您将遇到Stack Overflow，具体取决于允许的堆栈大小。为了防止这种情况，请确保提供一些结束递归的基本案例。

迈克是对的。 Java编译器或JVM没有对尾递归进行优化。你将总是得到一个像这样的堆栈溢出：

1
2
3

int count(int i) {
return i >= 100000000 ? i : count(i+1);
}

递归的缺点是使用递归编写的算法具有O(n)空间复杂度。
虽然迭代aproach的空间复杂度为O(1)。这是使用迭代而不是递归的优势。
那为什么我们使用递归呢？

见下文。

有时使用递归编写算法更容易，而使用迭代编写相同的算法则稍微困难一些。在这种情况下，如果您选择遵循迭代方法，则必须自己处理堆栈。

仅使用Chrome 45.0.2454.85 m，递归似乎更快。

这是代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

(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使用标准for循环运行

循环运行100x。
完成时间：7.683ms

// 100使用带尾递归的函数递归方法运行

100x递归运行。
完成时间：4.841ms

在下面的屏幕截图中，当每次测试运行300个周期时，递归再次以更大的余量获胜

Recursion wins again!