java是否支持并优化了尾递归调用？

Question

假设我得到了一个尾部递归的递归函数。我想知道这个函数是否会被实现为递归，在堆栈上增长，还是会被更改为循环(因为它是一个尾递归函数)？

我刚刚读到Scala会检测到这类调用并对其进行优化，但这是Scala独有的还是一般意义上的JVM？

Answer 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，其中包含一个到目前为止计算出的sum参数。这样，当您在else分支中循环时，您不再需要实际的堆栈框架-您在递归调用中获得了作为函数参数所需的所有内容。

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

Answer 2

java中阶乘的尾递归，其空间复杂度为O(1)

  int tailFactorial(int x){
    return tailFactorial(x, 1);
}

int tailFactorial(int x, int totalFactor){
    if(x == 0){
        return totalFactor;
    }else{
        return tailFactorial(x-1, totalFactor * x);
    }

}