6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ UnboundLocalError: local variable 'count' referenced before assignment \$\endgroup\$ – 200_success Feb 2 '15 at 11:39
  • 1
    \$\begingroup\$ Use global count to fix the error... \$\endgroup\$ – Pimgd Feb 2 '15 at 11:46
  • \$\begingroup\$ @200_success Yes, I did not fix that error, Because I still did not learn scoping in python and usage of global keyword \$\endgroup\$ – overexchange Feb 2 '15 at 13:14
6
\$\begingroup\$

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))
\$\endgroup\$
4
\$\begingroup\$

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)
    
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ am bad at using recursion, I need to improve on using recursion without errors. I guess this python execution model does not use stack frames(unlike C/Java) but uses heap. So, I think it is safe to use recursion for longest hailstone sequence. \$\endgroup\$ – overexchange Feb 2 '15 at 14:12
  • \$\begingroup\$ @overexchange Recursion would have been good if n was complex (like traversing a tree). Here, it's not needed, and recursion adds an unneeded overhead. \$\endgroup\$ – Pimgd Feb 2 '15 at 14:17
  • 2
    \$\begingroup\$ Python is not much different from Java. Excessively deep recursion would cause a stack overflow. \$\endgroup\$ – 200_success Feb 5 '15 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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