斯卡拉阶乘不

下面的程序，编译和测试，它有时会返回结果，有时填充有斯卡拉阶乘不

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上，有时会发生，someti堆栈溢出mes不？
这种非确定性行为是否被视为一个错误？
我认为斯卡拉没有尾递归呢？我怎样才能让它尾巴缓解呢？

详情：

Scala编译器版本2.7.5.final - 版权所有2002-2009，LAMP/EPFL的Scala代码亚军版本2.7.5.final - 版权所有2002-2009 ，LAMP/EPFL

Java版本 “1.6.0_0” 的OpenJDK 运行时环境（建立 1.6.0_0-B11）的OpenJDK客户机VM（建立1.6.0_0-B11，混合模式，共享）

Ubuntu的2.6.24-24-通用

来源

2009-07-27 Liran Orevi

你的“couldn”的意思t看到这个“第一行”？你可以将输出传送到文件中吗？ – msi 2009-07-27 10:35:36

@msiemeri，奇怪的是当我“scala bigint>文件”只有在程序没有粉碎时才起作用。 – 2009-07-27 10:43:00

您是否尝试过“scala bigint> file 2>＆1”？用2>＆1将stderr的输出重定向到标准输出接收器（在本例中为'文件'）。 – msi 2009-07-27 12:03:50

尾部调用优化仅在斯卡拉工作，如果递归调用是函数的最后一条语句。这是非常有限的。斯卡拉书上说：

[...]尾调用优化限于在一个方法或嵌套函数调用自身直接作为其最后一个操作，不通过函数值会情况或其他一些中介。

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

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

来源

2009-07-27 10:20:03 skaffman

在斯卡拉2.8，你可以在你所期望应使用尾部调用优化使用@tailrec注释，并得到一个警告，如果这是不可能的编译器这样做。

来源

2009-09-23 08:33:58

如果你真的有大的数字，有很多approximations，例如这一个Scala中使用因式分解：

class SwingFactorial(n: Int) { 

    def name() = "SwingFactorial" 

    def value(): BigInt = 
    { 
     if (n < 0) 
     { 
      throw new IllegalArgumentException(
      "Factorial: n has to be >= 0, but was " + n) 
     } 

     ndiv2OddFact = BigInt(1) 
     ndiv4OddFact = ndiv2OddFact 

     return oddFactorial(n) << (n - MathFun.bitCount(n)) 
    } 

    private def oddFactorial(n: Int): BigInt = 
    { 
     val oddFact = 
     if (n < Small.oddFactorial.length) 
     { 
      BigInt(Small.oddFactorial(n)) 
     } 
     else 
     { 
      val of = oddFactorial(n/2) 
      (of * of) * oddSwing(n) 
     } 

     ndiv4OddFact = ndiv2OddFact 
     ndiv2OddFact = oddFact 
     return oddFact 
    } 

    private def oddSwing(n: Int): BigInt = 
    { 
     if (n < Small.oddSwing.length) 
     { 
     return BigInt(Small.oddSwing(n)) 
     } 

     val len = if ((n % 4) != 2) (n - 1)/4 + 1 else (n - 1)/4 
     val high = n - ((n + 1) & 1) 
     val ndiv4 = n/4 
     val oddFact = if (ndiv4 < Small.oddFactorial.length) 
      BigInt(Small.oddFactorial(ndiv4)) else ndiv4OddFact 

     return product(high, len)/oddFact 
    } 

    private def product(m: Int, len: Int): BigInt = 
    { 
     if (len == 1) return BigInt(m) 
     if (len == 2) {val M = m.toLong; return BigInt(M * (M - 2))} 

     val hlen = len >>> 1 
     return product(m - hlen * 2, len - hlen) * product(m, hlen) 
    } 

    private var ndiv4OddFact = BigInt(1) 
    private var ndiv2OddFact = BigInt(1) 
}

用法：

var fs = new SwingFactorial(n) 
val a = fs.value()

来源

2011-11-10 20:03:51 Renaud

斯卡拉阶乘不

回答

相关问题