Scala thừa trên một số lượng lớn đôi khi bị treo và đôi khi không

Question

Các chương trình sau đây, được biên soạn và thử nghiệm, đôi khi nó trả về kết quả, và đôi khi lấp đầy màn hình với

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

Chương trình:

object bigint extends Application { 
    def factorial(n: BigInt): BigInt = if (n == 0) 1 else n * factorial(n-1) 
    println("4391! = "+factorial(4391)) 
} 

câu hỏi của tôi:

• có phải vì có một chồng tràn trên JVM, mà đôi khi xảy ra và someti mes không?
• Hành vi không xác định này có được coi là lỗi không?
• Tôi cho rằng Scala đã không tính toán lại điều này? làm thế nào tôi có thể làm cho nó đuôi recurse này?

chi tiết:

Scala biên dịch phiên bản 2.7.5.final - Copyright 2002-2009, LAMP/EPFL Scala mã phiên bản Á hậu 2.7.5.final - Copyright 2002-2009 , LAMP/EPFL

phiên bản java "1.6.0_0" OpenJDK Runtime Environment (xây dựng 1.6.0_0-b11) OpenJDK khách hàng VM (xây dựng 1.6.0_0-b11, chế độ hỗn hợp, chia sẻ)

Ubuntu 2.6.24-24-generic

Answer 1

Tối ưu hóa cuộc gọi đuôi sẽ chỉ hoạt động trong Scala nếu cuộc gọi đệ quy là phát biểu cuối cùng trong hàm. Nó rất hạn chế. Cuốn sách Scala nói:

[...] tối ưu hóa đuôi gọi là giới hạn với các tình huống trong đó một phương pháp hoặc lồng chức năng tự gọi mình trực tiếp như hoạt động cuối cùng của nó, mà không cần trải qua một giá trị hàm hoặc một số trung gian khác.

Trong trường hợp của bạn, cuộc gọi đệ quy là một phần của biểu thức lớn hơn và không phải là thao tác cuối cùng - thao tác cuối cùng ở đây là phép nhân.

This article chứng minh làm thế nào để làm cho nó hoạt:

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

Answer 2

Trong Scala 2.8 bạn có thể sử dụng chú thích @tailrec khi bạn hy vọng rằng tối ưu hóa cuộc gọi đuôi nên được sử dụng, và nhận được một cảnh báo nếu nó không phải là có thể cho trình biên dịch để làm như vậy.

Answer 3

Nếu bạn thực sự có số lượng lớn, có nhiều approximations, ví dụ thế này ở Scala có sử dụng nguyên tố:

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

Cách sử dụng:

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