Scala 对大数的阶乘有时会崩溃，有时不会

Question

下面的程序，经过编译和测试，它有时返回结果，有时充满屏幕

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

只有当递归调用是函数中的最后一个语句时，尾部调用优化才在 Scala 中起作用。这是非常有限的。 Scala 书中说:

[...] 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.

在您的情况下，递归调用是较大表达式的一部分，并且本身并不是最后一个操作 - 这里的最后一个操作是乘法。

This article演示如何使其工作:

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