在Java中总是避免递归方法吗？

Question

我记得，应该始终避免在中使用递归方法调用。我认为原因是，通过在堆上保存被调用的方法而导致的开销不值得在实现中减少代码行。

但是，最近有人告诉我，如果递归实现很好地捕捉了问题空间，那么这是不正确的。我没有完全理解这一点，因为每个递归方法都可以迭代地实现，例如使用堆栈。

有几个问题可以通过递归实现来解决，例如遍历树状数据结构。

应该始终避免中的递归实现()还是(而不是)？如果不是，什么是一个很好的标准来决定，是使用递归还是迭代实现。所产生的开销是重要的还是优化的？我读过关于堆栈溢出的文章，尾递归优化在Java中不受支持。

Answer 1

不，您不应该避免Java本身的递归。它在JVM中有其局限性，主要是您不能像函数式语言那样深入地递归(因为，正如您所注意到的，JVM不支持尾递归优化)，但是在这些限制范围内，它确实是有用的和可用的。

因此，每当它使您的解决方案变得更简单时，就使用它。是的，您总是可以将递归展开到迭代中，但是生成的代码往往更难理解和维护。递归的性能通常不是事先要担心的问题。首先用度量证明递归是程序中的一个性能瓶颈，然后您可以重写它。