CODEWITHSUNDEEP
scalatail-recursion
Sameer Kohli
Sameer Kohli

Reputation: 5

Recursive function throw StackOverflowError

I am having problems with this function. I need to process more than 1 million records, but this crashes. Looks like just works with thousands of records and throws a StackOverflowError for a larger list. Any suggestions?

def split(list: List[(Pair, Boolean)]): List[List[Pair]] = list match {
  case Nil => Nil
  case head :: tail => {
    val (l1, l2) = tail.span(!_._2)
    (head :: l1).map(_._1) :: split(l2)
  }
}

Upvotes: 0

Views: 123

Answers (1)

proximator
proximator

Reputation: 688

Your program will throw a StackOverflow exception:

Exception in thread "main" java.lang.StackOverflowError
    at scala.collection.immutable.List.map(List.scala:283)

The reason is very simple because your method is not tail-recursive If you annotate it with @tailrec, it won't compile:

  @tailrec
  def split(list: List[(Pair, Boolean)]): List[List[Pair]] = list match {
    case Nil => Nil
    case head :: tail => {
      val (l1, l2) = tail.span(!_._2)
      (head :: l1).map(_._1) :: split(l2)
    }
  }

The solution is to make your recusion tailrec, or use some kind of loop instead

You could try something like this:

 @tailrec
  def split(list: List[(Pair, Boolean)], accumulator:  List[List[Pair]] = List[List[Pair]]()): List[List[Pair]] = list match {
    case Nil => accumulator
    case head :: tail => {
      val (l1, l2) = tail.span(!_._2)
      split(l2, (head :: l1).map(_._1)::accumulator)
    }
  }

Upvotes: 1

Related Questions