Why doesn't this loop terminate?

Question

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?

Answer 1

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) 

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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)

Answer 7

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

Answer 8

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.