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-b…

Accepted Answer

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

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

Solution

Problem