深度递归在 Java 中是有问题的

考虑以下使用递归添加两个正数的天真方法：

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

这在算法上是正确的，但它有一个主要问题。如果你用一个大的 a 调用 add，它会在任何版本的 Java（至少）Java 9 上使用 StackOverflowError 崩溃。

在典型的函数编程语言（以及许多其他语言）中，编译器优化尾递归 。编译器会注意到对 add 的调用（在标记行处）是一个尾调用 ，并且会有效地将递归重写为循环。这种转换称为尾调用消除。

但是，当前的 Java 编译器不执行尾部调用消除。 （这不是一个简单的疏忽。这有很多技术原因;见下文。）相反，add 的每次递归调用都会导致在线程堆栈上分配一个新帧。例如，如果你调用 add(1000, 1)，它将需要 1000 递归调用才能得到答案 1001。

问题是创建线程时 Java 线程堆栈的大小是固定的。 （这包括单线程程序中的主线程。）如果分配的堆栈帧太多，则堆栈将溢出。JVM 将检测到这一点并抛出一个 StackOverflowError。

解决这个问题的一种方法是简单地使用更大的堆栈。有 JVM 选项可以控制堆栈的默认大小，你还可以将堆栈大小指定为 Thread 构造函数参数。不幸的是，这只会推迟堆栈溢出。如果你需要做一个需要更大堆栈的计算，那么 StackOverflowError 会回来。

真正的解决方案是识别可能进行深度递归的递归算法，并在源代码级别手动执行尾调用优化。例如，我们的 add 方法可以重写如下：

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

（显然，有更好的方法可以添加两个整数。上面只是为了说明手动尾部消除的效果。）

为什么在 Java 中没有实现尾调用消除（尚未）

将尾调用消除添加到 Java 并不容易的原因有很多。例如：

• 一些代码可以依赖于 StackOverflowError（例如）对计算问题的大小设置一个界限。
• 在决定是否允许非特权代码执行特权操作时，沙盒安全管理器通常依赖于分析调用堆栈。

正如 John Rose 在 “VM 中的尾调用”中所说 ：

“删除调用者的堆栈帧的效果对于某些 API 是可见的，特别是访问控制检查和堆栈跟踪。就好像调用者的调用者直接调用了被调用者。调用者拥有的任何特权在控制转移到调用者之后被丢弃。然而，在转移控制之前计算被调用方法的链接和可访问性，并考虑尾调用调用者。

换句话说，尾部调用消除可能导致访问控制方法错误地认为可信代码正在调用安全敏感 API。