Scala факториал на больших количествах иногда падает, а иногда не

Следующая программа была скомпилирована и протестирована, она иногда возвращает результат и иногда заполняет экран с помощью

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 - Copyright 2002-2009, LAMP/EPFL Scalaкод runner version 2.7.5.final - Copyright 2002-2009, LAMP/EPFL

java version "1.6.0_0" OpenJDK Среда выполнения (build 1.6.0_0-b11) OpenJDK Client VM (сборка 1.6.0_0-b11, смешанный режим, совместное использование)

Ubuntu 2.6.24-24-generic

Ответы

Ответ 1

Оптимизация Tail-call будет работать только в 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)
  }
}

Ответ 2

В Scala 2.8 вы можете использовать аннотацию @tailrec, когда вы ожидаете, что оптимизация хвостового вызова должна быть использована, и получите предупреждение, если это невозможно для компилятора.

Ответ 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()