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:
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
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)
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With