python - 用python递归实现冰雹序列或Collat​​z猜想的数学难题？

Question

有一道数学题:

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

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

我的代码有什么问题？如何完成任务？

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

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

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

递归过程

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

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

好的，这就是结束条件 - 现在我们已经确保函数将在 n 为 1 时返回。让我们继续并添加其余条件:

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

当 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

可以看出，面向用户的函数只是调用状态参数设置为初始值的内部函数。让我们继续实现实际的逻辑，所有这些都将驻留在帮助程序中。与前面的解决方案一样，让我们​​从结束条件 (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是偶数还是奇数)，以及到目前为止的结果。

更pythonic的解决方案

最后，由于您通常不会在 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)