时间戳

首页 > 解决方案 > 我尝试使用递归来解决所谓的 tribonacci 序列问题

python - 我尝试使用递归来解决所谓的 tribonacci 序列问题

问题描述

该函数应该像 tribonacci([1, 1, 1], 10)-> [1, 1, 1, 3, 5, 9, 17, 31, 57, 105]

这是我的代码

def tribonacci(signature, n):
    if n <= 3:
        return signature[:3]
    else:
        return tribonacci(signature, n-1).append(sum(tribonacci(signature, n-1)[-3:]))

它给了我一个 AttributeError：“NoneType”对象没有“附加”属性。

我真的不知道问题出在哪里。有人可以详细告诉我递归是如何工作的吗？

标签： pythonrecursion

解决方案

正如@JonClements 在评论中已经指出的那样，该append方法不返回列表。它返回，因此调用者在尝试将其用作列表None时会遇到异常。None

作为旁注，两次进行相同的递归调用是低效的。这将使您的程序第二次执行所有相同的工作。

因此，要解决这两个问题，只需一步一步进行，如下所示：

def tribonacci(signature, n):
    if n <= 3:
        return signature[:3]
    else:
        result = tribonacci(signature, n-1)
        result.append(sum(result[-3:]))
        return result

这可行，但看起来仍然有点可疑，因为result列表在每个递归级别中都发生了变化。这意味着理论上所有这些执行上下文都会在递归树的更高级别上看到稍后完成的突变。这在此特定代码中不是问题，但人们可能会认为不改变列表而是返回一个新列表更安全：

def tribonacci(signature, n):
    if n <= 3:
        return signature[:3]
    else:
        result = tribonacci(signature, n-1)
        return result + [sum(result[-3:])]

print(tribonacci([1,1,1], 10))

如果要使用不同的n值（但相同的签名）多次调用此函数，则如果您实施记忆化，您将获得效率提升，以便可以重用早期的结果。

推荐阅读