Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: StackOverflowError with recursive method

  1. #1
    Member samfin's Avatar
    Join Date
    Dec 2010
    Location
    Manchester UK
    Posts
    37
    Thanks
    1
    Thanked 5 Times in 4 Posts

    Default StackOverflowError with recursive method

    Hi,

    This is my first post here so hi all and bear with me.

    I am trying to solve problem 14 on Project Euler to find the longest Collatz sequence under 1000000. I have come up with the following code.

    public void solution14()
        {
           for(int i=1; i<1000000; i++)
           {
              collatz(i);
           } 
        }
     
        public int collatz(int n)
        {
            count++;
            if(n==1)
            {
                return 1;
            }
            if(n%2==0)
            {
                n=n/2;
            }
            else
            {
                n=n*3+1;    
            }
            collatz(n);
            return count;
        }

    The problem is that I am getting stack overflow error when I run the solution14 method and have the call to collatz(i) inside the for loop. If I call collatz(1000000) or any other number, I get the right answer with no errors.
    If I reduce the loop from 1000000 to 100000 it will work fine. Can anyone help please

    Thanks

    Sam


  2. #2
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: StackOverflowError with recursive method

    else
    {
    n=n*3+1;
    }
    collatz(n);

    300001

    collatz(300001)

    n = 900003 + 1 = 900004

    collatz(1 million)

    n = 3 million and 1

    collatz (3 million and 1)

    n = 9 million and 4

    collatz ((9 million and 4) / 2)

    4500002

    2250001

    6750004

    3375002

    1687501

    5062504

    2531252

    1265626

    632813

    1898440

    949220

    474610

    237305

    711916

    355958

    177979

    533938

    266969

    800908

    400454

    200227

    600682

    300341

    901024

    450512

    225256

    112628

    56314

    28157

    84472

    42236

    21118

    10559

    31678

    15839

    47518

    23759

    71278

    35639

    106918

    53459

    160378

    80189

    240568

    120284

    60142

    30071

    90214

    45107

    135322

    67661

    202984

    101492

    50746

    25373

    76120

    38060

    19030

    9515

    28546

    14273

    42820

    21410

    10705

    32116

    16058

    8029

    24088

    12044

    6022

    3011

    9034

    4517

    13552

    6776

    3388

    1694

    847

    2542

    1271

    3814

    1907

    5722

    2861

    8584

    4292

    2146

    1073

    3220

    1610

    805

    2416

    1208

    604

    302

    151

    454

    227

    682

    341

    1024

    512

    256

    128

    64

    32

    16

    8

    4

    2

    1

    done

  3. #3
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: StackOverflowError with recursive method

    I'm not certain on this, but if the same stack is handling between 1 and 1000000 it will be overwhelmed.

  4. #4
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: StackOverflowError with recursive method

    Welcome to the forums. Use some simple print line debugging to print out the values of i and see when the exception is being thrown. Then run the collatz function with just this value and print out the n values produced. (hint, also print out Integer.MAX_VALUE and compare it with the values produced, you should see that an int can get maxed out and produce unexpected behavior...)

  5. The Following User Says Thank You to copeg For This Useful Post:

    samfin (December 2nd, 2010)

  6. #5
    Member samfin's Avatar
    Join Date
    Dec 2010
    Location
    Manchester UK
    Posts
    37
    Thanks
    1
    Thanked 5 Times in 4 Posts

    Default Re: StackOverflowError with recursive method

    I found the numbers it wasn't working with and printed the output. As n got closer to the max value of int it would flip to a random minus number and then flip between -1 and -2 for ever more. Changed it to long and all ok. Thanks for your help.

Similar Threads

  1. recursive descent parser
    By gammaman in forum Algorithms & Recursion
    Replies: 4
    Last Post: March 21st, 2010, 03:50 AM
  2. Problem with Recursive code
    By Shadow703793 in forum Algorithms & Recursion
    Replies: 4
    Last Post: February 22nd, 2010, 09:36 PM
  3. [SOLVED] Recursive Sentence Finder
    By raphytaffy in forum Algorithms & Recursion
    Replies: 4
    Last Post: February 21st, 2010, 02:46 PM
  4. recursive search of all local disks
    By ttsdinesh in forum Java Theory & Questions
    Replies: 4
    Last Post: September 27th, 2009, 08:23 AM
  5. Java error "java.lang.StackOverflowError"
    By sanatkumar in forum Exceptions
    Replies: 2
    Last Post: July 7th, 2009, 02:40 PM