CODEWITHSUNDEEP
javarecursioncollatz
David
David

Reputation: 14963

Why doesn't this loop terminate?

Here's the sample code:

public static void col (int n) 
{
    if (n % 2 == 0) 
       n = n/2 ; 
    if (n % 2 != 0) 
       n = ((n*3)+1) ;

    System.out.println (n) ;
    if (n != 1) 
       col (n) ;
}

this works just fine until it gets down to 2. then it outputs 2 4 2 4 2 4 2 4 2 4 infinitely. it seems to me that if 2 is entered as n then (n % 2 == 0) is true 2 will be divided by 2 to yeild 1. then 1 will be printed and since (n != 1) is false the loop will terminate.

Why doesn't this happen?

Upvotes: 3

Views: 336

Answers (8)

terrific
terrific

Reputation: 1667

if (n % 2 != 0) n = ((n*3)+1) ;

this code is again implemented whenever u get 1.

therefore the recursive function will be called repeatedly hence leading to an infinite rec calling and code will never terminate.

Upvotes: 0

mjv
mjv

Reputation: 75255

The answer to the question can be read directly in the code:

Assume n is 2
(n % 2 == 0) is true therefore n <- 1
(n % 2 != 0) is also true therefore 4 <- n

this warrants a call to function with n = 4,  which is then changed to 2 and
"back to square 1"

by replacing the second test by an else, you solve this logic problem, at the cost of possibly causing more recursion (since in the current logic, two operations are sometimes performed in one iteration). Such a fix will also solve a more subtle bug, which is that in the current version not all new values of n are printed out.

Now, for extra credit, prove that not matter the initial value of n, the number of recursions is finite (i.e. the sequence converges to 1). ;-)

Upvotes: 1

Igby Largeman
Igby Largeman

Reputation: 16747

Because when you get to 1, you are multiplying by 3 and adding 1, taking you back to 4.

You need an ELSE in there. I don't know java, but it would look something like:

public static void col (int n) 
{
    if (n % 2 == 0) 
      n = n/2 ; 
    else if (n % 2 != 0) 
      n = ((n*3)+1) ;

    System.out.println (n) ;
    if (n != 1) 
      col (n) ;
}

EDIT: as mentioned in the comments, you can omit the if test after the else:

if (n % 2 == 0) 
  n = n/2 ; 
else 
  n = ((n*3)+1) ;

Upvotes: 13

David
David

Reputation: 14963

in addition to an else if to govern the condition that n is odd that same line also needs & n != 1 to be added to it within the conditional. So this: 

else if (n % 2 != 0 & n != 1)

Upvotes: -1

jwismar
jwismar

Reputation: 12268

Does it work if you change it to this?

if (n % 2 == 0) 
    n = n/2 ; 
else if (n % 2 != 0) 
    n = ((n*3)+1) ;

It looks like you're getting 2, dividing by 2 to get 1, then checking to see if 1/2 has a remainder (it does), and multiplying it by 3 and adding 1, to get 4....

Upvotes: 0

matt b
matt b

Reputation: 139971

when the input is 2:

if (n % 2 == 0)         //true
  n = n/2;              //n = 1 
if (n % 2 != 0)         //true
  n = ((n*3)+1);        //n = 4

System.out.println (n); //prints 4
if (n != 1)             //true
  col (n);              //call col(4)

Upvotes: 0

codaddict
codaddict

Reputation: 455292

I think you'll have to change the 2nd if statement to an else

if (n % 2 == 0)      // if the n is even
  n = n/2 ; 
else                 // if n is odd
  n = ((n*3)+1) ;

Upvotes: 2

President James K. Polk
President James K. Polk

Reputation: 42010

Use if/then/else. Your logic is wrong.

Upvotes: 0

Related Questions