在JVM中运行时在Scala中使用递归

从在此站点和Web上搜索其他位置，JVM不支持尾部调用优化。那么这是否意味着如果要在非常大的输入列表上运行的尾部递归Scala代码（如以下代码），如果要在JVM上运行，则不应该被写入？在JVM中运行时在Scala中使用递归

// Get the nth element in a list  
def nth[T](n : Int, list : List[T]) : T = list match { 
      case Nil => throw new IllegalArgumentException 
      case _ if n == 0 => throw new IllegalArgumentException 
      case _ :: tail if n == 1 => list.head 
      case _ :: tail => nth(n - 1, tail) 
}

马丁·奥德斯基的斯卡拉通过示例包含以下段落，这似乎表明，有环境或其他环境中的递归是合适的：

原则，尾调用可以随时重新使用堆栈呼叫函数的帧。但是，某些运行时环境（如Java VM）缺少基元以使堆栈帧重新用于尾部调用。生产质量因此，Scala实现仅需要重用直接尾递归函数的堆栈帧，其最后一个操作是对其自身的调用。其他尾部呼叫也可能被优化，但是不应该依赖于这个跨越实现。

任何人都可以解释这段中间的两句话是什么意思？

谢谢！

来源

2011-04-17 gw111zz

可能的重复http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations – 2011-04-17 20:29:16

由于直接尾递归相当于一个while循环，你的榜样将高效运行在JVM上，因为Scala的编译器可以将这个引擎盖下的环路，只需使用一个跳跃。然而，通用TCO在JVM上不受支持，尽管可用tailcall（）方法支持使用编译器生成的trampolines进行尾调用。

为了确保编译器能够正确地优化尾递归函数的循环，你可以使用scala.annotation.tailrec注释，这将导致一个编译错误，如果编译器不能进行所需的优化：

import scala.annotation.tailrec 

@tailrec def nth[T](n : Int, list : List[T]) : Option[T] = list match { 
      case Nil => None 
      case _ if n == 0 => None 
      case _ :: tail if n == 1 => list.headOption 
      case _ :: tail => nth(n - 1, tail) 
}

（螺丝IllegalArgmentException！）

来源

2011-04-17 20:56:48

Scala编译器将尝试通过“扁平化”他们进入一个循环，不会造成一个不断扩大堆栈优化尾调用。

当然，你的代码必须优化才能这样做。如果你在方法之前使用注解@tailrec（scala.annotation.tailrec），那么编译器会要求该方法可优化或不能编译。

来源

2011-04-17 20:57:44

Martin的评论是说只有直接自递归调用才是TCO优化的候选者（满足其他标准）。间接的，相互递归的方法对（或更大的递归方法集）不能如此优化。

来源

2011-04-17 22:07:33

在原理上，尾调用可以随时重新使用主叫函数的堆栈帧。但是，某些运行时环境（例如Java VM）缺少基元，以便为高效调用尾部调用重新使用堆栈帧。生产质量因此，只需要Scala实现来重新使用直接尾递归函数的堆栈帧，其最后一个操作是对其自身的调用。其他尾部呼叫也可能被优化，但是不应该依赖于这个跨越实现。

任何人都可以解释这段中间的两句话是什么意思？

尾递归是尾调用的特例。直接尾部递归是尾部递归的特例。只有直接尾部递归保证被优化。其他可能也被优化，但这基本上只是一个编译器优化。作为语言特性，斯卡拉只保证直接尾部递归消除。

那么，有什么区别？

好，一尾调用是简单地在一个子程序最后一次通话：

def a = { 
    b 
    c 
}

在这种情况下，调用c是尾调用，调用b不是。

尾递归是当一个尾调用调用一个已经被调用的子程序前：

def a = { 
    b 
} 

def b = { 
    a 
}

这是尾递归：a调用b（尾调用），这反过来又调用a。（与下面描述的直接尾部递归相反，这有时被称为间接尾递归。）

但是，这两个例子中没有一个会被Scala优化。或者，更确切地说：一个Scala实现允许允许来优化它们，但它不是要求这样做。这与例如方案，其中语言规范保证所有上述情况下将需要O(1)堆栈空间。

Scala语言规范仅保证直接尾递归被优化，即，当一个子程序直接呼叫本身在它们之间没有其他的呼叫：

def a = { 
    b 
    a 
}

在这种情况下， a的调用是一个尾调用（因为它是子程序中的最后一个调用），它是尾递归（因为它再次调用自己），最重要的是它是直接尾递归，因为a直接调用它自己而不先通过另一个调用。

请注意，有很多微妙的事情可能导致方法不直接尾递归。例如，如果a被重载，则递归实际上可能会经历不同的重载，因此不再是直接的。

在实践中，这意味着两件事情：

你不能在尾递归方法执行提取方法重构，至少不包括尾部调用，因为这会变成一个直接尾递归方法（这将得到优化）成间接尾递归方法（不会得到优化）。
你可以只有使用直接尾递归。尾递归下降解析器或状态机可以使用间接尾递归非常优美地表达出来。

造成这种情况的主要原因是，当你的底层执行引擎缺乏强大的控制流处理功能，如GOTO，延续，一流可变栈或适当的尾调用，那么你需要无论是在实现自己的堆栈最重要的是，使用蹦床，进行全球CPS变换或类似的讨厌的事情，以便提供广义的适当尾巴呼叫。所有这些对性能或与同一平台上的其他代码的互操作性都有严重影响。或者，正如Clojure的创始人Rich Hickey所说，他面临同样的问题时：“性能，Java互操作性，尾部调用，挑选两个”。 Clojure和Scala都选择在尾部呼叫上妥协，只提供尾部递归而不是全部尾部呼叫。

长话短说：是的，您发布的具体示例将被优化，因为它是直接尾部递归。您可以通过在该方法上添加一个@tailrec注释来测试。注释不会改变方法是否得到优化，但会确保不过会保证您会得到一个编译错误，如果方法可以不是被优化。

由于上述的细微之处，在需要优化的方法上添加注释通常是一个好主意，这既是为了获得编译错误，也是为了让其他开发人员维护你的代码。

来源

2011-04-18 02:23:59

请注意，是支持尾部调用优化的JVM（IIRC和IBM的J9），但这只是JLS中的一项要求，而Oracle的实现并不能实现。

来源

2011-04-18 09:55:33 Landei

+1，但's/JLS/JVMS /'。 – 2011-04-22 00:21:43

在JVM中运行时在Scala中使用递归

回答

相关问题