Project Euler (P14): recursion problems

Question

Hi I'm doing the Collatz sequence problem in project Euler (problem 14). My code works with numbers below 100000 but with numbers bigger I get stack over-flow error.

Is there a way I can re-factor the code to use tail recursion, or prevent the stack overflow. The code is below:

import java.util.*;

public class v4
{

   // use a HashMap to store computed number, and chain size 

   static HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

   public static void main(String[] args)
   {

      hm.put(1, 1);

      final int CEILING_MAX=Integer.parseInt(args[0]);
      int len=1;
      int max_count=1;
      int max_seed=1;

      for(int i=2; i<CEILING_MAX; i++)
      {
          len = seqCount(i);

          if(len > max_count)
          {
             max_count = len;
             max_seed = i;
          }
      }
      System.out.println(max_seed+"\t"+max_count);
   }

   // find the size of the hailstone sequence for N

   public static int seqCount(int n)
   {

      if(hm.get(n) != null)
      {
         return hm.get(n);
      }

      if(n ==1)
      {
         return 1;
      }
      else
      {
         int length = 1 + seqCount(nextSeq(n));
         hm.put(n, length);
         return length;
      }
   }

   // Find the next element in the sequence

   public static int nextSeq(int n)
   {

      if(n%2 == 0)
      {
         return n/2;
      }
      else
      {
         return n*3+1;
      }
   }

}

Answer 1

See this link for your answer: http://stackoverflow.com/questions/376346/project-euler-p14-recursion-problems

Answer 2

Your problem is not with the size of the stack (you're already memoizing the values), but with

1. the size of some of the numbers in the sequences, and
2. the upper limits of a 32-bit integer.

Hint:

public static int seqCount(int n)
{
   if(hm.get(n) != null) {
       return hm.get(n);
   }
   if (n < 1) {
      // this should never happen, right? ;)
   } ...
   ...

That should hopefully be enough :)

P.S. you'll run into a need for BigNums in a lot of project euler problems...

Answer 3

Side note (as it seems that you don't actually need tail call optimization for this problem): tail call optimization is not available in Java, and as far as I have heard, it is not even supported by the JVM bytecode. This means that any deep recursion is not possible, and you have to refactor it to use some other loop construct.

Answer 4

If you are counting the size of the Collatz sequence for numbers upto 1,000,000 you should re-consider using Integer type. I suggest using BigInteger or possible a long.

This should alleviate the problems encountered, but be warned you may still run out of heap-space depending on your JVM.

Answer 5

If you change from integer to long it will give you enough room to solve the problem. Here was the code that I used to answer this one:

 for(int i=1;i<=1000000;i+=2)
 {
  steps=1;
  int n=i;
  long current=i;
  while(current!=1)
  {
   if(current%2==0)
   {
    current=current/2;
   }else{
    current=(current*3)+1;
   }
   steps++;
  }
  if(steps>best)
  {
   best=steps;
   answer=n;
  }
 }

Brute forcing it, takes about 9 seconds to run

Answer 6

I think you need these 2 hints :

1. Don't use Integer because at some starting number, the sequence will fly into some numbers greater than Integer.Max_VALUE which is 2147483647. Use Long instead.
2. Try not to use recursion to solve this problem, even with memoization. As i mentioned earlier some numbers will fly high and produce a great deal of stacks which will lead into stack overflow. Try using "regular" iteration like do-while or for. Of course you can still use some ingredient like memoization in "regular" loop.

Oh i forget something. Perhaps the stack overflow occurs because of arithmetic overflow. Since you use Integer, maybe Java "change" those "flying numbers" into a negative number when arithmetic overflow occurs. And as seen in method seqCount(int), you don't check invariant n > 0.

Answer 7

import java .util.*; public class file { public static void main(String [] args) { long largest=0; long number=0; for( long i=106239;i<1000000;i=i+2) { long k=1; long z=i; while(z!=1) { if(z%2==0) { k++; z=z/2; } else{ k++; z=3*z+1; } }
if(k>largest) { number=i; largest=k; System.out.println(number+" "+largest); } }//for loop

}//main }