递归对服务器有什么影响？
我听说在服务器上运行递归代码会影响性能。这个说法有多真实？递归方法是否应该作为最后的手段？
I've heard that running recursive code on a server can impact performance. How true is this statement, and should recursive method be used as a last resort?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
递归可能比等效的迭代解决方案消耗更多的内存，因为后者可以优化为仅占用它严格需要的内存，但递归将所有局部变量保存在堆栈上，因此占用的内存比严格需要的多一点。这只是内存有限的环境中的问题（这并不是罕见的情况），并且对于可能非常深的递归（几十个递归分支最多占用几百个字节，无法影响服务器的内存占用），因此“最后的手段”是一个过高的出价。
但是，当分析显示足迹影响很大时，您绝对可以执行的一项优化重构是 递归删除——几十年前学术文献中一个流行的话题，但通常不难手动完成（特别是如果你将所有方法，无论是递归方法还是其他方法）保持得相当小，就像你应该的那样;-)。
Recursion can potentially consume more memory than an equivalent iterative solution, because the latter can be optimized to take up only the memory it strictly needs, but recursion saves all local variables on the stack, thus taking up a bit more than strictly needed. This is only a problem in a memory-limited environment (which is not a rare situation) and for potentially very deep recursion (a few dozen recursive legs taking up a few hundred bytes each at most will not measurably impact the memory footprint of the server), so "last resort" is an overbid.
But when profiling shows you that the footprint impact is large, one optimization-refactoring you can definitely perform is recursion removal -- a popular topic since a few decades ago in the academic literature, but typically not hard to do by hand (especially if you keep all your methods, recursive or otherwise, reasonably small, as you should;-).
是的，它会影响性能，就像创建变量、循环或执行几乎任何其他事情一样。
如果递归代码很差或不受控制，它将像不受控制的 while 循环一样消耗系统资源。
不。它可以作为第一个手段，很多时候编写递归函数会更容易。取决于你的技能。但要明确的是，递归并没有什么特别邪恶的地方。
It is true, it impacts the performance, in the same way creating variables, loops or executing pretty much anything else.
If the recursive code is poor or uncontrolled it will consume your system resources the same way an uncontrolled while loop.
No. It may be used as a first resort, many times it would be easier to code a recursive function. Depends on your skills. But to be clear, there is nothing particularly evil with recursion.
要讨论性能，您必须讨论非常具体的场景。 适当地使用递归就可以了。如果您使用它不恰当，您可能会耗尽堆栈，或者只是使用太多堆栈。如果你以某种方式得到一个递归尾部调用而没有终止（通常是：尝试遍历循环图之类的错误），则尤其如此，因为它甚至不会破坏堆栈（它只会永远运行，占用 CPU周期）。
但只要做得对（并将深度限制在合理的范围内）就可以了。
To discuss performance you have to talk about very specific scenarios. Used appropriately recursion is fine. If you use it inappropriately you could blow the stack, or just use too much stack. This is especially true if you somehow get a recursive tailcall without ever it terminating (typically: a bug such as an attempt to walk a cyclic graph), as it won't even blow the stack (it'll just run forever, chomping CPU cycles).
But get it right (and limit the depth to sane amounts) and it is fine.
一个编程错误的递归不会结束会对机器产生负面影响，消耗越来越多的资源，并在最坏的情况下威胁整个系统的稳定性。
否则，递归是一个完全合法的工具，就像循环和其他结构一样。它们本身对性能没有负面影响。
A badly programmed recursion that does not end has a negative impact on the machine, consuming an ever-grwoing amount of resources, and threatening the stability of the whole system in the worst case.
Otherwise, recursions are a perfectly legitimate tool like loops and other constructs. They have no negative effect on performance per se.
尾递归也是一种替代方法。归结为：只需将返回的 Result 作为可变引用作为递归方法的参数传递即可。这样堆栈就不会爆炸。更多信息请参见维基百科和此站点。
Tail-recursion is also an alternative. It boils down to this: just pass the returned
Resultas mutable reference as parameter of the recursion method. This way the stack won't blow up. More at Wikipedia and this site.当您必须编写算法时，递归是一个首选工具。当您必须处理树或图等递归数据结构时，它也比迭代容易得多。如果（根据经验）您可以将递归深度评估为不太大的值，那么通常是无害的，前提是您不要忘记结束条件...
大多数现代编译器都能够优化某些类型的递归调用（替换它们在内部具有非递归等价物）。使用尾递归特别容易，即递归调用是返回结果之前的最后一条指令。
然而，存在一些 Java 特有的问题。底层 JVM 不提供任何类型的 goto 指令。这设置了编译器可以执行的操作的限制。如果它是一个函数内部的尾端递归，则可以用该函数内部的简单循环来替换，但如果终端调用是通过另一个函数完成的，或者如果多个函数相互递归调用，则在以下情况下会变得相当困难针对 JVM 字节码。 SUN JVM 不支持尾部调用优化，但有计划来改变这一点， IBM JVM 确实支持尾部调用优化。
对于某些语言（如 LISP 或 Haskell 等函数式语言），递归也是编写程序的唯一（或更自然）方法。在基于 JVM 的函数式语言（如 Clojure 或 Scala）上，缺乏尾部调用优化是一个问题，导致出现诸如 蹦床。
Recusion is a tool of choice when you have to write algorithms. It's also much easier than iteration when you have to deal with recusive data structures like trees or graph. It's usually harmless if (as a rule of thumb) you can evaluate evaluate the recusion depth to something not too large, provided that you do not forget the end condition...
Most modern compilers are able to optimize some kinds of recursive call (replace them internally with non recursive equivalents). It's specialy easy with tail recursion, that is when the recursive call is the last instruction before returning the result.
However there is some issues specific to Java. The underlying JVM does not provide any kind of goto instruction. This set limits of what the compiler can do. If it's a tail-end recursion internal to one function it can be replaced by a simple loop internal to the function, but if the terminal call is done through another function, or if several functions recusively calls one another it become quite difficult to do when targeting JVM bytecode. SUN JVM does not support tail-call optimization, but there is plans to change that, IBM JVM does support tail-call optimization.
With some languages (functional languages like LISP or Haskell) recursion is also the only (or the more natural) way to write programs. On JVM based functional languages like Clojure or Scala the lack of tail-call optimization is a problem that leads to workarounds like trampolines in Scala.
在服务器上运行任何代码都会影响性能。服务器性能通常首先会受到存储 I/O 的影响，因此在“服务器性能”级别上看到谈论通用算法策略的问题很奇怪。
Running any code on a server can impact performance. Server performance is usually going to be impacted by storage I/O before anything else, so at the level of "server performance" it's odd to see the question of general algorithm strategy talked about.
深度递归可能会导致堆栈溢出，这是令人讨厌的。请小心，因为如果需要的话，很难再站起来。小型、可管理的工作更容易处理和并行化。
Deep recursion Can cause a stack overflow, which is nasty. Be careful as it s hard to get up again if you need to. Small, manageable piecs of work is easier to handle and parallize.