大量的Scala阶乘有时会崩溃，有时却不会 [英] Scala factorial on large numbers sometimes crashes and sometimes doesn't

问题描述

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

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

程序:

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编译器版本2.7.5.final- LAMP/EPFL Scala版权所有2002-2009 代码运行程序版本2.7.5.final- 版权所有2002-2009，LAMP/EPFL

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版本"1.6.0_0" OpenJDK 运行时环境(构建 1.6.0_0-b11)OpenJDK客户端VM(内部版本1.6.0_0-b11，混合模式，共享)

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

Ubuntu 2.6.24-24-generic

推荐答案

如果递归调用是函数中的最后一条语句，则尾调用优化将仅在Scala中起作用.这是非常有限的. Scala书中说:

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阶乘有时会崩溃，有时却不会的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！