递归开销——有多严重？
可能的重复：
递归比循环更快吗？
我首先接受了认真的 C 编程培训，大约15年前。我的雇主想要高度优化的代码来完成计算困难的任务。我记得不止一次被建议将递归重写为循环，即使以牺牲可读性为代价，以避免“递归开销”。据我当时的理解，递归开销是将数据推入堆栈然后将其弹出所需的额外工作。
现在我用 C、Python、Perl 编码，有时也用 Java 编码，有时我想知道递归。重写它们还有什么收获吗？如果它们是尾递归怎么办？现代编译器是否已经让所有这些问题变得毫无意义了？这些担忧与解释语言无关吗？
Possible Duplicate:
Is recursion ever faster than looping?
I was first trained to program seriously in C, about 15 years ago. My employer wanted highly optimized code for computationally difficult tasks. I remember being advised more than once to rewrite recursions as loops, even at the expensive of readability, in order to avoid "recursion overhead." As I understood it then, recursion overhead was the extra effort required to push data onto a stack and later pop it off.
Now I code in C, Python, Perl, and sometimes Java, and I wonder sometimes about recursions. Is there still something to be gained by rewriting them? What if they're tail recursions? Have modern compilers made all these issues moot? Are such concerns irrelevant for interpreted languages?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果递归函数的内核的计算成本低于函数进入/退出代码和调用本身的成本，则递归可能会导致显着的开销。找出答案的最佳方法就是简单地分析代码的两个版本 - 一种是递归的，另一种不是。
也就是说，如果您避免递归的想法是自己创建一个类似堆栈的结构，请注意 - 它不一定比更直接的递归方法更快。再说一次，分析是你的朋友。
最后，请记住，程序员的时间比 CPU 时间更昂贵。在对代码进行微观优化之前，最好先进行衡量，看看它是否真的会成为问题。
Recursion can lead to significant overhead if the kernel of the recursive function is less computationally expensive than the function entry/exit code and the cost of the call itself. The best way to find out is simply to profile two versions of the code - one recursive, and one not.
That said, if your idea of avoiding recursion is to make a stack-like structure yourself, watch out - it may not necessarily be any faster than the more straightforward recursive approach. Again, profiling is your friend.
Finally, remember that programmer time is more expensive than CPU time. Before you micro-optimize your code, it really is a good idea to measure to see if it really will be an issue.
问题仍然存在。递归会占用大量堆栈空间，因为每次方法调用自身时，都会再次生成指向该方法的指针及其局部变量。递归期间进行的函数调用次数导致内存使用量为 O(n)；与循环等非递归函数的 O(1) 相比。
The issue still exists. Recursion takes a lot of stack space, as each time a method calls itself, a pointer to it and its local variables are generated again. The number of function calls made during recursion makes an O(n) memory usage; compared to O(1) of a non-recursive function like loops.
这很严重。我编写的大多数语言都有函数调用的实际成本（它们的编译器通常也可以进行尾递归，所以有时这不是问题）。
这种成本，以及堆栈不是无限资源的事实，通常使我倾向于仅在我知道它可以达到的深度有限的情况下才使用递归。
例如，我知道平衡二叉树搜索对于一万亿个条目只能深入五十层。但是，我不会使用：，
因为对于 2000 万的
n这样做对于堆栈来说并不健康。It is serious. Most of the languages I code in have a real cost to function calls (the compilers for them can generally do tail recursion as well so sometimes it's not an issue).
That cost, and the fact that the stack is not an unlimited resource, usually makes me tend to use recursion only for cases where I know there's a limit on the depth it can go to.
For example, I know a balanced binary tree search will only go fifty levels deep for one quadrillion entries. I wouldn't, however, use:
since doing that for
nof twenty million would not be healthy for a stack.我不认为您提到的任何语言要求平台/编译器实现尾调用消除。您可以找到需要此优化的语言 - 大多数函数式语言都有此要求。
然而，您需要考虑的另一件事是，计算机的速度比 15 年前快了几个数量级，因此现在您需要担心微优化的情况比以前少得多。 15 年前，一个程序可能需要在汇编程序中进行仔细的手工优化才能获得不错的性能，但即使是用 Java 等高级语言编写的程序，也可能在现代计算机上运行得非常快。这并不是说性能不再是问题 - 但您应该集中精力选择正确的算法并编写可读代码。仅在测量性能并且您可以看到有问题的代码是瓶颈之后才进行微观优化。
不过，您确实需要担心的一件事是堆栈溢出。如果存在发生这种情况的任何风险，则可能值得以迭代方式重写递归函数。
I don't think any of the languages you mentioned require that the platform/compiler implements tail call elimination. You can find languages that do require this optimization - most functional languages have this requirement.
However another thing you need to consider is that computers have become orders of magnitudes faster than they were 15 years ago, so it's much rarer now then before that you need to worry about micro-optimizations. A program that 15 years ago might have required careful hand optimization in assembler to get decent performance might run blazingly fast on a modern computer, even if written in a higher level language like Java. That's not to say that performance is never a problem any more - but you should concentrate on choosing the correct algorithm and on writing readable code. Only make micro-optimizations after you have measured the performance and you can see that the code in question is the bottleneck.
One thing you do need to worry about though is overflowing the stack. If there's any risk of that happening it might be worth rewriting a recursive function in an iterative way instead.
人们对性能说了很多愚蠢的话。
如果你需要递归，比如进行深度优先树遍历，那么你需要它，所以使用它。
在担心任何事情的性能之前，先查明您是否有问题以及问题出在哪里。
性能问题就像骗子和骗子——他们专门出现在你最意想不到的地方，所以如果你担心一些特定的事情，比如递归，你几乎肯定会担心错误的事情。
在我看来，发现性能问题的最佳方法是按挂钟时间进行堆栈采样，以及检查示例以了解程序正在做什么，而不仅仅是获取测量结果并想知道它们的含义。
也就是说，如果您确实发现 10% 或更多的时间进入递归调用，并且递归例程内没有发生其他任何事情，并且您可以循环它，那么循环它可能会有所帮助。
People say lots of silly things about performance.
If you need recursion, like to do depth-first tree walk, then you need it, so use it.
Before worrying about the performance of anything, find out if you have a problem and where it is.
Performance problems are like con men and tricksters - they specialize in being where you least expect, so if you're worried about something specific like recursion, you are almost guaranteed to be worrying about the wrong thing.
In my opinion, the best way to find performance problems is by stack sampling on wall-clock time, and examining the samples to see what the program is doing, not just by getting measurements and wondering what they mean.
That said, if you do find 10% or more of time going into a recursive call, and nothing much else happens inside the recursive routine, and you can loop it, then looping it will probably help.