Thread: 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

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

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

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

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.