2

这是一个家庭作业问题。我尝试得到一个递归函数：

def problem_a(n):
    answer.append(n)
    if n == 1:
        return answer    
    elif n % 2 == 0:
        answer.append(n/2)
    else :
        answer.append(n*3 + 1)
        problem_a(n*3 + 1)

此代码显然不起作用，因为answer未定义为列表。使用循环它可以工作，但我想创建一个递归函数。我可以只使用一个列表作为输入，但我想知道是否存在更优雅的东西。

problem_a(7)应该作为输出：

[7, 22, 11, 34, 17, 52, 26, 13, 40 , 20, 10 ,5 ,16, 8, 4, 2, 1]
4

5 回答 5

2

您可以尝试使用生成器：

def problem_a(n):
    yield n
    if n == 1:
        return
    elif n % 2 == 0:
        x = n / 2
    else:
        x = n * 3 + 1

    for y in problem_a(x):
        yield y

print list(problem_a(7))
于 2013-06-17T11:33:08.590 回答
2

您可以定义一个局部变量answer并在递归调用中传递它。

def problem_a(n, answer = None):
    answer = [n] if answer is None else answer
    if n == 1:
        return answer
    elif n % 2 == 0:
        n = n/2
        answer.append(n)
    else:
        n = n*3 + 1
        answer.append(n)
    return problem_a(n, answer)

print problem_a(7)

输出：

[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
于 2013-06-17T11:26:35.243 回答
2

迄今为止建议的解决方案的一种替代解决方案（使用额外的参数将列表传递到递归链）是在您从递归返回时构建最终列表。这不是非常有效，因为连接列表需要复制它们，但它会起作用：

def problem_a(n):
    if n == 1:
        return [n]
    elif n % 2 == 0:
        return [n] + problem_a(n // 2)
    else:
        return [n] + problem_a(3*n + 1)
于 2013-06-17T11:48:08.757 回答
1

您的骨架解决方案有问题。你需要递归 whenn % 2 == 0以及 final else。该answer变量被赋予一个默认值，以便[]在没有参数的情况下首次调用该函数时将其初始化。

def problem_a(n, answer=None):
    if answer == None:
        answer = []

    answer.append(n)
    if n == 1:
        return answer    
    elif n % 2 == 0:
        return problem_a(n/2, answer)
    else :
        return problem_a(n*3 + 1, answer)

>>> problem_a(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

编辑

根据评论，使用可变的默认参数是一个坏主意。只需像在其他帖子中一样将其设置为 None 并检查它是否为 None 以创建新列表。我更改了答案以反映这一点。

原来的坏代码如下：

def problem_a(n, answer=[]):
    answer.append(n)
    ...
于 2013-06-17T11:35:23.707 回答
1

您还可以使用闭包：

>>> def s():
    ret = []
    def f(n):
        ret.append(n)
        if n % 2 == 0:
            f(int(n/2))
        elif n != 1:
            f(int(n*3 + 1))
        return ret
    return f

>>> s()
<function f at 0x00000000033A5848>
>>> s()(7)
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
于 2013-06-17T13:03:37.360 回答