how can I improve the execution time of my tailrec function in scala for collatz chain

Question

 def collatzChainLength(n:Int):Int={
      @tailrec
      def collatz(n:Int,acc:Int):Int=
         if(n==1) acc+1
         else if (n%2==0) collatz(n/2,acc+1)
         else collatz(3*n+1,acc+1)
      collatz(n,0)
   }

I am getting almost instant result for 100000 iterations but after that it is taking infinity

 println( (1 to 100000).map(x=> 
(x,collatzChainLength(x))).foldLeft((0,0))((m,y)=>{ 
if(y._2>m._2) y else m}))
 println( (100001 to 200000).map(x=> 
(x,collatzChainLength(x))).foldLeft((0,0))((m,y)=>{ 
if(y._2>m._2) y else m}))

Answer 1

You could better do the tail recursion reduction on even, as the odd case gives an even. (negating the if)

Or:

  else collatz((3*n + 1)/2, acc +2)

But the actual solution is to have one single call at the end.

  if (n == 1) acc + 1
  else collatz(n & 1 == 0? n/2 : 3*n + 1, acc + 1)

Also use Long when reaching a third of 2³¹.

Answer 2

Although there are a handful of minor improvements you could make, the real problem here is that your Int value is overflowing. Even though 200000 is a comfortable Int value, remember that n can grow as well as shrink over the course of multiple iterations.

Make this change...

def collatzChainLength(n: Long): Int = { 

...and all the little following mods to reconcile the compiler, and you're good to go.