Stack Overflow on running tail recursive method

Question

I test the performance of the tail recursion optimization in Scala. So I test it in both eclipse and sbt. However, I only get the result that the tail recursion version works much worse than the normal. I wonder the reason for it.

And here's my code.

package MyList

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List { // companion object

  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    case Cons(x, xs) => x+sum(xs)
  }

  def sum_tail_recursion(ints: List[Int]): Int = {
    @scala.annotation.tailrec
    def helper(ls: List[Int], res: Int): Int = ls match {
      case Nil => res
      case Cons(x, xs) => helper(xs, res+x)
    }
    helper(ints, 0)
  }

  def generate_tail_recursion(n: Int): List[Int] = {
    @scala.annotation.tailrec
    def helper(x: Int, ls: List[Int]): List[Int] = x match {
      case 0 => ls
      case x => helper(x-1, Cons(x, ls))
    }
    helper(n, Nil)
  }

  def generate(n: Int): List[Int] = n match {
    case 0 => Nil
    case x => Cons(x, generate(x-1))
  }

  def time[A](block: => A): A = {
    val t0 = System.nanoTime()
    val result = block
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1-t0) + "ns")
    result
  }
}

Additionally, I find that generate(10000) will cause the stack overflow but generate_tail_recursion(10000) won't. (But the latter one will cause some toString error. How can I solve it?) So, how can I improve the performance by using tail recursion in Scala? Thanks!

Update:

Here's the errors.

When I run 'generate(10000)':

java.lang.StackOverflowError at scala.runtime.BoxesRunTime.boxToInteger(BoxesRunTime.java:70) at MyList.List$.generate(List.scala:56) at MyList.List$.generate(List.scala:56) at MyList.List$.generate(List.scala:56) at MyList.List$.generate(List.scala:56)

When I run generate_tail_recursion(10000):

java.lang.StackOverflowError at scala.collection.AbstractIterator.addString(Iterator.scala:1157) at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:286) at scala.collection.AbstractIterator.mkString(Iterator.scala:1157) at scala.runtime.ScalaRunTime$._toString(ScalaRunTime.scala:170) at MyList.Cons.toString(List.scala:5) at java.lang.String.valueOf(Unknown Source) at scala.collection.mutable.StringBuilder.append(StringBuilder.scala:197) at scala.collection.TraversableOnce$$anonfun$addString$1.apply(TraversableOnce.scala:327) at scala.collection.Iterator$class.foreach(Iterator.scala:727) at scala.collection.AbstractIterator.foreach(Iterator.scala:1157) at scala.collection.TraversableOnce$class.addString(TraversableOnce.scala:320) at scala.collection.AbstractIterator.addString(Iterator.scala:1157) at scala.collection.TraversableOnce$class.mkString(TraversableOnce.scala:286) at scala.collection.AbstractIterator.mkString(Iterator.scala:1157) at scala.runtime.ScalaRunTime$._toString(ScalaRunTime.scala:170)

When you say 'tail recursion version works much worse than the normal', do you mean the runtime speed is worse, or that you're getting this error? — Yawar, Oct 14 '16 at 04:23
@Yawar I mean the runtime speed. Theoretically, the tail recursion version should be faster than the normal, right? — OtosakaYuu, Oct 14 '16 at 05:28

score 1 · Answer 1 · edited May 23 '17 at 12:16

Probably the most unexpected thing here is that you seem to be getting a stack overflow from the tail-recursive version of your method, so I will explain why that is happening.

Simply put, it's because you're running generate_tail_recursion(10000) on the console. That is forcing the JVM to try to build a String describing the entire 10,000-element list and then print it. As you can imagine, that would be a massive string because it would look something like Cons(1,Cons(2,Cons(3,...,Cons(10000,Nil)...))). You can confirm this for yourself by just running generate_tail_recursion(10) to see a tiny version of this. So that is what is overflowing your stack.

To avoid printing the whole list immediately, you need to define it in a method body, e.g.:

object Main {
  private val Size = 10000

  def main(args: Array[String]): Unit = {
    val list = List time (List generate_tail_recursion Size)
    //val list2 = List time (List generate Size)
  }
}

To understand clearly exactly what Scala does with the @annotation.tailrec, see https://stackoverflow.com/a/1682912/20371

I got you. But in the REPL, when I generate a List, it will automatically print it out, and I don't find any method to deal with it. So I will just fail to generate my list in the REPL. — OtosakaYuu, Oct 14 '16 at 05:34

Stack Overflow on running tail recursive method

1 Answers1