为什么java.util.Arrays中的binarySearch()方法是用循环实现的？
Why is the binarySearch() method in java.util.Arrays implemented using a loop?
为什么java.util.Arrays中的binarySearch()方法是用循环而不是递归实现的？
tl;dr: 因为javac不做尾调用优化
您可能已经注意到，许多算法本质上都是递归的（二进制搜索就是一个很好的例子）。那么为什么递归在Java中没有被广泛使用呢？
第一个原因是递归的性能不如普通循环。其次，一个更重要的原因是Java中的递归不是stack-safe。如果您的递归将深入调用堆栈，则可能会导致 WhosebugError。这是有问题的，因为你无法真正预测你会走多深，因为它取决于你正在处理的数据。这样做的结果是您的递归函数可能在较小的数据集上正常工作，但会在较大的数据集上炸毁堆栈。
幸运的是，通过用迭代控制结构替换递归调用，每个递归函数都可以转换为迭代函数，因此变成 stack-safe，这正是您在 [=44= 中看到的].
还有一个缺点是算法的迭代版本可能被认为更难推理且可读性更差（但这值得商榷）。
递归也是一种在没有可变状态（循环计数器）的情况下执行 "loops" 的方法，因此您可以通过这种方式进行纯函数迭代（例如 Haskell ，只依赖于递归）。
那么我们可以stack-safe、可读且高效的递归吗？是的，如果编译器可以将递归优化为与循环非常相似的代码。大多数 JVM 语言编译器（Groovy、Scala、Kotlin、Clojure 等等）都可以做到 tail-call optimalization。这意味着递归调用是函数执行的最后一件事，它将被编译为字节码，这看起来与普通的 while 循环非常相似。
其实有proposal对javac添加tail-call优化，但还没有实现。如果您现在想使用 stack-safe 递归，您可能需要使用其他一些 JVM 语言。
为什么java.util.Arrays中的binarySearch()方法是用循环而不是递归实现的？
tl;dr: 因为javac不做尾调用优化
您可能已经注意到，许多算法本质上都是递归的（二进制搜索就是一个很好的例子）。那么为什么递归在Java中没有被广泛使用呢？
第一个原因是递归的性能不如普通循环。其次，一个更重要的原因是Java中的递归不是stack-safe。如果您的递归将深入调用堆栈，则可能会导致 WhosebugError。这是有问题的，因为你无法真正预测你会走多深，因为它取决于你正在处理的数据。这样做的结果是您的递归函数可能在较小的数据集上正常工作，但会在较大的数据集上炸毁堆栈。
幸运的是，通过用迭代控制结构替换递归调用，每个递归函数都可以转换为迭代函数，因此变成 stack-safe，这正是您在 [=44= 中看到的].
还有一个缺点是算法的迭代版本可能被认为更难推理且可读性更差（但这值得商榷）。
递归也是一种在没有可变状态（循环计数器）的情况下执行 "loops" 的方法，因此您可以通过这种方式进行纯函数迭代（例如 Haskell
那么我们可以stack-safe、可读且高效的递归吗？是的，如果编译器可以将递归优化为与循环非常相似的代码。大多数 JVM 语言编译器（Groovy、Scala、Kotlin、Clojure 等等）都可以做到 tail-call optimalization。这意味着递归调用是函数执行的最后一件事，它将被编译为字节码，这看起来与普通的 while 循环非常相似。
其实有proposal对javac添加tail-call优化，但还没有实现。如果您现在想使用 stack-safe 递归，您可能需要使用其他一些 JVM 语言。