迹忆客 专注技术分享

本文讨论尾部调用优化（也称为 TCO）及其在 Java 中不存在的原因。 我们还将看到一些其他可以用来在 Java 中模拟 TCO 的方法。

什么是尾调用优化

尾调用优化是一个过程，我们可以避免为函数分配一个新的堆栈帧，因为调用函数将返回从被调用函数接收的值。

最常见的用途之一是尾递归（一种递归函数，其中函数在末尾调用自身），其中编写递归方法是为了利用尾调用优化，并且可以使用常量堆栈空间。

该方案是在规范中保证任何实现都必须服务于这种优化的编程语言之一。 因此，以下是Scheme编程语言中阶乘方法的两个示例。

示例代码一（无尾递归）：

(define (factorial n)
  (if (= n 0) 1
      (* n (factorial (- n 1)))))

示例代码二（带尾递归）：

(define (factorial n)
  (define (factorial-tail n accum)
    (if (= n 0) accum
        (factorial-tail (- n 1) (* n accum))))
  (factorial-tail n 1))

在示例代码一中，该函数不是尾递归的。 这是因为每当进行递归调用时（考虑阶乘示例），该方法必须跟踪调用返回后需要对结果执行的乘法。

因此，堆栈如下所示。

(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

相反，尾递归阶乘的堆栈跟踪如下所示。

(factorial 3)
(factorial-tail 3 1)
(factorial-tail 2 3)
(factorial-tail 1 6)
(factorial-tail 0 6)
6

我们只需要为每次调用 Factorial-tail 跟踪相同的数据。

原因是我们返回一个直接到达顶部的值，这意味着即使我们要调用（阶乘 1000000），我们也只需要与（阶乘 3）所需的空间量相同的空间。

当我们考虑非尾递归阶乘时，情况并非如此，大值可能会导致堆栈溢出。

Java中没有尾部调用优化的原因

目前，在编译器级别，普通 Java 不支持 Java 尾调用优化。 由于继承的存在，找出正在调用的方法可能不是一件容易的事。

另外，现有的堆栈计数机制不允许这种优化很快实现。 也许有理由避免每年语言工作方式发生巨大变化。

第一个原因是尾部调用优化的成本很高。 其次，根据 Java 中的一条规则，每当遇到错误时，我们都会获取堆栈跟踪。

堆栈跟踪是定义明确的概念，几乎无法跟踪每个逻辑调用的一个堆栈帧。 如果 Java 中存在尾调用优化，则这是不可能的。

第三，尾调用优化作为模型是做事的方式，但不是唯一的方式。 一般来说，对于任何可以编写为 TCO 递归应用程序的东西，重构为基于循环的非递归算法并不难。

那么，我们应该做什么呢？ 我们可以使用 while 或 for 循环来代替。

有没有办法在Java中模拟尾部调用优化

尽管 Java（虚拟机）具有可以使其他人的工作变得更容易的新功能，但非 Java 编程语言编译到类文件中以在 Java 运行时上执行以支持尾调用优化。

并非每个功能总是合理的，特别是当该语言是最流行的语言之一时。

因此，我们不确定应该使用什么方法在 Java 中使用 TCO； Project Loom 的提案对此进行了很好的解释。

然而，我们认为仍然可以使用一些其他方法来模拟 Java 中的尾调用优化。 第一种是使用其他 JVM 语言，例如 Scala。

第二种解决方案可以使用 lambda 表达式。