Scala factorial en grandes números a veces se bloquea y, a veces no se

Question

El programa siguiente, fue compilado y probado, a veces devuelve el resultado, y, a veces llena la pantalla con

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) 
... 

El programa:

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

Mis preguntas:

• ¿es porque hay un desbordamiento de pila en la JVM, que a veces ocurre y someti mes no?
• ¿Este comportamiento no determinista se considera un error?
• Supongo que Scala no reclutó la cola esto? ¿Cómo puedo hacer que esto sea recurrente?

Detalles:

Scala versión del compilador 2.7.5.final - Derechos de Autor 2002-2009, LAMP/EPFL Scala código de la versión corredor 2.7.5.final - Derechos de Autor 2002-2009 , LAMP/EPFL

java version "1.6.0_0" OpenJDK Runtime Environment (build 1.6.0_0-b11) OpenJDK VM cliente (build 1.6.0_0-b11, mixed mode, sharing)

Ubuntu 2.6.24-24-generic

Answer 1

optimización de llamada sólo funcionará en la Scala si la llamada recursiva es la última sentencia de la función. Es muy limitado El libro Scala dice:

[...] optimización de llamada se limita a situaciones en las que una función método o anidada llama a sí mismo directamente como su última operación, sin pasar por un valor de la función o algún otro intermediario

En su caso, la llamada recursiva es parte de una expresión más grande, y no es en sí misma la última operación - la última operación aquí es la multiplicación.

This article muestra cómo hacer que funcione:

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

En Scala 2.8 se puede utilizar la anotación @tailrec cuando se espera que la optimización de llamada de cola se debe utilizar, y obtener una advertencia si no es posible para la compilador para hacerlo.

Answer 3

Si realmente tiene un gran número, hay muchos approximations, por ejemplo éste en Scala que utiliza factorización prima:

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) 
} 

Uso:

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