Project Euler (P14): recursion problems

Posted by sean mcdaid on Stack Overflow See other posts from Stack Overflow or by sean mcdaid
Published on 2008-12-17T22:51:53Z Indexed on 2010/05/22 13:30 UTC
Read the original article Hit count: 355

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;
      }
   }

}

© Stack Overflow or respective owner

Related posts about recursion

Related posts about project-euler