11

可能重复：
递归比循环快吗？

大约 15 年前，我第一次接受了认真的 C 语言培训。我的雇主想要高度优化的代码来完成计算困难的任务。我记得不止一次被建议将递归重写为循环，即使以牺牲可读性为代价，以避免“递归开销”。正如我当时所理解的那样，递归开销是将数据推送到堆栈然后将其弹出所需的额外工作。

现在我用 C、Python、Perl 和 Java 编写代码，有时我想知道递归。重写它们还有什么好处吗？如果它们是尾递归怎么办？现代编译器是否已经解决了所有这些问题？这些问题与解释语言无关吗？

4

5 回答 5

19

如果递归函数的内核的计算成本低于函数进入/退出代码和调用本身的成本，则递归可能会导致大量开销。找出答案的最好方法是简单地分析两个版本的代码——一个是递归的，一个不是。

也就是说，如果您避免递归的想法是自己制作一个类似堆栈的结构，请注意 - 它可能不一定比更直接的递归方法更快。同样，分析是您的朋友。

最后，请记住，程序员的时间比 CPU 时间更昂贵。在对代码进行微优化之前，测量一下它是否真的会成为一个问题确实是个好主意。

于 2010-10-24T14:20:17.840 回答
3

问题依然存在。递归占用大量堆栈空间，因为每次方法调用自身时，都会再次生成指向它的指针及其局部变量。递归期间进行的函数调用次数使内存使用量为 O(n)；与像循环这样的非递归函数的 O(1) 相比。

于 2010-10-24T14:17:49.707 回答
2

我认为您提到的任何语言都不需要平台/编译器实现尾调用消除。你可以找到确实需要这种优化的语言——大多数函数式语言都有这个要求。

但是，您需要考虑的另一件事是，计算机的速度比 15 年前快了几个数量级，因此现在您需要担心微优化的情况比以前少得多。一个 15 年前的程序可能需要在汇编程序中进行仔细的手工优化才能获得良好的性能，即使是用 Java 等高级语言编写的，它也可能在现代计算机上运行得非常快。这并不是说性能不再是问题 - 但您应该专注于选择正确的算法和编写可读的代码。只有在您测量了性能之后才进行微优化，您可以看到有问题的代码是瓶颈。

您确实需要担心的一件事是溢出堆栈。如果有发生这种情况的风险，那么可能值得以迭代的方式重写递归函数。

于 2010-10-24T14:16:42.450 回答
2

这是严重的。我编写的大多数语言都有函数调用的实际成本（它们的编译器通常也可以进行尾递归，所以有时这不是问题）。

这种成本，以及堆栈不是无限资源的事实，通常使我倾向于仅在我知道它可以达到的深度有限制的情况下使用递归。

例如，我知道平衡二叉树搜索对于 100 亿个条目只能进行 50 级深。但是，我不会使用：

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

因为为n两千万美元做这件事对堆栈来说是不健康的。

于 2010-10-24T14:16:55.263 回答
1

人们对性能说了很多傻话。

  1. 如果你需要递归，比如深度优先树遍历，那么你需要它，所以使用它。

  2. 在担心任何事情的性能之前，请先弄清楚您是否有问题以及问题出在哪里。
    性能问题就像骗子和骗子——他们专注于你最不期望的地方，所以如果你担心递归等特定的事情，你几乎肯定会担心错误的事情。

在我看来，发现性能问题的最佳方法是在挂钟时间进行堆栈采样，并检查样本以查看程序在做什么，而不仅仅是通过测量并了解它们的含义。

也就是说，如果您确实发现 10% 或更多的时间用于递归调用，并且在递归例程中没有发生任何其他事情，并且您可以循环它，那么循环它可能会有所帮助。

于 2010-10-24T16:45:57.623 回答