I've got infinite looping

Question

i am practicing my java by counting possible ways to reach n with a dice. and when input n value to smaller number, it works. but when i input n value to 100, it got infinite looping.

can u guys help me ?

here is my code :

public static void main(String[] args) { testCode test = new testCode(); System.out.println(test.countWays(100)); } private static int countWays(int n) { if(n<=1) { return 1; } else { System.out.println("counting ...."); return countWays(n-6) + countWays(n-5) + countWays(n-4) + countWays(n-3) + countWays(n-2) + countWays(n-1); } }

.... but it doesn't look infinite actually, just very large. — Hovercraft Full Of Eels
– Hovercraft Full Of Eels, Commented Feb 5, 2017 at 15:14
@HovercraftFullOfEels Actually it's not infinite recursion, but before it reaches the base case it most likely hits stack overflow. — Tim Biegeleisen
– Tim Biegeleisen, Commented Feb 5, 2017 at 15:15
Consider: Every single time you call countWays with n > 1, you trigger six further calls to it. Each of those triggers six further calls (e.g., 36 more; 43 so far if you're counting); each of those 36 triggers six further calls (259 so far), and so on, and so on. — T.J. Crowder
– T.J. Crowder, Commented Feb 5, 2017 at 15:16

azro · Accepted Answer · 2017-02-05 15:54:51Z

Your problem is similar to Fibonnaci's one :

x0 = 0, x1 = 1, x(N) = x(N-2) + x(N-1)

If you need to do it with big numbers you should use a non-recursive method :

static long countBis(int n) { long fn, f1, f2, f3, f4, f5, f6; int i; f1=f2=f3=f4=f5=f6=fn = 1; for ( i = 2; i <= n; i++ ) { f6 = f5; f5 = f4; f4 = f3; f3 = f2; f2 = f1; f1 = fn; fn = f6 + f5 + f4 + f3 + f2 + f1; } return fn; }

At each iteration you just calculate the sum of the precedent ones

I've tested with n = 32 => with yours it took 8sec, with this one it took less than 1sec (I tried with n = 1000 => always 1sec, but i didn't try yours haha, after n = 35 it's a bit long ^^

WOW, it works ! thankyou very much sir. but can i ask u question? why i=2?
Thanks, just because i have i<=n then, it can be changed in : i=1 ; i<n To do like you, because if you set n=5 you'll do (n-1) iterations until 1, so I coded to do same as you, from 1 include to n exclude : (n-1) iterations

Collectives™ on Stack Overflow

I've got infinite looping

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related