scala - 减少大数据流而不会导致堆栈溢出

Question

1我正在尝试制作一个无极限的阶乘函数(只是出于好奇。)该函数适用于较大的n(尝试达到100000，并且似乎可以正常工作，尽管我无法检查输出值的正确性，因为，这是大!)

(BigInt(1) to n).reduceRight(_*_)

但是我担心整个BigInt(1) to n范围可能都在内存中，而对于reduceRight我只需要一个元素一个元素。看一下Scala的标准库代码，看起来BigInt(1) to n实际上输出了整个Range而不是一个懒惰的Stream，但是我发现了Stream.range可以像这样使用(注意n+1，流范围是排他的)

Stream.range[BigInt](BigInt(1), BigInt(n+1)).reduceRight(_*_)

它适用于n=10000(由于某种原因，它需要更长的时间!这使我认为正常范围实际上也可以是Stream吗？)，但是对于n=100000，我会得到此堆栈溢出

java.lang.StackOverflowError
    at java.math.BigInteger.add(Unknown Source)
    at scala.math.BigInt.$plus(BigInt.scala:161)
    at scala.math.Numeric$BigIntIsIntegral$class.plus(Numeric.scala:28)
    at scala.math.Numeric$BigIntIsIntegral$.plus(Numeric.scala:40)
    at scala.math.Numeric$BigIntIsIntegral$.plus(Numeric.scala:40)
    at scala.math.Numeric$Ops.$plus(Numeric.scala:208)
    at scala.collection.immutable.Stream$$anonfun$range$1.apply(Stream.scala:695)
    at scala.collection.immutable.Stream$$anonfun$range$1.apply(Stream.scala:695)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:634)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:626)
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:130)
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47)
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:131)
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47)
    at scala.collection.LinearSeqOptimized$class.reduceRight(LinearSeqOptimized.scala:131)
    at scala.collection.immutable.Stream.reduceRight(Stream.scala:47)
    ...

很明显reduceRight像这样自称

reduceRight(reduceRight(first, second, op), third, op)...

因此，堆栈溢出。我认为它不是优化的尾部调用，因为它首先减小然后在返回值之前运行，因此无法优化。那我该如何解决这个问题呢？我是否应该放弃功能性方法，而瞄准定制的命令式代码以减少代码量？

令我感到奇怪的是，对于大(BigInt(1) to n).reduceRight(_*_)，n不会溢出，而使用流几乎相同。

Answer 1

reduceLeft实现为在流上进行计算(并按顺序调用)。您可以验证如下:

Stream.range(1,10).map(i => print(i)).reduceLeft((a,b) => println("r"))

或者，您可以使用尾部递归:

final def fac(n: BigInt, prod: BigInt = BigInt(1)): BigInt = {
  if (n<2) prod else fac(n-1,prod*n)
}

(正如Travis指出的那样，先将小数字相乘会更快，这会花费额外的一行)。