递归函数-Collatz

Question

我做了以下几点：

def collatz(b):
    l=[b]
    if b==1:
        return 1
    elif b%2==0:
        l.append(collatz(b/2))
    else:
        l.append(collatz(b*3+1))
    return l

但是，输出如下：

>>>[21, [64, [32, [16, [8, [4, [2, 1]]]]]]]

如何生成这样的输出(使用递归函数)：

>>>Collatz: 21 64 32 16 8 4 2 1

Answer 1

使用extend代替append，并确保总是返回一个列表，以返回一个“平面”列表：

def collatz(b):
    l=[b]
    if b==1:
        return [1]                  # wrapped in list
    elif b%2==0:
        l.extend(collatz(b/2))      # extend
    else:
        l.extend(collatz(b*3+1))    # extend
    return l

或者更简洁一点：

def collatz(b):
    if b == 1:
        return [b]
    elif b%2==0:
        return [b] + collatz(b/2)
    else:
        return [b] + collatz(b*3+1)

如果要返回Collatz:前缀，则必须使用包装函数：

def collatz(x):
    def collatz_inner(b):
        if b == 1:
            return [b]
        elif b%2==0:
            return [b] + collatz_inner(b/2)
        else:
            return [b] + collatz_inner(b*3+1)
    return "Collatz: " + ' '.join(map(str, collatz_inner(x)))

Answer 2

正如tobias已经回答的那样，您需要扩展not append来获取平面列表，但您也可以使用if/else返回[b] + collatz...来获取返回的值的平面列表：

def collatz(b):
    if b == 1:
        return [b]
    return [b] + collatz(b / 2) if not b % 2 else [b] + collatz(b * 3 + 1)

您可以使用打印以任意方式格式化输出：

In [5]: from __future__ import print_function

In [6]: print("Collatz :",*collatz(20))
Collatz : 20 10 5 16 8 4 2 1

您可能还应该确保输入是非负的，否则将导致RuntimeError。