大数阶乘斯卡拉有时会崩溃，有时不(Scala factorial on large numbers

下面的程序，编译和测试，它有时会返回结果，有时充满屏幕，

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编译器版本2.7.5.final - 版权所有2002-2009，LAMP / EPFL Scala代码亚军版本2.7.5.final - 版权所有2002-2009，LAMP / EPFL

Java版本 “1.6.0_0” 的OpenJDK运行时环境（建1.6.0_0-B11）OpenJDK的客户端虚拟机（建设1.6.0_0-B11，混合模式，共享）

Ubuntu的2.6.24-24泛型

Answer 1:

尾部调用优化仅在斯卡拉工作，如果递归调用是函数的最后一条语句。 这是非常有限的。 斯卡拉书中说：

[...]尾调用优化被限制于其中的方法或嵌套函数调用自身直接作为其最后一个操作的情况下，不通过函数值或一些其它中间去。

在你的情况下，递归调用是一个更大的表达式的一部分，而不是本身的最后操作 - 在这里最后一次操作是乘法。

本文介绍如何使其工作：

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:

在斯卡拉2.8当你想到应使用尾部调用优化可以使用@tailrec注释，并得到一个警告，如果这是不可能的编译器这样做。

Answer 3:

如果你真的有大的数字，有很多近似 ，比如这一个Scala中使用质数分解：

class SwingFactorial(n: Int) {

  def name() = "SwingFactorial"

  def value(): BigInt =
    {
      if (n < 0)
         {
          throw new IllegalArgumentException(
          "Factorial: n has to be >= 0, but was " + n)
         }

      ndiv2OddFact = BigInt(1)
      ndiv4OddFact = ndiv2OddFact

      return oddFactorial(n) << (n - MathFun.bitCount(n))
    }

  private def oddFactorial(n: Int): BigInt =
    {
      val oddFact =
      if (n < Small.oddFactorial.length)
        {
          BigInt(Small.oddFactorial(n))
        }
      else
        {
          val of = oddFactorial(n / 2)
          (of * of) * oddSwing(n)
        }

      ndiv4OddFact = ndiv2OddFact
      ndiv2OddFact = oddFact
      return oddFact
    }

  private def oddSwing(n: Int): BigInt =
    {
      if (n < Small.oddSwing.length)
      {
        return BigInt(Small.oddSwing(n))
      }

      val len = if ((n % 4) != 2) (n - 1) / 4 + 1 else (n - 1) / 4
      val high = n - ((n + 1) & 1)
      val ndiv4 = n / 4
      val oddFact = if (ndiv4 < Small.oddFactorial.length)
            BigInt(Small.oddFactorial(ndiv4)) else ndiv4OddFact

      return product(high, len) / oddFact
    }

    private def product(m: Int, len: Int): BigInt =
    {
      if (len == 1) return BigInt(m) 
      if (len == 2) {val M = m.toLong; return BigInt(M * (M - 2))}

      val hlen = len >>> 1
      return product(m - hlen * 2, len - hlen) * product(m, hlen)
    }

  private var ndiv4OddFact = BigInt(1)
  private var ndiv2OddFact = BigInt(1)
} 

用法：

var fs = new SwingFactorial(n)
val a = fs.value()

文章来源: Scala factorial on large numbers sometimes crashes and sometimes doesn't