Scala slow hashmap
<p>For <a href="https://projecteuler.net/problem=14" rel="nofollow noreferrer" title="Project Euler problem 14">Project Euler problem 14</a>, I created this answer:</p>

<pre><code>import scala.collection.immutable.LongMap

object LongestCollatzSequencePerso {
  def nextElem(n: Long): Long = n match {
    case x if n % 2 == 0 =&gt; n / 2
    case _ =&gt; 3 * n + 1
  }

  def funcVal(acc: LongMap[Long], n: Long): LongMap[Long] = {
    if (acc.contains(n)) {
      return acc
    }
    else {
      val nNext = nextElem(n)
      val size = funcVal(acc, nNext)(nNext) + 1      
      return acc + (n -&gt; size)
    }
  }

  def main = {
    val max = 1000000L
    val allVal = (1L to max).foldLeft(LongMap(1L -&gt; 1L))(funcVal)
    println(allVal.filter(_._1 &lt; max).maxBy(_._2)._1)
  }
}
</code></pre>

<p>I use an immutable <code>LongMap</code> that caches every result computed so far, in order to stop recursive call as soon as one has to be returned. My code is very slow, and I can not get the result.</p>

<p>Now this code, taken from the Internet, does not cache anything:</p>

<pre><code>object LongestCollatzSequenceWeb {  
  def from(n: Long, c: Int = 0): Int = if (n == 1) c + 1 else
    from(if (n % 2 == 0) n / 2 else 3 * n + 1, c + 1)

  val r = (1 until 1000000).view
                           .map(n =&gt; (n, from(n)))
                           .reduceLeft((a, b) =&gt; if (a._2 &gt; b._2) a else b)
                           ._1

  def main = println(r)
}
</code></pre>

<p>But it runs fast enough to get the correct answer in a short time.</p>

<p>Why is my cached version so slow ? I understand that caching creates its own overhead, but I was hoping to get a result in a reasonnable time anyway. Do you see a way I could increase the performances while keeping everything immutable ?</p>

<p>I also created this tail recursive version (as suggested in an answer), but it is very slow too:</p>

<pre><code>import scala.annotation.tailrec
import scala.collection.immutable.LongMap

object LongestCollatzSequenceTailRec {
  def nextElem(n: Long): Long = n match {
    case x if n % 2 == 0 =&gt; n / 2
    case _ =&gt; 3 * n + 1
  }

  @tailrec
  def funcVal(acc: (List[Long], LongMap[Long]), n: Long): (List[Long], LongMap[Long]) = {
    val (previous, dic) = acc
    if (dic.contains(n)) {
      val disN = dic(n)
      val dis = disN + 1 to disN + previous.length
      return (Nil, dic ++ previous.zip(dis))
    }
    else {   
      return funcVal((n :: previous, dic), nextElem(n))
    }
  }

  def main = {
    val max = 1000000L
    val allVal = (1L to max).foldLeft((List[Long](), LongMap(1L -&gt; 1L)))(funcVal)
    println(allVal._2.filter(_._1 &lt; max).maxBy(_._2)._1)
  }
}
</code></pre>