Java是否支持并优化尾部递归调用？

optimization java recursion jvm scala

2022-09-01 17:36:52

假设我有一个尾递归的递归函数。我想知道这个函数是否会作为递归实现，在堆栈上增长，或者它会被更改为循环（因为它是一个尾递归函数）？

我刚刚读到Scala检测到这样的调用并对其进行优化，但这是Scala独有的东西还是一般的JVM？

答案 1

Java支持尾递归调用，但AFAIK它不会优化它们。我认为是Scala编译器能够做到这一点，而不是JVM本身。查看Scala中的注释，看看编译器还能做些什么:)@tailrec

但是，无论 Java/JVM 是否优化尾递归，您的函数都比必要的更难优化。

看看这个：

int sum(List<Integer> integers) {
    return sum(integers, 0);
}

int sum(List<Integer> integers, int sumSoFar) {
    if (integers.isEmpty())
        return sumSoFar;
    else
        return sum(
                integers.subList(1, integers.size()),
                sumSoFar + integers.get(0)
        );
}

看，我已经添加了一个重载，其中包含到目前为止计算的 sum 参数。这样，当您在分支中重复时，您不再需要实际的堆栈帧 - 您在递归调用中获得了所有需要的函数参数。sumelse

在您的代码段中，堆栈帧可能必须与递归调用一样存在。

答案 2

Java 和 JVM 目前不支持尾部调用

需要发生的基本工作是在JVM级别，而不是Java。有一个缓慢的工作线来解决这个问题（最初是作为MLVM的一部分，现在在Project Loom下）。尽管相对较旧，但John Rose的这篇2007年博客很好地概述了如何更改JVM字节码。我认为尾部调用工作被推到了一边，转而首先完成（这揭示了尾部调用的更棘手的设计考虑因素）。以下是最新的Project Loom提案的摘录：invokedynamic

由于毫无疑问需要将操作调用堆栈的能力添加到JVM中，因此该项目的目标也是添加一个重量更轻的构造，该构造将允许将堆栈展开到某个点，然后调用具有给定参数的方法（基本上是高效尾部调用的泛化）。我们将该功能称为展开和调用，或UAI。

其他一些细节：

Java作为一种语言不太可能自动优化尾部调用。这是因为大多数尾部调用消除的实现对调用堆栈都有一些不直观的影响（例如，如果您在递归调用中引发异常，则不会在堆栈跟踪中看到所有递归调用）。

JavaScript是一种试图自动优化尾部调用的语言的例子（在ES2015中），以下是V8团队的汇报，解释了这些困难。此后，他们删除了该功能，并转而支持仅在显式支持尾部调用优化的提案。

如果JVM在字节码级别添加了对尾部调用的支持，我推测Java也可能支持显式尾部调用优化（即以对a的注释或对函数的注释的形式，甚至可能是一个新的关键字）。return
Scala试图检测并优化尾递归到JVM字节码循环中。这是一个承诺对现有JVM字节码执行这种优化的项目。这个想法没有被Java采用，因为它有点脆弱和有限：
1. 互递归函数变得非常棘手（Scala只是放弃了）@tailrec
2. 多态递归不起作用
3. 广义的尾部调用显然不起作用