sat*_*h m 2 java recursion binary-search
为什么java.util.Arrays中的binarySearch()方法使用循环而不是使用递归来实现？
tl; dr：因为javac不执行尾部调用优化。
您可能已经注意到，许多算法本质上都是递归的（二进制搜索是一个很好的例子）。那么为什么递归在Java中没有得到广泛使用呢？
第一个原因是递归的性能不如普通循环。其次，一个更重要的原因是Java中的递归不是堆栈安全的。如果您的递归将深入到调用堆栈中，则可能会导致StackOverflowError。这是有问题的，因为您不能真正预测要走的深度，这取决于您处理的数据。这样的结果是您的递归函数可能会在较小的数据集上正常工作，但会炸毁较大的数据集上的堆栈。
幸运的是，通过将递归调用替换为迭代控制结构，可以将每个递归函数转换为迭代函数，从而使其成为栈安全的，而这正是在java.util.Arrays中看到的。
还有一个缺点是，迭代算法的版本可能被认为较难推理且可读性较差（但这值得商bat）。
递归也是一种在没有可变状态（循环计数器）的情况下进行“循环”的方法，因此您可以执行纯函数式的迭代（例如，Haskell 甚至没有循环，它仅取决于递归）。
那么，我们可以进行堆栈安全，可读和高性能的递归吗？是的，如果编译器可以优化递归以使代码与循环非常相似。大多数JVM语言编译器（Groovy，Scala，Kotlin，Clojure甚至更多）都可以进行尾调用优化。这意味着递归调用是函数的最后一件事，它将被编译为字节码，这与普通的while循环非常相似。
实际上，有人建议将尾调用优化添加到javac，但尚未实现。如果要立即使用堆栈安全递归，则可能需要使用其他JVM语言。