current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote -2 down vote favorite

Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle:

  • Pick a positive integer n as the start.
  • If n is even, divide it by 2.
  • If n is odd, multiply it by 3 and add 1.
  • Continue this process until n is 1.

The number n will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried -- nobody has ever proved that the sequence will terminate). Analogously, hailstone travels up and down in the atmosphere before eventually landing on earth.

The sequence of values of n is often called a Hailstone sequence, because hailstones also travel up and down in the atmosphere before falling to earth.

Does it make sense to implement using recursion? I wrote some bad solution below. Please correct me.

def hailstone(n):
    if(n<0):
        print("Invalid input")
        return 
    if(n==1):
        print(1)
        return 
    if(n%2 == 0):
        print(n)
        hailstone(n/2)
        return
    if(n%2==1):
        print(n)
        hailstone((n*3) + 1)
        return

How do I move the n<0 condition to the right place?

share|improve this question
1  
This is also known as the Collatz sequence. And yes, it makes sense to use recursion - then you can memoize it for an easy "dynamic programming" approach. –  jonrsharpe Jul 7 at 13:46
    
@jonrsharpe (n < 0) condition makes it bad coding style, so can you help me refine the code logic? –  overexchange Jul 8 at 6:20
    
What do you mean "bad coding style"? Where do you think "a right place" for if(n<0): would be? –  jonrsharpe Jul 8 at 7:38

1 Answer 1

up vote 2 down vote accepted

Your code is a bit awkward, mostly due to:

  1. Repetition;
  2. Repetition; and
  3. Doesn't follow PEP-0008 (specifically, e.g. if(n<0): should be if n < 0:.

A few comments:

def hailstone(n):
    if(n<0):
        print("Invalid input") # should be an exception
        return # don't need explicit return[ None]
    # what if n == 0?
    if(n==1):
        print(1) # same as print(n)
        return # see above 
    if(n%2 == 0): # n == 0 comes here and loops indefinitely
        print(n) # repeat
        hailstone(n/2)
        return # repeat
    if(n%2==1): # should just be else
        print(n) # repeat
        hailstone((n*3) + 1)
        return # repeat

An alternative, moving all the print(n) to the top and all the return (implicitly) to the bottom, would be:

def hailstone(n):
    """Print the terms of the 'hailstone sequence' from n to 1."""
    assert n > 0
    print(n)
    if n % 2 == 0:
        hailstone(n / 2) 
    elif n > 1:
        hailstone((n * 3) + 1)
share|improve this answer
    
we are printing the values whenever we enter into new localframe of a function, and then we are returning back with implicit return None which is at bottom of the function? –  overexchange Jul 8 at 8:00
    
@overexchange that's right. –  jonrsharpe Jul 8 at 8:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.