CODEWITHSUNDEEP
javarecursionstack-overflowcollatz
sean mcdaid
sean mcdaid

Reputation:

Project Euler (P14): recursion problems

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

}

Upvotes: 5

Views: 4065

Answers (8)

shatrughan
shatrughan

Reputation: 1

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
  }

Upvotes: -1

chmu
chmu

Reputation: 1

Here you can have a look at my recursive implementation of problem 14:

http://chmu.bplaced.net/?p=265

Upvotes: 0

user467871
user467871

Reputation:

You can solve this problem not only with recursion but also with a single loop. there is overflow if you write int. because it generates long while chaning and the recursion never ends because never equal to 1 and you probably get stackoverflow error

Here is my solution with loop and recursion:

public class Collatz {

    public int getChainLength(long i) {
        int count = 1;

        while (i != 1) {
            count++;

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

        return count;
    }

    public static int getChainLength(long i, int count) {
        if (i == 1) {
            return count;
        } else if (i % 2 == 0) {
            return getChainLength(i / 2, count + 1);
        } else {
            return getChainLength(3 * i + 1, count + 1);
        }
    }

    public int getLongestChain(int number) {
        int longestChain[] = { 0, 0 };

        for (int i = 1; i < number; i++) {
            int chain = getChainLength(i);

            if (longestChain[1] < chain) {
                longestChain[0] = i;
                longestChain[1] = chain;
            }
        }

        return longestChain[0];
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(new Collatz().getLongestChain(1000000));
    }
}

Upvotes: 0

Hendra Jaya
Hendra Jaya

Reputation: 1628

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.

Upvotes: 1

Greg Leaver
Greg Leaver

Reputation: 801

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

Upvotes: 2

Sean McDaid
Sean McDaid

Reputation: 71

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.

Upvotes: 1

Jimmy
Jimmy

Reputation: 91482

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...

Upvotes: 8

Svante
Svante

Reputation: 51511

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.

Upvotes: 1

Related Questions