java支持并优化尾递归调用吗？

Question

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

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()));
}

我想知道这个函数sum是否会在堆栈上增长,还是会被改为循环(因为它是一个尾递归函数)？

我刚刚读到Scala检测到这样的调用并对其进行优化但是这只是一个Scala专用的东西还是JVM？

Answer 1

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

但无论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 和 JVM 目前不支持尾调用

需要进行的基本工作是在 JVM 级别，而不是 Java。有一个缓慢移动的工作线来解决这个问题（最初作为MLVM现在在Project Loom下的一部分）。尽管相对较旧，但这篇来自 John Rose 的 2007 年博客很好且简短地概述了如何更改 JVM 字节码。我认为尾调用工作被搁置一旁，有利于invokedynamic先完成（这揭示了尾调用更棘手的设计注意事项）。以下是最新的 Project Loom 提案的摘录：

由于向 JVM 添加操作调用堆栈的能力无疑是必需的，因此该项目的目标也是添加一个更轻量级的构造，允许将堆栈展开到某个点，然后调用具有给定参数的方法（基本上，有效尾调用的概括）。我们将该功能称为 unwind-and-invoke 或 UAI。

其他一些细节：

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

  JavaScript 是一种尝试自动优化尾调用的语言示例（在 ES2015 中），这里是 V8 团队解释困难的汇报。他们已经删除了该功能，并转而支持一项仅在明确时才支持尾调用优化的提案。

  如果 JVM 在字节码级别添加对尾调用的支持，我推测 Java 也可能支持显式尾调用优化（即以 a 上的注释return或函数上的注释甚至可能是新关键字的形式） .

• Scala 尝试检测并优化到 JVM 字节码循环的尾递归。这是一个承诺对现有 JVM 字节码执行此类优化的项目。这个想法没有被 Java 采用，因为它有点脆弱和有限：

  1. 相互递归的函数变得非常棘手（Scala@tailrec只是放弃了）
  2. 多态递归不起作用
  3. 广义尾调用显然不起作用