title: Scala recursion vs loop: performance and runtime considerations
body: <p>I've wrote a naïve test-bed to measure the performance of three kinds of factorial implementation: loop based, non tail-recursive and tail-recursive.</p>
  <blockquote>
  <p><em>Surprisingly to me <strong>the worst performant was the loop ones («while» was expected to be more efficient so I provided both)</strong>  that cost
  almost twice than the tail recursive alternative.</em></p>
  </blockquote>
  <p>*<em>ANSWER: fixing the loop implementation avoiding the <em>= operator which outperform worst with BigInt due to its internals «loops» became fastest as expected</em></em></p>
  <blockquote>
  <p>Another «woodoo» behavior I've experienced was the StackOverflow
  exception which wasn't thrown systematically for the same input in the
  case of non-tail recursive implementation. I can circumvent the
  StackOverlow by progressively call the function with larger and larger
  values… I feel crazy :) <strong>Answer: JVM require to converge during startup, then behavior is coherent and systematic</strong></p>
  </blockquote>
  <p>This is the code:</p>
  <pre><code>final object Factorial {
    type Out = BigInt
  
    def calculateByRecursion(n: Int): Out = {
      require(n&gt;0, &quot;n must be positive&quot;)
  
      n match {
        case _ if n == 1 =&gt; return 1
        case _ =&gt; return n * calculateByRecursion(n-1)
      }
    }
  
    def calculateByForLoop(n: Int): Out = {
      require(n&gt;0, &quot;n must be positive&quot;)
  
      var accumulator: Out = 1
      for (i &lt;- 1 to n)
        accumulator = i * accumulator
      accumulator
    }
  
    def calculateByWhileLoop(n: Int): Out = {
      require(n&gt;0, &quot;n must be positive&quot;)
  
      var accumulator: Out = 1
      var i = 1
      while (i &lt;= n) {
        accumulator = i * accumulator
        i += 1
      }
      accumulator
    }
  
    def calculateByTailRecursion(n: Int): Out = {
      require(n&gt;0, &quot;n must be positive&quot;)
  
      @tailrec def fac(n: Int, acc: Out): Out = n match {
        case _ if n == 1 =&gt; acc
        case _ =&gt; fac(n-1, n * acc)
      }
  
      fac(n, 1)
    }
  
    def calculateByTailRecursionUpward(n: Int): Out = {
      require(n&gt;0, &quot;n must be positive&quot;)
  
      @tailrec def fac(i: Int, acc: Out): Out = n match {
        case _ if i == n =&gt; n * acc
        case _ =&gt; fac(i+1, i * acc)
      }
  
      fac(1, 1)
    }
  
    def comparePerformance(n: Int) {
      def showOutput[A](msg: String, data: (Long, A), showOutput:Boolean = false) =
        showOutput match {
          case true =&gt; printf(&quot;%s returned %s in %d ms\n&quot;, msg, data._2.toString, data._1)
          case false =&gt; printf(&quot;%s in %d ms\n&quot;, msg, data._1)
      }
      def measure[A](f:()=&gt;A): (Long, A) = {
        val start = System.currentTimeMillis
        val o = f()
        (System.currentTimeMillis - start, o)
      }
      showOutput (&quot;By for loop&quot;, measure(()=&gt;calculateByForLoop(n)))
      showOutput (&quot;By while loop&quot;, measure(()=&gt;calculateByWhileLoop(n)))
      showOutput (&quot;By non-tail recursion&quot;, measure(()=&gt;calculateByRecursion(n)))
      showOutput (&quot;By tail recursion&quot;, measure(()=&gt;calculateByTailRecursion(n)))
      showOutput (&quot;By tail recursion upward&quot;, measure(()=&gt;calculateByTailRecursionUpward(n)))
    }
  }
  </code></pre>
  <p><strong>What follows is some output from sbt console (Before «while» implementation)</strong>:</p>
  <pre><code>scala&gt; example.Factorial.comparePerformance(10000)
  By loop in 3 ns
  By non-tail recursion in &gt;&gt;&gt;&gt;&gt; StackOverflow!!!!!… see later!!!
  ........
  
  scala&gt; example.Factorial.comparePerformance(1000)
  By loop in 3 ms
  By non-tail recursion in 1 ms
  By tail recursion in 4 ms
  
  scala&gt; example.Factorial.comparePerformance(5000)
  By loop in 105 ms
  By non-tail recursion in 27 ms
  By tail recursion in 34 ms
  
  scala&gt; example.Factorial.comparePerformance(10000)
  By loop in 236 ms
  By non-tail recursion in 106 ms     &gt;&gt;&gt;&gt; Now works!!!
  By tail recursion in 127 ms
  
  scala&gt; example.Factorial.comparePerformance(20000)
  By loop in 977 ms
  By non-tail recursion in 495 ms
  By tail recursion in 564 ms
  
  scala&gt; example.Factorial.comparePerformance(30000)
  By loop in 2285 ms
  By non-tail recursion in 1183 ms
  By tail recursion in 1281 ms
  </code></pre>
  <p><strong>What follows is some output from sbt console (After «while» implementation)</strong>:</p>
  <pre><code>scala&gt; example.Factorial.comparePerformance(10000)
  By for loop in 252 ms
  By while loop in 246 ms
  By non-tail recursion in 130 ms
  By tail recursion in 136 ns
  
  scala&gt; example.Factorial.comparePerformance(20000)
  By for loop in 984 ms
  By while loop in 1091 ms
  By non-tail recursion in 508 ms
  By tail recursion in 560 ms
  </code></pre>
  <p><strong>What follows is some output from sbt console (after «upward» tail recursion implementation) the world come back sane</strong>:</p>
  <pre><code>scala&gt; example.Factorial.comparePerformance(10000)
  By for loop in 259 ms
  By while loop in 229 ms
  By non-tail recursion in 114 ms
  By tail recursion in 119 ms
  By tail recursion upward in 105 ms
  
  scala&gt; example.Factorial.comparePerformance(20000)
  By for loop in 1053 ms
  By while loop in 957 ms
  By non-tail recursion in 513 ms
  By tail recursion in 565 ms
  By tail recursion upward in 470 ms
  </code></pre>
  <p><strong>What follows is some output from sbt console after fixing BigInt multiplication in «loops»: the world is totally sane</strong>:</p>
  <pre><code>    scala&gt; example.Factorial.comparePerformance(20000)
  By for loop in 498 ms
  By while loop in 502 ms
  By non-tail recursion in 521 ms
  By tail recursion in 611 ms
  By tail recursion upward in 503 ms
  </code></pre>
  <p>BigInt overhead and a <em>stupid</em> implementation by me masked the expected behavior.</p>
  <p><em>PS.: In the end I should re-title this post to «A lernt lesson on BigInts»</em></p>