title: Reducing a large stream without stack overflowing
body: <p>1I'm trying to make a limit-less factorial function (just out of curiosity.) This works for large <code>n</code> (tried up to 100000 and it seems to work, although I can't check the output value for correctness because, well, it's LARGE!)</p>
  
  <pre><code>(BigInt(1) to n).reduceRight(_*_)
  </code></pre>
  
  <p>But I'm afraid that the whole <code>BigInt(1) to n</code> range might be in memory, while I just need it element by element for <code>reduceRight</code>. Taking a look at Scala's standard library code it looks like <code>BigInt(1) to n</code> actually outputs the whole <code>Range</code> and not a lazy <code>Stream</code> but I found <code>Stream.range</code> which I can use like this (notice the <code>n+1</code>, stream range is exclusive)</p>
  
  <pre><code>Stream.range[BigInt](BigInt(1), BigInt(n+1)).reduceRight(_*_)
  </code></pre>
  
  <p>It works for <code>n=10000</code> (for some reason it takes a little bit longer! which makes me think that maybe the normal range is actually a <code>Stream</code> too?) but for <code>n=100000</code> I get this stack overflow</p>
  
  <pre><code>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)
      ...
  </code></pre>
  
  <p>It's obvious that <code>reduceRight</code> is calling itself like this</p>
  
  <pre><code>reduceRight(reduceRight(first, second, op), third, op)...
  </code></pre>
  
  <p>And thus the stack overflow. I assume it's not tail-call optimized because it first reduces and then operates prior to returning the value, so it can't be optimized. How could I approach this problem then? Should I ditch the functional approach and aim for custom imperative-style code for reducing?</p>
  
  <p>What strikes me as a very odd thing is that the <code>(BigInt(1) to n).reduceRight(_*_)</code> does not overflow for large <code>n</code> while almost the same using a stream does... What's going on here?</p>