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>You can use an accumulator:</p>

<pre><code>def hailstone(n):
    """
    return a tuple that includes the hailstone sequence
    starting at n, and the length of sequence.
    1) Pick a positive integer n as start.
    2) If n is even, then divide it by 2.
    3) If n is odd, multiply it by 3, and add 1.
    4) continue this process until n is 1.
    """

    def hailstone_acc(n, acc):
        acc.append(n)
        if n == 1:
            return acc, len(acc)
        elif n % 2 == 0:
            return hailstone_acc(n//2, acc)
        else:
            return hailstone_acc(3*n + 1, acc)

    if n == 1:
        return hailstone_acc(4,[1])
    else:
        return hailstone_acc(n, [])
</code></pre>

<p>Now, in action:</p>

<pre><code>(trusty)juan@localhost:~/workspace/testing/hailstone$ python -i hailstone.py 
&gt;&gt;&gt; hailstone(1)
([1, 4, 2, 1], 4)
&gt;&gt;&gt; hailstone(4)
([4, 2, 1], 3)
&gt;&gt;&gt; hailstone(23)
([23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1], 16)
&gt;&gt;&gt; 
</code></pre>

python algorithm recursion