Scala factorial on large numbers sometimes crashes and sometimes doesn't

Question

The following program, was compiled and tested, it sometimes return the result, and sometimes fills the screen with

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

The program:

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

My questions:

• Is it because there is a stack overflow on the JVM, which sometimes happens and sometimes doesn't?
• Is this nondeterministic behavior considered a bug?
• I assume Scala did not tail-recursed this? how can I make it tail-recurse this?

Details:

Scala compiler version 2.7.5.final -- Copyright 2002-2009, LAMP/EPFL Scala code runner version 2.7.5.final -- Copyright 2002-2009, LAMP/EPFL

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

Ubuntu 2.6.24-24-generic

Answer 1

Tail-call optimization will only work in Scala if the recursive call is the last statement in the function. It's very limited. The Scala book says:

[...] tail-call optimization is limited to situations in which a method or nested function calls itself directly as its last operation, without going through a function value or some other intermediary.

In your case, the recursive call is part of a larger expression, and is not itself the very last operation - the last operation here is the multiplication.

This article demonstrates how to make it work:

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

In Scala 2.8 you can use the @tailrec annotation when you expect that tail call optimization should be used, and get a warning if it's not possible for the compiler to do so.