java支持并优化尾递归调用吗？ [英] Does java support and optimize away tail-recursive calls?

问题描述

假设我有一个尾递归的递归函数。

Say I got a recursive function that is tail-recursive.

System.out.println( sum(Arrays.asList(0, 1, 2, 3, 4, 5)) );

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

我想知道这个函数是否总和会在堆栈上增长还是会被改为循环（因为它是一个尾递归函数）？

I wonder if this function sum will grow on stack or will it be changed to a loop (since it is a tail-recursive function)?

我刚刚读到Scala检测到这样的调用并对其进行优化但是这只是一个Scala-only或JVM？

I have just read that Scala detects such calls and optimizes it but is this a Scala-only thing or JVM in general?

推荐答案

Java支持尾递归调用，但AFAIK并没有对它们进行优化。我认为Scala编译器只是能够做到这一点，而不是JVM本身。查看Scala中的 @tailrec 注释，看看编译器能够做什么：）

Java supports tail-recursive calls, but AFAIK it doesn't optimize them away. I think it's the Scala compiler that is simply capable of this, not the JVM itself. Check out the @tailrec annotation in Scala to see what more the compiler is capable of :)

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

But regardless of whether Java/JVM optimizes tail-recursion away, your function would be harder to optimize than necessary.

看看这个：

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参数。这样当你在 else 分支中重复出现时，你不再需要实际的堆栈框架了 - 你在递归调用中得到了所有你需要的函数参数。

See, I've added an overloaded sum with a so-far calculated sum parameter. This way when you recur in the else branch you don't need the actual stack frame any more - you got all you need as function arguments in the recursive call.

在你的代码片段中，只要递归调用，堆栈帧就可能必须存在..

In your snippet the stack frame would probably have to exist as long as the recursive call..

这篇关于java支持并优化尾递归调用吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！