斯卡拉階乘不

下面的程序，編譯和測試，它有時會返回結果，有時填充有斯卡拉階乘不

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

斯卡拉階乘不

回答

相關問題