冰雹序列或Collatz猜想的数学难题的python递归实现？

Question

有一个数学难题：

1. 选择一个正整数n作为开始。在
2. 如果n是偶数，则除以2。在
3. 如果n是奇数，乘以3，再加1。在
4. 继续这个过程直到n为1。在

我想写一个递归函数，以n作为参数，然后返回一个元组，该元组包含进程中n的track序列，以及序列的长度。但是失败了。在

我的密码怎么了？如何完成任务？在

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

    >>> 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)

Answer 1

您可以使用累加器：

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, [])

现在，行动起来：

^{pr2}$

Answer 2

首先，您需要决定是使用迭代过程还是递归过程——在Python中，这并不重要（因为Python不使用尾部调用优化），但是在语言中可以。有关迭代/递归过程的更深入解释，请参见this question。在

无论哪种情况，通常最好从结束条件开始，然后从那里开始工作。在本例中是n == 1。在

递归过程

让我们从递归过程开始。在这种情况下，状态是在调用链中维护的，一旦到达最内层的调用（并返回调用链），就会计算结果。在

def hailstone(n):
    if n == 1:
        return [n], 1

好了，这是结束条件-现在我们确保函数将返回一次n为1。让我们继续并添加其他条件：

^{pr2}$

当n不是1时，我们首先递归计算序列的其余部分，然后将当前调用的值添加到结果中。所以，如果n是2，这意味着我们将计算hailstone_rec(2//2)，它将返回((1,), 1)，然后我们添加当前值并返回结果（((2, 1), 2)）。在

迭代过程

在迭代过程中，结果是在沿着调用链继续进行时计算的，递归时将当前状态传递给下一个函数调用。这意味着结果不依赖于调用链中更高层的调用，这意味着当到达结尾时，最里面的函数可以返回结果。这在具有尾部调用优化的语言中具有重要意义，因为外部调用的状态可能会被丢弃。在

使用此过程实现函数时，使用带有额外参数的内部辅助函数来传递状态通常很有帮助，因此，让我们定义一个面向用户的函数和一个内部助手函数：

# 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

可以看出，面向用户的函数只调用内部函数，状态参数设置为初始值。让我们继续实现实际的逻辑，所有这些逻辑都将驻留在helper中。与前面的解决方案一样，让我们从结束条件（n == 1）开始：

def hailstone_it_helper(n, seq, length):
    if n == 1:
        return seq + (n,), length + 1

这一次，我们从上一次调用中获取部分结果，添加当前值，然后返回该结果。现在，处理剩下的案子：

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)

在这里递归时，我们传入序列中的下一个n（取决于当前n是偶数还是奇数），以及到目前为止的结果。在

更像Python的解决方案

最后，由于您通常不会在Python中编写这样的代码，让我们以一个更具Python风格的解决方案作为结束（即，一个根本不使用递归的解决方案）：

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)