Hailstone Sequences in Python

Question

For the problem given:

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 thesis is: 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. Write a function that takes a single argument with formal parameter name \$n\$, prints out the hailstone sequence starting at \$n\$, and returns the number of steps in the sequence.

Hailstone sequences can get quite long! Try 27. What's the longest you can find? Fill in your solution below:

def hailstone(n):
    """Print the hailstone sequence starting at n and return its length.

    >>> a = hailstone(10)  # Seven elements are 10, 5, 16, 8, 4, 2, 1
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** YOUR CODE HERE ***"

Below is the solution written for above problem that performs hailstone sequence:

def hailstone(n):
    count = 1
    """Print the terms of the 'hailstone sequence' from n to 1."""
    assert n > 0
    print(n)
    if n > 1:
        if n % 2 == 0:
            count += hailstone(n / 2)
        else:
            count += hailstone((n * 3) + 1)
    return count

result = hailstone(10)
print(result)

With the above solution, I would like to confirm that this program follows functional paradigm instead of imperative paradigm with good abstraction.

I would like to understand if this program can still be improved from paradigm perspective.

Answer 1

The docstring needs to be the first thing that appears in your function.

In functional programming, it is not proper to ever change the value of a variable.

If you know that you need integer division rather than floating-point division, use // instead of /.

A common idiom for recursion is

def recursive_function(input):
    if base_case_applies(input):
        return base_value
    else:
        return …(recursive_function(…))

Your recursive function would therefore be better expressed as:

def hailstone(n):
    """Print the terms of the 'hailstone sequence' from n to 1, and
    return the length of the sequence."""
    assert n > 0
    print(n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + hailstone(n // 2)
    else:
        return 1 + hailstone(3 * n + 1)

An even more functional programming approach, which admittedly looks horrible in Python and therefore isn't something I recommend, is to use a single expression for the recursion.

def hailstone(n):
    """Print the terms of the 'hailstone sequence' from n to 1, and
    return the length of the sequence."""
    assert n > 0
    print(n)
    return 1 if n == 1 else \
           1 + hailstone((n // 2) if n % 2 == 0 else (3 * n + 1))

Answer 2

Why do you have to use recursion?

What's wrong with

while n > 1:
    if n % 2 == 0:
        n = n / 2
    else:
        n = ((n * 3) + 1)
    print(n)
    count += 1

?

Recursion just complicates the program. When you can use iteration, just use that. Recursion is best suited for cases where you can leverage the ability of function calls to "reset" local variables.

Answer 3

Some minor things:

1. The docstring usually gets at least two lines. you can also specify parameters and types in it. (minor n

   def hailstone(n):
       """
       Print the terms of the 'hailstone sequence' from n to 1
   
       :param n: The starting point of the hailstone sequence
       :type n: int
       """
   

2. You should not execute this when you import the module. Wrap your global namespace code into a proper execution context:

   if __name__ == '__main__':
       hailstone(10)