大数的Scala阶乘有时会崩溃,有时则不会崩溃

Question

以下程序经过编译和测试,有时会返回结果,有时会填满屏幕

java.lang.StackOverflowError
at scala.BigInt$.apply(BigInt.scala:47)
at scala.BigInt.equals(BigInt.scala:129)
at scala.runtime.BoxesRunTime.equals(Unknown Source)
at bigint$.factorial(fact2.scala:3)
at bigint$.factorial(fact2.scala:3)
...

该程序:

object bigint extends Application {
  def factorial(n: BigInt): BigInt = if (n == 0) 1 else n * factorial(n-1)
  println("4391! = "+factorial(4391))
}

我的问题:

• 是因为JVM上存在堆栈溢出,有时会发生,有时却不会？
• 这种不确定行为是否被视为错误？
• 我假设Scala没有尾递归这个？我怎么能让它尾巴递归呢？

细节:

Scala编译器版本2.7.5.final - 版权所有2002-2009,LAMP/EPFL Scala代码运行器版本2.7.5.final - 版权所有2002-2009,LAMP/EPFL

java版"1.6.0_0"OpenJDK运行时环境(build 1.6.0_0-b11)OpenJDK客户端VM(版本1.6.0_0-b11,混合模式,共享)

Ubuntu 2.6.24-24-通用

Answer 1

如果递归调用是函数中的最后一个语句,则尾调用优化仅适用于Scala.这是非常有限的.Scala的书说:

[...]尾部调用优化仅限于方法或嵌套函数直接将其自身称为最后一个操作的情况,而不通过函数值或其他中介.

在你的情况下,递归调用是一个更大的表达式的一部分,并且它本身不是最后一个操作 - 这里的最后一个操作是乘法.

本文演示了如何使其工作:

class Factorial {
  def factorial(n: Int): Int = {
    def factorialAcc(acc: Int, n: Int): Int = {
      if (n <= 1) acc
      else factorialAcc(n * acc, n - 1)
    }
    factorialAcc(1, n)
  }
}

Answer 2

在Scala 2.8中,当您期望应该使用尾调用优化时,可以使用@tailrec注释,如果编译器无法执行此操作,则会收到警告.