递归还是迭代？

循环可能会为您的程序带来性能提升。递归可能会为您的程序员带来性能提升。选择在您的情况下哪个更重要！

---

递归可能会更昂贵，具体取决于递归函数是否为 tail recursive（最后一行是递归调用）。尾递归应该被编译器识别并优化为它的迭代对应物（同时保持你在代码中的简洁、清晰的实现）。

我会以最有意义的方式编写算法，并且对于必须在几个月或几年内维护代码的可怜的傻瓜（无论是你自己还是其他人）来说最清晰。如果您遇到性能问题，请分析您的代码，然后并且只有这样才能通过转向迭代实现来进行优化。您可能需要查看 memoization 和 dynamic programming。

---

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

由于设计方式（斐波那契数列、遍历树状结构等），一些算法只适合递归。递归使算法更简洁，更容易理解（因此可共享和可重用）。

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

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

链接 1：Haskel 与 PHP（递归与迭代）

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

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

链接 2：掌握递归

大多数递归的坏名声来自于命令式语言的高成本和低效率。这篇文章的作者谈到了如何优化递归算法，使其更快、更高效。他还介绍了如何将传统循环转换为递归函数以及使用尾端递归的好处。他的结束语确实总结了我认为的一些要点：

“递归编程为程序员提供了一种更好的方式来组织代码，这种方式既可维护又逻辑一致。” https://developer.ibm.com/articles/l-recurs/

链接 3：递归比循环快吗？ （回答）

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

递归比循环快吗？

---

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

尽管如此，在很多情况下，递归比循环更自然、更易读——比如在处理树时。在这些情况下，我建议坚持递归。

---

通常，人们会期望性能损失位于另一个方向。递归调用会导致构建额外的栈帧；对此的处罚各不相同。此外，在 Python 等某些语言中（更准确地说，在某些语言的某些实现中......），对于可能递归指定的任务，您可以很容易地遇到堆栈限制，例如在树数据结构中查找最大值。在这些情况下，你真的想坚持使用循环。

编写好的递归函数可以在一定程度上减少性能损失，假设您有一个优化尾递归的编译器等。（还要仔细检查以确保该函数确实是尾递归——这是许多人犯错误的事情之一上。）

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

---

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

例如，要制作递归斐波那契算法，您将 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) 被计算两次！

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

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

---

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

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

---

我相信java中的尾递归目前没有优化。详细信息在 LtU 和相关链接的 this 讨论中散布。它可能是即将发布的第 7 版中的一项功能，但显然在与堆栈检查结合使用时会出现某些困难，因为某些帧会丢失。自 Java 2 以来，堆栈检查已被用于实现其细粒度的安全模型。

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

---

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

---

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

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

现在考虑使用递归函数

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

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

---

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

迭代实现

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

递归实现

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 上的算法课程中所说的。

---

使用递归，每次“迭代”都会产生函数调用的成本，而使用循环，您通常支付的唯一费用是递增/递减。因此，如果循环的代码并不比递归解决方案的代码复杂得多，那么循环通常会优于递归。

---

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

---

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

---

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

见下文。

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

---

如果你只是迭代一个列表，那么当然，迭代掉。

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

在此处查看“查找”方法：http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

---

递归比任何可能的迭代定义都更简单（因此更基本）。您可以仅使用 pair of combinators 定义图灵完备系统（是的，即使递归本身也是此类系统中的派生概念）。 Lambda 微积分是一个同样强大的基本系统，具有递归函数。但是如果你想正确地定义一个迭代，你需要更多的原语开始。

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

---

我认为在（非尾）递归中，每次调用函数时分配新堆栈等都会对性能造成影响（当然取决于语言）。

---

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

例如，以递归方式计算经典阶乘是非常低效的，因为： - 数据溢出的风险 - 堆栈溢出的风险 - 函数调用开销占用了 80% 的执行时间

在开发用于在国际象棋游戏中进行位置分析的最小-最大算法时，可以在“分析深度”上递归实现（就像我正在做的那样^_^）

---

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

早在我做 C 的时候，C++ 递归就是天赐之物，诸如“尾递归”之类的东西。您还会发现许多排序算法使用递归。快速排序示例：http://alienryderflex.com/quicksort/

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

---

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

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

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 获得的。英特尔编译器也显示了类似的结果。

---

迈克是对的。 Java 编译器或 JVM 不会优化尾递归。你总是会遇到这样的堆栈溢出：

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

---

您必须记住，使用太深的递归会遇到堆栈溢出，具体取决于允许的堆栈大小。为了防止这种情况，请确保提供一些结束递归的基本情况。

---

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

这是代码：

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

结果

// 使用标准 for 循环运行 100 次

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

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

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

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

https://i.stack.imgur.com/dQemM.png

---

如果迭代是原子的，并且比推送新堆栈帧和创建新线程要昂贵几个数量级，并且您有多个内核并且您的运行时环境可以使用所有内核，那么递归方法可以在结合使用时产生巨大的性能提升多线程。如果平均迭代次数不可预测，那么使用线程池可能是一个好主意，该线程池将控制线程分配并防止您的进程创建过多线程并占用系统。

例如，在某些语言中，存在递归多线程合并排序实现。

但同样，多线程可以与循环一起使用而不是递归，因此这种组合的效果取决于更多因素，包括操作系统及其线程分配机制。

---

