为什么递归优于迭代？

Question

迭代比递归性能更高，对吧？那么为什么有些人认为递归比迭代更好（用他们的话说更优雅）？我真的不明白为什么像 Haskell 这样的语言不允许迭代并鼓励递归？鼓励性能不佳的东西（当有更高性能的选项，即递归可用时也是如此），这不是很荒谬吗？请阐明这一点。谢谢。

Answer 1

迭代的性能比
递归，对吗？

未必。
这个概念来自许多类似 C 的语言，在这些语言中，无论是否递归调用函数，都会产生很大的开销，并为每次调用创建一个新的堆栈帧。

对于许多语言来说，情况并非如此，递归与迭代版本的性能相同或更高。如今，甚至一些 C 编译器将一些递归结构重写为迭代版本，或者重用堆栈帧进行尾递归调用。

Answer 2

尝试以递归和迭代方式实现深度优先搜索，并告诉我哪一个让您更轻松。或者归并排序。对于很多问题，归根结底是显式维护自己的堆栈，而不是将数据保留在函数堆栈上。

我无法与 Haskell 交谈，因为我从未使用过它，但这是为了解决您标题中提出的问题的更一般部分。

Answer 3

Haskell 不允许迭代，因为迭代涉及可变状态（索引）。

Answer 4

正如其他人所说，递归本质上并没有什么性能较差的地方。有些语言会比较慢，但这不是普遍规则。

话虽这么说，对我来说，递归是一种工具，在有意义的时候使用。有些算法可以更好地表示为递归（就像有些算法通过迭代更好一样）。

举个例子：

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

我无法想象一个迭代解决方案可以使意图比这更清晰。

Answer 5

以下是有关优点和优点的一些信息。递归和递归的缺点c 中的迭代：

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

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

Answer 6

迭代只是递归的一种特殊形式。

Answer 7

递归是理论上看起来优雅或高效的事物之一，但实际上通常效率较低（除非编译器或动态重新编译器）正在改变代码的功能。一般来说，任何导致不必要的子例程调用的事情都会变慢，特别是当超过 1 个参数被压入/弹出时。您可以采取任何措施来消除处理器周期，即处理器必须咀嚼的指令，这都是公平的游戏。如今，编译器通常可以在这方面做得很好，但了解如何手动编写高效的代码总是好的。

Answer 8

有几点：

1. 迭代不一定更快
2. 万恶之源：仅仅因为某件事可能稍微快一点就鼓励它还为时过早；还有其他考虑因素。
3. 递归通常可以更简洁、更清晰地传达您的意图。
4. 通过通常避免可变状态，函数式编程语言更容易推理和调试，递归就是一个例子。
5. 递归比迭代占用更多内存。

Answer 9

我不认为递归本质上有什么性能较差的地方——至少在抽象方面是这样。递归是迭代的一种特殊形式。如果一种语言被设计为能够很好地支持递归，那么它的性能可能与迭代一样好。

一般来说，递归使人们明确地了解您在下一次迭代中提出的状态（即参数）。这可以使语言处理器更容易并行执行。至少这是语言设计者正在努力探索的一个方向。

Answer 10

作为低级 ITERATION 处理 CX 注册表以计算循环，当然还有数据注册表。
递归不仅处理这个问题，它还添加对堆栈指针的引用，以保留先前调用的引用以及如何返回。-

我的大学老师告诉我，无论你用递归做什么都可以用迭代来完成，反之亦然，但有时通过递归比迭代更简单（更优雅），但在性能级别上使用迭代更好。-

Answer 11

在 Java 中，递归解决方案通常优于非递归解决方案。在 C 语言中，情况往往相反。我认为这通常适用于自适应编译语言与提前编译语言。

编辑：
我所说的“一般”是指 60/40 的分配。它很大程度上取决于语言处理方法调用的效率。我认为 JIT 编译有利于递归，因为它可以选择如何处理内联并在优化中使用运行时数据。不过，它非常依赖于所讨论的算法和编译器。尤其是 Java 在处理递归方面不断变得更加智能。

Java 的定量研究结果（PDF 链接）。请注意，这些大多是排序算法，并且使用较旧的 Java 虚拟机（如果我没看错的话，为 1.5.x）。 有时通过使用递归实现可以获得 2:1 或 4:1 的性能改进，并且很少会出现递归明显变慢的情况。根据我个人的经验，这种差异通常并不那么明显，但会相差 50当我明智地使用递归时，% 的改进是很常见的。

Answer 12

我发现很难推断一个人总是比另一个人更好。

我正在开发一个需要在用户文件系统上进行后台工作的移动应用程序。其中一个后台线程需要不时地扫描整个文件系统，以向用户维护更新的数据。因此，由于担心 Stack Overflow，我编写了一个迭代算法。今天我为同样的工作写了一个递归的。令我惊讶的是，迭代算法更快：递归 -> 37s，迭代-> 34 秒（处理完全相同的文件结构）。

递归：

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

迭代： - 迭代深度优先搜索，具有递归回溯

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

当然，迭代并不优雅，但尽管目前以低效的方式实现，但它仍然更快比递归的。而且我可以更好地控制它，因为我不希望它全速运行，并且会让垃圾收集器更频繁地执行其工作。

无论如何，我不会理所当然地认为一种方法比另一种方法更好，并且会回顾当前递归的其他算法。但至少从上面的两种算法来看，迭代的算法将是最终产品中的算法。

Answer 13

我认为这将有助于了解性能的真正含义。 此链接展示了一个完美合理编码的应用程序实际上如何具有很大的优化空间 - 即 43 倍！ 这些都与迭代与递归无关。

当一个应用程序已经调整到那么远时，它就会达到这样的程度：通过迭代保存的循环相对于递归可能实际上会产生影响。

Answer 14

递归是迭代的典型实现。它只是较低级别的抽象（至少在 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)

Answer 15

我将递归比作炸药：你可以立即获得巨大的结果。但如果不小心使用它，结果可能是灾难性的。

这里计算斐波那契数的递归复杂性给我留下了深刻的印象。在这种情况下，递归的复杂度为 O((3/2)^n)，而迭代的复杂度仅为 O(n)。用c#编写的递归计算n=46需要半分钟！哇...

恕我直言，只有当实体的性质适合递归（树，语法解析，...）时才应使用递归，而绝不能因为美观而使用递归。任何“神圣”递归代码的性能和资源消耗都需要仔细检查。

Answer 16

迭代比递归性能更高，对吗？

是的。

但是，当您遇到的问题完美映射到递归数据结构时，更好的解决方案始终是递归。

如果你假装用迭代来解决问题，那么与优雅相比，你最终会重新发明堆栈并创建更混乱和丑陋的代码代码的递归版本。

也就是说，迭代总是比递归更快。 （在冯诺依曼架构中），所以如果你总是使用递归，即使循环就足够了，你也会付出性能损失。

递归比循环更快吗？

Answer 17

“迭代比递归性能更高”实际上是特定于语言和/或编译器的。我想到的情况是编译器进行循环展开时。如果您在这种情况下实现了递归解决方案，那么速度会慢很多。

这就是成为一名科学家（测试假设）并了解你的工具的价值所在......

Answer 18

在 ntfs UNC 最大路径上为 32K
C:\A\B\X\C...可以创建超过16K的文件夹...

但是你甚至无法用任何递归方法计算文件夹的数量，迟早都会出现堆栈溢出。

仅应使用良好的轻量级迭代代码来专业扫描文件夹。

不管您是否相信，大多数顶级防病毒软件都无法扫描最大深度的 UNC 文件夹。