为什么binarySearch()方法在java.util.Arrays中使用循环而不是递归实现？
最佳答案
tl;dr:因为javac不做尾部调用优化。
正如您可能注意到的那样，许多算法本质上都是递归的(二分搜索就是一个很好的例子)。那么为什么递归在Java中没有被广泛使用呢？
第一个原因是递归的性能不如普通循环。其次，更重要的原因是Java中的递归不是堆栈安全的。如果您的递归深入到调用堆栈，则可能会导致 StackOverflowError。这是有问题的，因为你无法真正预测你会走多深，因为这取决于你正在处理的数据。这样做的结果是，您的递归函数可能在较小的数据集上正确工作，但在较大的数据集上会炸毁堆栈。
幸运的是，通过用迭代控制结构替换递归调用，每个递归函数都可以转换为迭代函数，从而成为堆栈安全的，这正是您在 java.util.Arrays 中看到的。
还有一个缺点，即算法的迭代版本可能被认为更难以推理且可读性较差(但这是有争议的)。
递归也是一种在没有可变状态(循环计数器)的情况下进行“循环”的方法，因此通过这种方式您可以进行纯功能迭代(例如 Haskell don't even have loops ，它仅取决于递归) .
那么我们可以拥有堆栈安全、可读且高性能的递归吗？是的，如果编译器可以将递归优化为与循环非常相似的代码。大多数 JVM 语言编译器(Groovy、Scala、Kotlin、Clojure 等)都可以执行 tail-call optimalization 。这意味着递归调用是函数执行的最后一件事，它将被编译为字节码，这看起来与普通的 while 循环非常相似。
其实有proposal向javac添加尾部调用优化，但尚未实现。如果您现在想使用堆栈安全递归，您可能需要使用其他 JVM 语言。
关于java - 为什么java.util.Arrays中的binarySearch()方法是使用循环实现的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56564930/