The recursive implementation with python for a mathematical puzzle of hailstone sequence or Collatz conjecture?
<p>There is a mathematical puzzle:</p>

<ol>
<li>Pick a positive integer n as start. </li>
<li>If n is even, then divide it by 2.</li>
<li>If n is odd, multiply it by 3, and add 1. </li>
<li>continue this process until n is 1.</li>
</ol>

<p>I want to write a recursive function, that takes the n as parameter, and then return a tuple that includes a sequence of track of n in the process, and the length of sequence. But failed. </p>

<p>What wrong is my code? How to achieve the task?</p>

<pre><code>def hailstone(n):
    """the implementation of recursive one,
    return a tuple that includes the hailstone sequence
    starting at n, and the length of sequence.

    &gt;&gt;&gt; a = hailstone(1)
    ([1, 4, 2, 1], 4)
    """
    if n % 2 == 0:
        n = n//2
    else:
        n = n*3 + 1

    if n == 1:
        return [n]
    else:
        """
        for some magic code here,
        it will return a tuple that includes the list track of n,
        and the length of sequence,
        like ([1, 4, 2, 1], 4)
        """
        return ([n for some_magic in hailstone(n)], lenght_of_seq)
</code></pre>

<p>First, you need to decide whether to use an iterative or recursive process - in Python it doesn't matter much (since Python doesn't employ tail call optimization), but in languages it could. For a more in-depth explanation of iterative/recursive process see <a href="http://stackoverflow.com/q/17254240/106471" title="SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process">this question</a>.</p>

<p>In either case, it's usually best to start from the ending condition and work your way from there. In this case that's <code>n == 1</code>.</p>

<h2>Recursive process</h2>

<p>Let's start with a recursive process. In this case, state is maintained in the call chain, and the result is computed once we have reached the innermost call (and we're returning up the call chain).</p>

<pre><code>def hailstone(n):
    if n == 1:
        return [n], 1
</code></pre>

<p>Alright, that's the end condition - now we've made sure the function will return once <code>n</code> is 1. Let's continue and add the rest of the conditions:</p>

<pre><code>def hailstone_rec(n):
    if n == 1:
        return (n,), 1

    if n % 2 == 0: # Even
        rest = hailstone_rec(n//2)
    else: # Odd
        rest = hailstone_rec(n*3+1)

    return (n,) + rest[0], rest[1] + 1
</code></pre>

<p>What happens here when <code>n</code> is not 1, is that we first recurse to compute the rest of the sequence, and then add the values for current invocation to that result. So, if <code>n</code> is 2, this means we'll compute <code>hailstone_rec(2//2)</code> which will return <code>((1,), 1)</code>, and then we add the current values and return the result (<code>((2, 1), 2)</code>).</p>

<h2>Iterative process</h2>

<p>With an iterative process, the result is computed while proceeding down the call chain, and you pass the current state into the next function call when recursing. This means that the result does not depend on calls higher up in the call chain, which means that when the end is reached, the innermost function can just return the result. This has significance in languages with tail call optimization, since the state of the outer calls may be discarded.</p>

<p>When implementing a function with this process it's often helpful to use an inner helper function with extra parameters to pass on the state, so let's define a user-facing function and an inner helper function:</p>

<pre><code># user facing function
def hailstone_it(n):
    # Call the helper function with initial values set
    return hailstone_it_helper(n, (), 0)

# internal helper function
def hailstone_it_helper(n, seq, length):
    pass
</code></pre>

<p>As can be seen, the user-facing function just calls the internal function with the state parameters set to initial values. Let's continue implementing the actual logic, all of which will reside inside the helper. As with the previous solution, let's start with the end condition (<code>n == 1</code>):</p>

<pre><code>def hailstone_it_helper(n, seq, length):
    if n == 1:
        return seq + (n,), length + 1
</code></pre>

<p>This time around, we take partial result from the previous call(s), add the current values, and return that. Now, handle the remaining cases:</p>

<pre><code>def hailstone_it_helper(n, seq, length):
    if n == 1:
        return seq + (n,), length + 1

    if n % 2 == 0: # Even
        return hailstone_it_helper(n//2, seq + (n,), length + 1)
    else:
        return hailstone_it_helper(n*3+1, seq + (n,), length + 1)

def hailstone_it(n):
    return hailstone_it_helper(n, (), 0)
</code></pre>

<p>When recursing here, we pass in the next n in the series (depending on whether the current n is even or odd), and the result so far.</p>

<h2>A more pythonic solution</h2>

<p>Finally, since you would normally not code like this in Python, let's finish with a more pythonic solution as a bonus (i.e, one that's not using recursion at all):</p>

<pre><code>def hailstone_pythonic(n):
    seq = []
    while n != 1:
        seq.append(n)
        if n % 2 == 0:
            n //= 2
        else:
            n = n * 3 + 1
    seq.append(n)
    return tuple(seq), len(seq)
</code></pre>

python algorithm recursion