我发现了这些方法之间的另一个区别。它看起来简单而不重要，但它在你准备面试时起着非常重要的作用，并且这个主题出现了，所以仔细看看。

简而言之：1）迭代后序遍历并不容易 - 这使得 DFT 更加复杂 2）循环检查更容易递归

细节：

在递归的情况下，很容易创建前后遍历：

想象一个非常标准的问题：“当任务依赖于其他任务时，打印所有应该执行的任务以执行任务 5”

例子：

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

请注意，递归后序遍历不需要随后反转结果。孩子们最先打印，你在问题中的任务最后打印。一切都很好。您可以进行递归前序遍历（也如上所示），并且需要反转结果列表。

迭代方法没那么简单！在迭代（一个堆栈）方法中，您只能进行预排序遍历，因此您必须在最后反转结果数组：

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

看起来很简单，不是吗？

但这在某些采访中是一个陷阱。

这意味着：使用递归方法，您可以实现深度优先遍历，然后选择您需要的前后顺序（只需更改“打印”的位置，在我们的“添加到结果列表”的情况下） ）。使用迭代（一个堆栈）方法，您可以轻松只进行预排序遍历，因此在需要首先打印孩子的情况下（几乎所有需要从底部节点开始打印的情况，向上） - 你有麻烦了。如果你有这个麻烦，你可以稍后逆转，但这将是你算法的一个补充。如果面试官正在看他的手表，那对你来说可能是个问题。进行迭代后序遍历有很复杂的方法，它们存在，但它们并不简单。示例：https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

因此，底线：我会在面试中使用递归，它更易于管理和解释。在任何紧急情况下，您都可以轻松地从订单前遍历到订单后遍历。使用迭代，你就没有那么灵活了。

我会使用递归然后告诉：“好的，但是迭代可以让我更直接地控制已用内存，我可以轻松测量堆栈大小并禁止一些危险的溢出......”

递归的另一个优点 - 避免/注意图中的循环更简单。

示例（前置代码）：

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

---

把它写成递归或练习可能会很有趣。

但是，如果要在生产中使用代码，则需要考虑堆栈溢出的可能性。

尾递归优化可以消除堆栈溢出，但是您是否想要这样做，并且您需要知道您可以依靠它在您的环境中进行优化。

每次算法递归，数据大小或n减少了多少？

如果您每次递归时都将数据或 n 的大小减少一半，那么通常您无需担心堆栈溢出。比如说，如果程序堆栈溢出需要 4,000 级或 10,000 级深度，那么您的程序堆栈溢出的数据大小需要大约为 2⁴⁰⁰⁰。从这个角度来看，最近一个最大的存储设备可以容纳 2⁶¹ 字节，如果你有 2⁶¹ 个这样的设备，你只处理 2 ¹²² 数据大小。如果你看宇宙中所有的原子，估计可能不到2⁸⁴。如果你需要处理宇宙中的所有数据及其状态，自宇宙诞生估计在 140 亿年前，它可能只有 2¹⁵³。因此，如果您的程序可以处理 2⁴⁰⁰⁰ 个数据单位或 n，则您可以处理 Universe 中的所有数据，并且程序不会堆栈溢出。如果您不需要处理大到 2⁴⁰⁰⁰（一个 4000 位整数）的数字，那么通常您无需担心堆栈溢出。

但是，如果每次递归都将数据或 n 的大小减小一个常数，那么当 n 仅变为 20000 时，您可能会遇到堆栈溢出。即n为1000时程序运行良好，你认为程序良好，然后在未来某个时间，当n为5000或20000时，程序堆栈溢出。

因此，如果您有可能发生堆栈溢出，请尝试使其成为迭代解决方案。

---

据我所知，Perl 没有优化尾递归调用，但你可以伪造它。

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

首次调用时，它将在堆栈上分配空间。然后它将更改其参数，并重新启动子程序，而不向堆栈添加任何内容。因此它会假装它从未调用过它自己，将它变成一个迭代过程。

请注意，没有“my @_;”或“local @_;”，如果你这样做了，它将不再起作用。

---

我将通过“归纳”设计一个 Haskell 数据结构来回答您的问题，这是一种“对偶”递归。然后我将展示这种二元性如何导致美好的事物。

我们为一棵简单的树引入一个类型：

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 a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

首先，请注意这实际上是一个递归定义。它以数据构造函数 Branch 和 Leaf 为案例（并且由于 Leaf 是最小的并且这些是唯一可能的情况），我们确信该函数将终止。

以迭代方式编写 addOne 需要什么？循环到任意数量的分支会是什么样子？

此外，就“函子”而言，这种递归通常可以被分解出来。我们可以通过定义将树变成函子：

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

并定义：

addOne' = fmap (+1)

我们可以分解出其他递归方案，例如代数数据类型的变态（或折叠）。使用变态，我们可以写：

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

---

堆栈溢出只会在您使用没有内置内存管理的语言进行编程时发生。否则，请确保您的函数中有某些内容（或函数调用、STDLbs 等）。如果没有递归，就不可能拥有诸如... Google 或 SQL 之类的东西，或者任何必须有效地对大型数据结构（类）或数据库进行排序的地方。

如果你想遍历文件，递归是要走的路，很确定这就是'find * | ?grep *' 有效。有点双重递归，尤其是使用管道（但不要像很多人喜欢做的那样做一堆系统调用，如果它是你要放在那里供其他人使用的任何东西）。

更高级的语言甚至 clang/cpp 都可以在后台实现它。

---